Как Решить Задачу Линейного Программирования в Excel Примеры • Варианты решения

Основные методы решения ЗЛП_Методичка. Основные методы решения задач линейного программирования

Задание. Реализуйте все нижеприведенные шаги в табличном процессоре Excel, необходимые для решения задачи ЛП.
Поясним последовательность действий при решения задачи ЛП табличным симплекс-методом на примере.

Задача. Решить задачу табличным симплекс-методом [8].

  1. .
  2. Задача каноническая.
  3. В каждом ограничении есть базисная переменная: — в первом, — во втором, — в третьем.
  4. В целевой функции нет базисных переменных.
  1. Откройте табличный процессор Excel и введите заголовок Табличный способ решения задач линейного программирования.
  2. Заполните начальную симплекс-таблицу.

Следующая строка таблицы соответствует первому ограничению. Базисная переменная, найденная в первом ограничении, свободный член, коэффициенты при переменных соответствующего ограничения. Аналогичным образом заполняются 2 и 3 строки.

  1. Проконтролируйте правильность заполнения таблицы. Так как , , — базисные переменные, то на пересечении (5 строка) с (столбец D) должна стоять 1 (ячейка D5), а в соответствующем столбце ниже – нули, на пересечении (6 строка) с (столбец E) должна стоять 1 (ячейка E6), а в соответствующем столбце ниже – нули, (7 строка) с (столбец H) должна стоять 1 (ячейка H7), а в соответствующем столбце ниже – нули.
  1. Запишите значение целевой функции, начальный опорный план, опираясь на столбец свободных членов (рис. 27).

Рис. 27 . Значение целевой функции и начальный опорный план.

  1. Так в индексной строке есть отрицательные коэффициенты при переменных, то опорный план не является оптимальным. Организуйте процесс улучшения плана, выполнив предложенные шаги.
  2. Среди отрицательных элементов индексной строки выберите наибольший по модулю элемент. Соответствующий столбец назовите ведущим. Данный столбец показывает, какую переменную необходимо включить в базис (рис. 28).
  1. Теперь необходимо определить какую переменную исключить из базиса. Для этого составьте отношения для всех элементов столбца свободных членов () к соответствующим элементам ведущего столбца (). Например, в ячейку I5 введите формулу =B5/C5. Растяните формулы для ячеек I6, I7, исключая ячейку индексной строки (рис. 29).
  1. Так как теперь — базисная переменная, то на пересечении (13 строка) с (столбец C) должна стоять 1 (ячейка С13), а в соответствующем столбце ниже – нули. С помощью элементарных преобразований сделайте ведущий столбец базисным.

В ячейку С13 запишите формулу = С5/2 (рис 34), нажмите Enter.

Рис. 34. Получение 1 в ячейке С13.
Растяните формулу (рис. 35).

Рис. 35. Первая строка второй симплексной таблицы.
Затем получите нуль в ячейке С14.

Для этого во второй симплексной таблице 1 (ячейка С13) умножьте на элемент предыдущей таблицы, соответствующий элементу ячейки С14, взятый с противоположным знаком и сложите с этим же элементом.

Так как элемент, соответствующий элементу ячейки С14 равен 1 (ячейка С6), то это означает, что все элементы первой строки второй симплексной таблицы умножаются на (-1) и складывается с соответствующими элементами первой симплексной ьаблицы. Запишите в ячейку С14 формулу =C13*(-1)+C6 (рис. 36).

Рис. 36. Элемент С14 второй симплексной таблицы.
Аналогичным образом получите остальные элементы базисного столбца (рис. 37 и рис. 38).

Рис. 38. Элемент С16 второй симплексной таблицы.

  1. Так в индексной строке есть отрицательные коэффициенты при переменных, то опорный план не является оптимальным.
  2. Запишите значение целевой функции, найденный новый опорный план, опираясь на столбец свободных членов (рис. 40). Проконтролируйте, что значение целевой функции максимизируется.

Рис. 40. Значение целевой функции и опорного плана второй симплексной таблицы.

  1. Организуйте процесс улучшения плана, выполнив предложенные шаги, начиная с пункта 5, до тех пор пока не будет выполняться какой-нибудь из критериев остановки. Получите третью симплексную таблицу (рис. 41).

Рис. 41. Первая, вторая и третья симплексные таблицы.

Задание. Воспользуйтесь материалами лабораторной работы №3. Выполните проверку, используя программу MathCad.

Лабораторная работа №4. Реализация пошагового алгоритма решения задачи линейного программирования табличным симплекс-методом средствами Excel при выполнении всех условий
Общая задача линейного программирования
решается симплексным методом
Симплекс (лат. simplex — простой) –
простейший выпуклый многогранник
в n-мерном пространстве с n+1 вершиной
(например, тетраэдр в 3-мерном
пространстве)
Знайка, самый умный эксперт в Цветочном городе
Мнение эксперта
Знайка, самый умный эксперт в Цветочном городе
Если у вас есть вопросы, задавайте их мне!
Задать вопрос эксперту
Так как элемент, соответствующий элементу ячейки С14 равен 1 ячейка С6 , то это означает, что все элементы первой строки второй симплексной таблицы умножаются на -1 и складывается с соответствующими элементами первой симплексной ьаблицы. Если же вы хотите что-то уточнить, я с радостью помогу!
План называется ациклическим, если его базисные клетки не содержат циклов. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ниже приведен пример цикла:
Как Решить Задачу Линейного Программирования в Excel Примеры • Варианты решения

Транспортная задача в Microsoft Excel. Методы оптимальных решений. Транспортная задача в MS Excel

  1. .
  2. Задача каноническая.
  3. В каждом ограничении есть базисная переменная: — в первом, — во втором, — в третьем.
  4. В целевой функции нет базисных переменных.
  1. Откройте табличный процессор Excel и введите заголовок Табличный способ решения задач линейного программирования.
  2. Заполните начальную симплекс-таблицу.

Решим в MS Excel задачу линейного программирования
3. Создадим область ограничений
В ячейках А11:А13 будем
вычислять левые части
ограничений в системе
В ячейках В11:В13 введем правые
части ограничений системы

Оставить отзыв

Публикуя свою персональную информацию в открытом доступе на нашем сайте вы, даете согласие на обработку персональных данных и самостоятельно несете ответственность за содержание высказываний, мнений и предоставляемых данных. Мы никак не используем, не продаем и не передаем ваши данные третьим лицам.