Пример решения задачи методом искусственного
Базиса
Выделить допустимое базисное решение для задачи ЛП:
Приведем задачу к канонической форме на минимум с неотрицательными правыми частями:
Заметим, что переменные 
и 
можно использовать для введения в исходный базис, поэтому в первую и третью строку ограничений можно не вводить искусственные переменные.
Во вторую строку ограничений вводим искусственную переменную z, потому что в этой строке нет переменной, которую можно взять базисной, не проводя при этом дополнительных преобразований всей системы ограничений.
Полученная вспомогательная задача имеет вид
Приведем задачу к виду (16):
Выпишем соответствующую симплексную таблицу:
| B | 
| 
| 
| |
| 10 | 5 | 4 | -1 |
| 3 | 3 | -2 | 0 |
| 10 | 5 | 4 | -1 |
| 5 | 2 | 1 | 0 |
Ведущий столбец рекомендуется выбирать не по максимальному положительному элементу строки целевой функции, а так, чтобы из базиса выводилась искусственная базисная переменная (соответствующая ведущая строка должна быть строкой искусственной переменной). Так, выбрав ведущим столбцом, столбец переменной 
, получим ведущую строку – строку с переменной z (выбирая ведущим столбцом 
, получили бы ведущую строку , и из базиса выводилась бы переменная ).
Итак, искусственная переменная z выйдет из базиса, а переменная введется в базис.
Симплексная таблица преобразуется к виду:
| B |
|
|
| |
|
| 0 | 0 | -1 | 0 |
|
| 8 | 11/2 | 1/2 | -1/2 |
|
| 5/2 | 5/4 | 1/4 | -1/4 |
|
| 5/2 | 3/4 | -1/4 | 1/4 |
|
|
|
Так как значение 
, то полученный базис 
является начальным допустимым базисом для исходной задачи ЛП. Чтобы выразить целевую функцию 
через небазисные переменные 
, подставим значение базисной переменной 
в целевую функцию. В результате получим:
Тогда исходная задача будет иметь вид специальной формы задачи ЛП:
что и требовалось получить в результате решения вспомогательной задачи.
Двойственный симплекс-метод
Метод работает с теми же симплексными таблицами, что и прямой симплекс-метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис [1,3].
Вычислительная схема двойственного симплекс-метода
Шаг 0. Начинаем с симплексной таблицы, где 
.
| B | 
| … | 
| |
| L | 
| 
| … | 
|
| 
| 
| … | 
|
| … | … | ………….. | ||
| 
| 
| … | 
|
Шаг 1. Проверка на оптимальность. Если 
, то решение 
– оптимальное.
Шаг 2. Выбор ведущей строки. Выбираем среди номеров i, для которых 
, номер k с максимальным по модулю значением
.
Строка k объявляется ведущей.
Шаг 3. Проверка на неразрешимость. Если в строке 
нет отрицательных элементов, то двойственная целевая функция неограниченная и, следовательно, прямая задача не имеет допустимых решений. Процесс решения завершается.
|
|
|
Шаг 4. Выбор ведущего столбца s. Выбираем среди отрицательных элементов строки 
элемент с номером s, для которого выполняется равенство
.
Столбец s объявляется ведущим, а элемент 
– ведущим элементом.
Шаг 5. Проводим стандартное преобразование симплексной таблицы (Шаг 6 из прямого симплекс-метода).
Дата добавления: 2021-12-10; просмотров: 13; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!