Алгоритм симплекс-метода
Date: 2015-10-07; view: 533.
Решение задачи ЛП симплекс-методом можно разбить на 3 шага.
1. Выбор начального базисного плана.
2. Проверка его на оптимальность. Если план оптимальный — задача решена. В противном случае —
3. Переход к новому базису.
Повторяя действия со второго шага, за конечное число шагов мы либо придем к оптимальному решению, либо убедимся в его отсутствии. Это означает конечность процедуры симплекс-метода.
I шаг. Выбор начального плана.
Пусть задача ЛП задана в канонической форме. Т.е. система ограничений состоит только из уравнений, правые части которых неотрицательны (т.е. 
); и в каждом из них есть базисная переменная, т.е. переменная, которая с коэффициентом +1 содержится в одном уравнении и отсутствует во всех остальных; функция цели максимизируется.
Эти базисные переменные канонической задачи составят естественный начальный базисный план Х1 при 
. Таким образом, начальный план задачи (1) содержится во втором столбце первой симплекс-таблицы (табл.1.), 
.
II шаг. Проверка плана на оптимальность.
Проверка плана на оптимальность заключается в анализе коэффициентов индексной строки (кроме d0). Возможны 3 случая:
1. Все элементы индексной строки неотрицательны. Тогда записанный в этой таблице план Х1 является оптимальным, 
= d0 (см. табл. 1).
2. Среди элементов индексной строки есть отрицательные, но в столбце над ними нет ни одного положительного элемента. В этом случае целевая функция F не ограничена сверху на области планов и оптимального решения задачи не существует.
3. Среди элементов индексной строки есть отрицательные, и в столбцах над ними есть хотя бы один положительный элемент. Это означает, что целевая функция на плане Х1 не достигла максимального значения и план может быть улучшен. Переходим к III шагу.
III шаг. Построение нового плана.
Каждый новый план отличается от предыдущего одной из базисных переменных. Переход к новому плану осуществляется преобразованиями Жордана-Гаусса, на каждом шаге которых один из базисных столбцов выводится из базиса и заменяется другим, небазисным. Алгоритм перехода к новому плану заключается в следующем.
1. Среди отрицательных элементов индексной строки выбираем наибольший по абсолютной величине (если таких несколько, можно взять любой из них). Соответствующий ему столбец называется ключевым столбцом, выделяем его. Переменная, соответствующая ключевому столбцу, войдет в новый базис, т.к. ключевой столбец переходит в число базисных.
2. Среди элементов ключевого столбца находим ключевой элемент. Для этого составляем отношения свободных членов к положительным элементам ключевого столбца; среди всех отношений выбираем минимальное. Знаменатель этого минимального отношения принимаем за ключевой элемент. Содержащая ключевой элемент строка соответствует переменной, которая выводится из базиса.
3. Все элементы строки, в которой находится ключевой элемент, делятся на значение ключевого элемента. Полученная строка называется ключевой строкой и записывается в новую таблицу на соответствующее место. Ключевую строку выделяем.
4. Остальные элементы новой таблицы (включая элементы индексной строки) находятся по правилу двух перпендикуляров: «прежнее значение элемента минус произведение чисел, стоящих на концах перпендикуляров, опущенных из этого элемента на ключевой столбец и ключевую строку».
Поясним сказанное на примере задачи (1).
Пусть в табл.1. отрицательный элемент d2<0 индексной строки соответствует столбцу х2. Тогда столбец х2 является ключевым и пусть элемент a22 — ключевой элемент, выделим их. Переменная х4 выходит их базиса, ее место займет переменная х2. Вторая строка плана 
будет ключевой, вычислим ее элементы и выделим.
Остальные элементы пересчитываются по правилу двух перпендикуляров, их значения приведены в таблице 2. Отметим, что элементы новой таблицы под ключевым столбцом равны 0, за исключением элемента в ключевой строке, который всегда равен 1, поскольку ключевой столбец становится базисным.
Таблица 2.
| баз. | своб. | х1 | х2 | х3 | х4 |
| х3 | b1 | a11 | a12 | ||
| х4 | b2 | a21 | a22 | ||
| d0 | d1 | d2 | ||
| х3 | b1- a12  
| A11- a12 
| - a12 
| ||
| х2 |
|
|
| ||
|
| d0–d2 
| d1–d2
| –d2
|
В первую очередь целесообразно пересчитывать индексную строку, т.к. в случае оптимальности плана достаточно ограничиться вычислением элементов только второго столбца.
Пример 1. Составить математическую модель и найти решение следующей задачи.
Предприятие выпускает продукцию двух видов — I и II, используя для этого два вида сырья — S1 и S2. Количество сырья, необходимое для выпуска единицы продукции, запасы сырья и прибыль от продажи единицы продукции заданы в таблице. Необходимо составить план производства, при котором прибыль от продажи будет максимальной, при условии, что продукции II вида можно произвести не более 6 единиц.
| Сырье | Расход сырья на ед. прод. вида | Запасы сырья | |
| I | II | ||
| S1 | |||
| S2 | |||
| Прибыль от продажи ед.прод. |
Обозначим количество выпускаемой продукции I и II вида через х1 и х2 соответственно.
Первые два неравенства выражают ограничение объемов выпуска продукции наличными запасами сырья S1 и S2, третье неравенство соответствует ограничению количества продукции II вида. Функция цели — суммарная выручка от продажи продукции —максимизируется. Задача содержит две переменные и может быть решена графически, однако разберем на данном примере решение симплекс –методом.
Запишем задачу в каноническом виде. Правые части ограничений неотрицательны, знаки неравенств типа « 
», поэтому вводим в левые части неравенств дополнительные неотрицательные переменные со знаком «+» и получаем систему уравнений, в каждом из которых есть базисная переменная. 
, задача записана в каноническом виде.
Внесем данные в симплекс-таблицу (табл.3).
Таблица 3.
| баз. | св. | 
| 
| 
| 
| 
| ||
|
| ||||||||
|
| ||||||||
|
|  0
| |||||||
| -1 | -2 | План X1 | |||||
|
| -1 | |||||||
| х2 | 14/4 | 1/4 | 1/4 | |||||
|
| 5/2 | -1/4 | -1/4 | |||||
| F | -1/2 | 1/2 | План X2 | |||||
| х1 | 1/2 | -1/2 | ||||||
| х2 | ||||||||
|
| ||||||||
| F | 1/4 | 1/4 | План X3 |
Базисными переменными в первом уравнении является переменная х3 , во втором уравнении — переменная х4, в третьем — переменная х5.
Для вычисления элементов индексной строки припишем слева и сверху таблицы коэффициенты при соответствующих переменных целевой функции: коэффициент при х1 равен 1, при х2 равен 2, остальные переменные не содержатся в целевой функции, следовательно, коэффициенты при них равны 0. Найдем элементы индексной строки по формулам (2).
Поскольку в индексной строке есть отрицательные элементы (d0 не рассматриваем), план X1 не оптимален, следовательно, необходим переход к новому базису.
Наибольшим по модулю среди отрицательных элементов индексной строки является элемент –2, записанный в столбце . Это ключевой столбец, выделяем его. Ключевой столбец указывает переменную, вводимую в новый базис.
Найдем ключевой элемент. Для этого определим минимальное среди отношений свободных коэффициентов системы к положительным элементам ключевого столбца, 
. Знаменатель этого отношения есть ключевой элемент. Он находится во второй строке, которая становится ключевой, и указывает переменную, выходящую из базиса. Элементы ключевой строки плана X2 получаются делением всех элементов второй строки плана X1 на ключевой элемент, равный 4; в новой таблице второй строке соответствует переменная .
Остальные элементы нового плана X2 находятся по правилу двух перпендикуляров. Заполнение новой таблицы рациональнее начинать с индексной строки, поскольку если все ее элементы окажутся неотрицательными, то план оптимален, и для остальных переменных достаточно будет вычислить лишь значения столбца свободных членов.
Индексная строка: 
; 
; 0 (т.к. соответствует базисному столбцу); 
; 
; . План не оптимален, считаем дальше.
Строка : 
; 
;0 (т.к. соответствует базисному столбцу); 
; 
; 
.
Строка : 
; 
; 0 (т.к. соответствует базисному столбцу); 
; ; 
.
В таблице получены план X2 и целевая функция . План X2 может быть улучшен, т.к. в индексной строке есть отрицательный элемент –1/2. Он находится в первом столбце, следовательно, это новый ключевой столбец. Переменная входит в базис нового плана. Считаем отношения свободных членов к положительным элементам ключевого столбца и выбираем наименьшее: 
, знаменатель этой дроби определяет ключевой элемент, равный 2. Он стоит в первой строке, следовательно, эта строка становится ключевой, переменная выходит из базиса. Ключевая строка плана X3 получается делением всех элементов первой строки плана X2 на ключевой элемент, равный 2.
Индексная строка: 
; 0; 
; 
; 
; . Поскольку в индексной строке нет отрицательных элементов, план X3 оптимален и для него достаточно вычислить только значения базисных переменных.
По правилу двух перпендикуляров:
, 
.
В плане X3 базисными переменными являются х1, х2, , остальные переменные — свободные, в базисном плане их полагают равными 0.
Выписываем оптимальный план задачи:
, 
.
Исходная задача содержала только две переменных, следовательно, окончательно, X*(x1,x2)=(2;3). Отброшенная переменная означает «резерв» выпуска изделий II вида.
Предлагаем самостоятельно решить эту задачу графически и проверить себя по известному уже ответу.
Пример 2. Решить задачу ЛП:
Это общая задача, правые части ограничений неотрицательны. Сведем задачу к основной.
Первое ограничение уже дано в виде уравнения, в левую часть второго ограничения-неравенства для записи его в виде уравнения введем дополнительную переменную . В первом уравнении базисной переменной является х3, во втором — переменная х4. В исходной задаче целевая функция минимизируется. Поэтому введем функцию 
, для которой будем искать максимум: 
.
Получаем каноническую задачу:
Внесем условия в симплекс-таблицу (табл.4). Базисными являются переменные и .
Для заполнения индексной строки слева и сверху таблицы выпишем коэффициенты при переменных, входящих в целевую функцию, по формулам (2) вычислим элементы индексной строки:
Таблица 4.
| -1 | -1 | |||||||||||||
| Баз. | св. |
|
|
|
| |||||||||
| -1 |
| |||||||||||||
|
| 5
| -2 | ||||||||||||
| W | -8 | -5 | -2 | |||||||||||
|
| 38/5 | 19/5 | -2/5 | |||||||||||
| х1 | 1/5 | -2/5 | 1/5 | |||||||||||
| W | -7 | -4 | ||||||||||||
| х2 | 5/19 | -2/19 | ||||||||||||
|
| ||||||||||||||
| W | 20/19 | 11/19 | ||||||||||||
Начальный план 
не оптимален, т.к. среди элементов индексной строки есть отрицательные. Среди них наибольшим по модулю является элемент –5. Он стоит в столбце , следовательно, это ключевой столбец, переменная войдет в базис плана . Ключевой элемент равен знаменателю минимального из отношений: 
, т.е. 5. Ключевой элемент находится во второй строке. Следовательно, переменная уходит из базиса. Делим все элементы второй строки на 5 и получаем ключевую строку плана X2 .
Остальные элементы плана X2 находим по правилу двух перпендикуляров.
Индексная строка: 
; 0; 
; 0; 
. План X2 не оптимален, т.к. есть отрицательный элемент d2 = –4.
Строка : 
; 0; 
; 
; 
.
Отрицательный элемент d2 = –4 индексной строки находится в столбце , следовательно, это ключевой столбец. Переменная войдет в базис нового плана. Из элементов ключевого столбца положителен только элемент, стоящий в первой строке и равный 
, он и будет ключевым, переменная выходит из базиса.
Разделим первую строку плана X2 на и получим ключевую строку плана X3. Вычислим элементы индексной строки: 
; 
; 0; 
, 
. Поскольку в индексной строке нет отрицательных элементов, план X3 оптимален и для него достаточно вычислить только значения базисных переменных.
По правилу двух перпендикуляров: 
.
В последней симплекс-таблице (табл.4) находится оптимальный план 
и 
. Исходная задача содержала две переменные, поэтому отбросим значения дополнительных переменных: 
, 
–W(X*)=–1.
Окончательный ответ: , –1.
| <== previous lecture | | | next lecture ==> |
| Составление симплекс-таблицы | | | С искусственным базисом М-методом |