Лекции.Орг


Поиск:




Пример решения задачи методом искусственного

  базиса

 

Выделить допустимое базисное решение для задачи ЛП.

 

 

Приведем задачу к канонической форме на минимум с неотрицательными правыми частями.

 

 

Заметим, что переменные  и  можно использовать для введения в исходный базис, поэтому в первую и третью строку ограничений можно не вводить искусственные переменные.

Во вторую строку ограничений вводим искусственную переменную 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

 

Так как значение , то полученный базис  является начальным допустимым базисом для исходной задачи ЛП. Чтобы выразить целевую функцию  через небазисные переменные , подставим значение базисной переменной  в целевую функцию. В результате получим

Тогда исходная задача будет иметь вид специальной формы задачи ЛП:

что и требовалось получить в результате решения вспомогательной задачи.

 

Пример решения задачи двойственным

  симплекс-методом

 

Решить задачу ЛП двойственным симплекс-методом.

Приводим задачу к каноническому виду:

Знаки в ограничениях заменили противоположными для того, чтобы переменные  и  можно было взять в качестве базисных. Симплексная таблица имеет вид

 

  b
L 0 -1 -1 0
-2 -1 1 -1
-1 -2 -1 1

 

Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку – это строка переменной , ведущий столбец – это столбец переменной . После преобразования таблица принимает вид

 

  b
L 0 -1 -1 0
2 1 -1 -1
-3 -3 0 1

 

Так как в столбце b есть отрицательная переменная , то эту строку выбираем ведущей, а столбец переменной  будет ведущим столбцом. После преобразования получаем таблицу:

 

  b
L 1 -1/3 -1 -1/3
1 1/3 -1 -2/3
1 -1/3 0 -1/3

 

которая является оптимальной. Соответствующее оптимальное решение имеет вид .



<== предыдущая лекция | следующая лекция ==>
Пример графического решения задачи ЛП | Пример построения двойственной задачи
Поделиться с друзьями:


Дата добавления: 2018-10-14; Мы поможем в написании ваших работ!; просмотров: 198 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Неосмысленная жизнь не стоит того, чтобы жить. © Сократ
==> читать все изречения...

770 - | 680 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.013 с.