Сделай Сам Свою Работу на 5

Метод искусственного базиса





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

За счет чего мы так легко составили исходную симплекс-таблицу в предыдущем примере? Легко видеть, что это произошло потому, что среди

векторов были векторы вида

,

так как искать координаты в этом базисе очень просто.

На искусственном введении этих векторов и основан метод искусственного базиса.

Итак, пусть мы имеем задачу линейного программирования в канонической форме

.

Можно считать, что все , так как умножением соответствующего
ограничения на -1 у всегда можно сменить знак.

Возьмем ну очень большое число M и будем решать следующую вспомогательную задачу:

В этой задаче сразу ясен исходный базис - в качестве него надо взять

векторы, стоящие при , ведь они имеют вид

В качестве исходного опорного плана надо взять план

Коэффициенты разложения векторов . Исходная симплекс-таблица приобретает тогда вид:


Надо лишь сосчитать дополнительную строку, где стоят числаи :

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



,

где - единичная матрица размерности , а .

А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса векторы, соответствующие введенным дополнительным переменным. Так как M очень большое, то среди разностей будет много положительных и будет много претендентов на введение в базис из

векторов .  

Заметим, что если какой-то вектор, соответствующий какой-то дополнительной переменной выведен из базиса, то соответствующий столбец симплекс-таблицы можно просто вычеркнуть и больше к нему не возвращаться.

В конце концов возможны два варианта.

 

Вариант 1

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

Вариант 2

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



Заметим в заключение, что величина M вообще не конкретизируется и так и остается в виде буквы M. При решении учебных задач в дополнительную строку пишут алгебраические выражения, содержащие M, а при счете на ЭВМ вводится еще одна дополнительная строка, куда пишутся коэффициенты при M.

Проиллюстрируем это примером.

Пример

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

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

Исходная симплекс-таблица примет тогда вид:

 

  Ба- с План -1 -2 -3 М М
  зис    
  M
M
 
      10+ 35M 2+ 3M 4+ 3M 4+ 8M
                 

Дальнейшие итерации приводятся без особых пояснений.

Первая итерация

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

  Ба- с План -1 -2 -3 М
  зис    
M
  -3
 
      -6+ 3M 2/5- -1/5M 16/5+ +1/5M
               

Вторая итерация



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

  Ба- с План -1 -2 -3
  зис    
  -2
  -3
 
   
             

Третья итерация

Мы вернулись к исходной задаче и продолжаем решать ее по стандартной схеме.

Ба- с План -1 -2 -3
зис    
-2
-3
-1
    -15 -1

Таким образом, задача решилась и оптимальный план имеет вид:

.

Минимальное значение целевой функции равно - 15.

Отметим в заключение, что если первоначальная задача линейного программирования имела ограничения вида и все компоненты вектора неотрицательны, то, приводя её к канонической форме, мы сразу будем иметь единичную матрицу порядка m которую и можно брать в качестве исходного базиса

Двойственные задачи

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.