Алгоритм симплекс-метода. Симплекс-таблицы

Шаги симплекс-метода принято выполнять с помощью т.н. симплекс таблиц. Рассмотрим их на следующем примере:

x1 -x4 - 2x6 = 5

x2 + 2x4 - 3х5 + x6 = 3

x3 + 2x4 - 5х5 + 6x6 = 5

F = x1 + x2 + x3 +1→ min

В таблицу вносятся коэффициенты при переменных в ограничениях и свободные члены. Коэффициенты целевой функции вносятся (с противоположными знаками) в последнюю строку. Первый столбец содержит обозначения текущих базисных переменных. В правую нижнюю ячейку вносится свободный член целевой функции (со своим знаком!).

Пояснение. Целевая функция записывается также как динейное ограничение на переменные F, x1,…, x6: F - x1 - x2 - x3=1. В этой полной СЛУ F является базисной переменной, но при всех переходах от базиса к базису соответствующий ей столбец не меняется, переменная F остается базисной и потому в таблице не записывается, остается «за кадром».

В исходной форме примера целевая функция содержит базисные переменные. Следует исключить их и выразить функцию только через свободные переменные. Добавим к последней строчке таблицы последовательно первую, вторую и третью (в общем случае умножив предварительно на «подходящее число). Получим: F + 3x4-8x5 + 5x6.= 14.

x1 x2 x3 x4 x5 x6 b

x1 1 0 0 -1 0 -2 5

3/1 x2 0 1 0 2 -3 1 3

5/6 x3 0 0 1 2 -5 6 5

-1 -1 -1 0 0 0 1 (исходная строка для целевой функции)

0 0 0 3 -8 5 14 (б.п. исключены)

В нашем примере система ограничений-равенств уже приведена к базису.

В общем случае единичные базисные столбцы формируются из исходной таблицы методом Гаусса. Однако при этом может получиться недопустимое базисное решение (некоторые базисные переменные могут получить отрицательные значения). Получение исходного допустимого базиса – отдельная задача, обсудим позже.

Для перехода от исходного допустимого базиса к очередному лопустимому и «лучшему» базису необходимо выбрать некоторую «новую» переменную xj, такую, что знак коэффициента при ней в последней строке таблицы положителен (то есть в целевой функции отрицателен). Назовем ее и соответствующий ей столбец разрешающими. Кроме того, необходимо соблюдение двух правил, обеспечивающих допустимость очередного базиса:

1. Разрешающий столбец Aj (вводимый в базис) должен содержать хотя бы один положительный элемент aij > 0.

2. Для всех положительных элементов этого столбца Aj надо подсчитать отношение bi/ aij и выбрать строку i, для которой оно минимально – ведущую строку.

Повторение предыдущей таблицы (для обозримости)

x1 x2 x3 x4 x5 x6 b Базисное решение:

x1 1 0 0 -1 0 -2 5 x1=(5,3,5,0,0,0), F(x1)=14

5/1 x2 0 1 0 2 -3 1 3

5/6 x3 0 0 1 2 -5 6 5

0 0 0 3 -8 5 14

 

Введем в базис переменную х6. Правила 1 и 2 будут соблюдены, если в качестве ведущей выбрать третью строку. При этом из базиса уйдет переменная x3.

x1 x2 x3 x4 x5 x6 b Базисное решение:

x1 1 0 1/3 -1/3 10/6 0 20/3 x2=(20/3,13/6,0,0,5/6), F(x2)=59/6<14

13/10 x2 0 1 -1/6 5/3 -13/6 0 13/6

2 ½ x6 0 0 1/6 1/3 -5/6 1 5/6

0 0 5/6 4/3 -23/6 0 59/6

 

На следующей итерации вводим в базис x4 , выводя из него переменную x2 .

Получим следующую таблицу:

x1 x2 x3 x4 x5 x6 b

x1 1 1/5 3/10 0 -21/10 0 71/10

x4 0 1/5 -1/10 1 23/5 0 13/10

x6 0 -4/5 1/5 0 -2/5 1 2/5

0 -4/5 -11/18 0 -17/18 0 81/10

В этой таблице все коэффициенты последней строки неположительны. Следовательно, дальнейшее улучшение целевой функции невозможно. Итак,

x3=x* = (71/10, 0, 0, 13/10, 0, 2/5) – оптимальное базисное решение, F*=F(x*) = 81/10.

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

Упражнение: Выпишите СЛУ, соответствующую полученному базису.

Замечание 1. Если условие 1 не выполнено (т. е. все коэффициенты при переменной xj, входящей в целевую функцию с положительным коэффициентом, неположительны), то задача ЛП неограничена, решения нет.

Замечание 2. Если минимальное из отношений bi/aij равно нулю, новая базисная переменная в очередном базисном решении равна 0, улучшения функции на данном шаге не происходит. Но происходит переход к новому базису. В принципе возможен эффект зацикливания, когда после нескольких таких шагов (без улучшения значения функции) происходит возврат к уже пройденному базисному решению. В линейном программировании, к счастью, разработаны процедуры (антициклины) предотвращающие такой эффект, и они заложены в программные реализации симплекс-метода.









Дата добавления: 2016-03-27; просмотров: 798;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

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

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.01 сек.