Как Решить Задачу Линейного Программирования в Excel Примеры • Варианты решения
Основные методы решения ЗЛП_Методичка. Основные методы решения задач линейного программирования
Задание. Реализуйте все нижеприведенные шаги в табличном процессоре Excel, необходимые для решения задачи ЛП.
Поясним последовательность действий при решения задачи ЛП табличным симплекс-методом на примере.
Задача. Решить задачу табличным симплекс-методом [8].
- .
- Задача каноническая.
- В каждом ограничении есть базисная переменная: — в первом, — во втором, — в третьем.
- В целевой функции нет базисных переменных.
- Откройте табличный процессор Excel и введите заголовок Табличный способ решения задач линейного программирования.
- Заполните начальную симплекс-таблицу.
Следующая строка таблицы соответствует первому ограничению. Базисная переменная, найденная в первом ограничении, свободный член, коэффициенты при переменных соответствующего ограничения. Аналогичным образом заполняются 2 и 3 строки.
- Проконтролируйте правильность заполнения таблицы. Так как , , — базисные переменные, то на пересечении (5 строка) с (столбец D) должна стоять 1 (ячейка D5), а в соответствующем столбце ниже – нули, на пересечении (6 строка) с (столбец E) должна стоять 1 (ячейка E6), а в соответствующем столбце ниже – нули, (7 строка) с (столбец H) должна стоять 1 (ячейка H7), а в соответствующем столбце ниже – нули.
- Запишите значение целевой функции, начальный опорный план, опираясь на столбец свободных членов (рис. 27).
Рис. 27 . Значение целевой функции и начальный опорный план.
- Так в индексной строке есть отрицательные коэффициенты при переменных, то опорный план не является оптимальным. Организуйте процесс улучшения плана, выполнив предложенные шаги.
- Среди отрицательных элементов индексной строки выберите наибольший по модулю элемент. Соответствующий столбец назовите ведущим. Данный столбец показывает, какую переменную необходимо включить в базис (рис. 28).
- Теперь необходимо определить какую переменную исключить из базиса. Для этого составьте отношения для всех элементов столбца свободных членов () к соответствующим элементам ведущего столбца (). Например, в ячейку I5 введите формулу =B5/C5. Растяните формулы для ячеек I6, I7, исключая ячейку индексной строки (рис. 29).
- Так как теперь — базисная переменная, то на пересечении (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 второй симплексной таблицы.
- Так в индексной строке есть отрицательные коэффициенты при переменных, то опорный план не является оптимальным.
- Запишите значение целевой функции, найденный новый опорный план, опираясь на столбец свободных членов (рис. 40). Проконтролируйте, что значение целевой функции максимизируется.
Рис. 40. Значение целевой функции и опорного плана второй симплексной таблицы.
- Организуйте процесс улучшения плана, выполнив предложенные шаги, начиная с пункта 5, до тех пор пока не будет выполняться какой-нибудь из критериев остановки. Получите третью симплексную таблицу (рис. 41).
Рис. 41. Первая, вторая и третья симплексные таблицы.
Задание. Воспользуйтесь материалами лабораторной работы №3. Выполните проверку, используя программу MathCad.
решается симплексным методом
Симплекс (лат. simplex — простой) –
простейший выпуклый многогранник
в n-мерном пространстве с n+1 вершиной
(например, тетраэдр в 3-мерном
пространстве)
Транспортная задача в Microsoft Excel. Методы оптимальных решений. Транспортная задача в MS Excel
- .
- Задача каноническая.
- В каждом ограничении есть базисная переменная: — в первом, — во втором, — в третьем.
- В целевой функции нет базисных переменных.
- Откройте табличный процессор Excel и введите заголовок Табличный способ решения задач линейного программирования.
- Заполните начальную симплекс-таблицу.
Решим в MS Excel задачу линейного программирования
3. Создадим область ограничений
В ячейках А11:А13 будем
вычислять левые части
ограничений в системе
В ячейках В11:В13 введем правые
части ограничений системы
Публикуя свою персональную информацию в открытом доступе на нашем сайте вы, даете согласие на обработку персональных данных и самостоятельно несете ответственность за содержание высказываний, мнений и предоставляемых данных. Мы никак не используем, не продаем и не передаем ваши данные третьим лицам.