Лабораторная работа Двухэтапный симплекс-метод
Двухэтапный симплекс-метод применяется к задачам, заданным не в канонической форме.
Алгоритм двухэтапного симплекс-метода
1 шаг. Привести задачу к стандартному виду. Если он является каноническим – решать одноэтапным симплекс-методом (иди к шагу 5)
2 шаг. Составить вспомогательную задачу (см. лекцию). Решить ее симплекс-методом.
3 шаг. Если вспомогательная задача не имеет решения или по окончании решения получены ненулевые (положительные) коэффициенты в целевой функции вспомогательной задачи, то исходная задача не имеет решения, иначе иди к 4 шагу.
4 шаг. Отбросить вспомогательную целевую функцию, выписать начальное допустимое базисное решение.
5 шаг. Решить полученную каноническую задачу одноэтапным симплекс-методом.
Пример
Решить симплекс-методом
Найти
При ограничениях
Решение.
Задача записана не в стандартном виде. Приведем ее к стандартному виду. Изменим знаки в целевой функции и введем дополнительную переменную, чтобы избавиться от неравенства.
Это стандартный вид, не являющийся каноническим. Поэтому будем решать двухэтапным симплекс-методом.
Составим целевую функцию вспомогательной задачи
Построим симплекс-таблицу
| x1 x2 x3 x4 |своб
---------------------------------
| 1 1 -3 1 |7
| 1 3 1 0 |15
---------------------------------
F | -1 1 3 0 |0
F1 | -2 -4 2 -1 |-22
Ведущий столбец – 2 (т.к. минимальный отрицательный -4)
Ведущая строка – 2 (т.к 15/3 меньше, чем 7/1)
Ведущий элемент равен 3.
Проведем шаг симплекс-метода. Получим таблицу
| x1 x2 x3 x4 |своб
---------------------------------
| 2/3 0 -10/3 1 |2
х2 | 1/3 1 1/3 0 |5
---------------------------------
F |-4/3 0 8/3 0 |-5
F1 |-2/3 0 10/3 -1 |-2
Ведущий столбец – 4 (т.к. минимальный отрицательный -1)
Ведущая строка – 1
Ведущий элемент равен 1.
Проведем шаг симплекс-метода. Получим таблицу
| x1 x2 x3 x4 |своб
---------------------------------
х4 | 2/3 0 -10/3 1 |2
х2 | 1/3 1 1/3 0 |5
---------------------------------
F |-4/3 0 8/3 0 |-5
F1 | 0 0 0 0 |0
В строке вспомогательной целевой функции получены нули, значит, приведение к каноническому виду завершено. Выпишем начальное допустимое базисное решение: Х = (0, 5, 0, 2), F=5
Отбросим вспомогательную целевую функцию, получим таблицу
| x1 x2 x3 x4 |своб
---------------------------------
х4 | 2/3 0 -10/3 1 |2
х2 | 1/3 1 1/3 0 |5
---------------------------------
F |-4/3 0 8/3 0 |-5
Продолжим решение одноэтапным симплекс-методом, получим ответ
hmax = 7 при Х = (13, 0, 2)
Задание 1 (выполнить на занятии, показать преподавателю)
Решить задачу линейного программирования симплекс-методом
Задание 2 (индивидуальное)
Решить задачу 2 своего варианта лабораторной работы «Переборный метод»
Задание 3 (домашнее)
Написать программу, реализующую двухэтапный симплекс-метод. Задачу задавать в стандартном виде, чтение данных осуществлять из файла. Программа должна выдавать симплекс-таблицы и находить оптимальное решение задачи (минимум f и значения х), или выводить сообщения: «Область допустимых решений – пустое множество» или «Целевая функция не ограничена».