Лекции.Орг


Поиск:




Пример решения задачи в специальной форме




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

 

Решить задачу, записанную в виде:

Составим симплексную таблицу:

 
L      
     
   

 

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базиса L=0.

Выбираем ведущий столбец – это столбец, соответствующий переменной . Выбираем ведущую строку. Для этого находим . Следовательно, ведущая строка соответствует переменной .

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

 

 
L -2   -2
  -1
   

 

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисе
L= -2.

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

 

 
L -4/3 -2/3
4/3 2/3 -2/3
5/4 1/3 2/3

 

Еще одна итерация завершена. Переходим к новой итерации.

Строка целевой функции не содержит положительных значений, значит, соответствующее базисное решение

,

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

 

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

Базиса

 

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

 

 

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

 

 

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

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

 

Полученная вспомогательная задача имеет вид

Приведем задачу к виду (16):

Выпишем соответствующую симплексную таблицу:

 

  B
      -1
    -2  
      -1
       

 

Ведущий столбец рекомендуется выбирать не по максимальному положительному элементу строки целевой функции, а так, чтобы из базиса выводилась искусственная базисная переменная (соответствующая ведущая строка должна быть строкой искусственной переменной). Так, выбрав ведущим столбцом столбец переменной , получим ведущую строку – строку с переменной z (выбирая ведущим столбцом , получили бы ведущую строку и из базиса выводилась бы переменная ).

Итак, искусственная переменная z выйдет из базиса, а переменная введется в базис.

Симплексная таблица преобразуется к виду

 

  B
    -1  
  11/2 1/2 -1/2
5/2 5/4 1/4 -1/4
5/2 3/4 -1/4 1/4

 

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

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

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

 





Поделиться с друзьями:


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


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

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

Жизнь - это то, что с тобой происходит, пока ты строишь планы. © Джон Леннон
==> читать все изречения...

840 - | 710 -


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

Ген: 0.01 с.