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

Симплексный метод решения задач линейного программирования

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

Этот метод включает в себя три основные этапа:

1. Построение начального опорного плана.
2. Правило перехода к лучшему (точнее, нехудшему) решению.
3. Критерий проверки найденного решения на оптимальность.

1) Построение начального опорного плана.

Данную задачу линейного программирования необходимо сначала привести к каноническому виду; при этом правые части ограничений должны быть неотрицательными. Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной. Базисной называют плановую переменную, которая входит только в одно уравнение (а в другие не входит), и при этом имеет коэффициент, равный единице. Пусть задача линейного программирования приведена к каноническому виду, и все уравнения системы ограничений имеют свою базисную переменную. Приравняв базисные переменные к соответствующим правым частям ограничений, а остальные переменные к нулю, получим опорное или базисное решение задачи. Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение). max Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой: В каждом ограничении слева добавим положительную переменную , соответственно запишем канонический вид задачи: max . Переменные базисные. Приравниваем их к правым частям ограничений:Все остальные переменные – свободные, приравниваем их к нулю: Запишем теперь начальный опорный план (0; 0; 0; 0; 16; 4; 0).

2) Составление симплексных таблиц. Критерий оптимальности.

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

Базис		В			…
					…
					…
					…
…	…	…	…	…	…	…
					…
					…

Здесь приняты следующие обозначения. Столбец «Базис» – это базисные переменные. Столбец «» – это коэффициенты при базисных переменных в целевой функции. Столбец «В» – правые части ограничений; –коэффициенты при переменных в ограничениях; –коэффициенты при переменных в целевой функции. Последняя строка в таблице () – это проверочная или оценочная строка. –значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца умножают на соответствующий элемент столбца В и произведения складывают, т.е. . –называют оценками или симплексными разностями и находят так: элементы столбца умножают на соответствующие элементы столбца, складывают результаты и вычитают. Например, . Оценки () базисных переменных всегда равны нулю. Признак оптимальности опорного плана состоит в следующем: Опорный план будет оптимальным тогда и только тогда, когда все оценки для задачи на max и для задачи на min. Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных. Переменная, которую нужно ввести в базис, соответствует той оценке , которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называютразрешающим. Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения . Выбирают изнаименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называетсяразрешающей. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере. Пример. Решить симплексным методом задачу линейного программирования. max Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства. max 2) Определяем базисные переменные – это . 3) Заполняем первую таблицу

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0
	0	16	2	1	0	1	0	0
	0	5	0	1	0	0	1	0
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0

Здесь ине удовлетворяют условию оптимальности, т. к. они меньше нуля. Выбираем среди них большее по модулю. Это. Следовательно, столбец переменной– разрешающий. Значит, в новый базис нужно ввести переменную. Находим :;; Наименьшее из этих чисел – это число 5, что соответствует строке базисной переменной . Значит, строка базисной переменной– разрешающая, следовательно, из базиса нужно вывести переменную. Элемент=1 – разрешающий. Новый базис:. Заполнение следующей таблицы начинаем со столбцов «Базис» и «». Потом заполняем разрешающую строку, разделив каждый ее элемент на разрешающий, т.е. на 1. Все элементы разрешающего столбца будут нулями, кроме разрешающего, который всегда равен 1. Столбцы подпереписываем без изменения, т. к. эти переменные остались в базисе. Остальные элементы новой таблицы находим по правилу прямоугольника. Например, элементнайдем из прямоугольника = Или элемент =из прямоугольника Оценки для новой таблицы можно находить по этому же правилу. Вцелом, решение данной задачи симплексным методом в виде таблиц будет иметь вид

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0	6
	0	16	2	1	0	1	0	0	16
	0	5	0	1	0	0	1	0	5
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0	таб. 1
	0	3	1	0	1	0	–3	0	3
	0	11	2	0	0	1	–1	0	5,5
	3	5	0	1	0	0	1	0	–
	0	21	3	0	0	0	0	1	7
		15	–2	0	0	0	3	0	таб. 2

Базис		В	2	3	0	0	0	0
	2	3	1	0	1	0	–3	0	–
	0	5	0	0	–2	1	5	0	1
	3	5	0	1	0	0	1	0	5
	0	12	0	0	–3	0	9	1
		21	0	0	2	0	–3	0	таб. 3
	2	6	1	0	–0,2	0,6	0	0
	0	1	0	0	–0,4	0,2	1	0
	3	4	0	1	0,4	–0,2	0	0
	0	3	0	0	0,6	–1,8	0	1
		24	0	0	0,8	0,6	0	0	таб. 4

Оценочная строка четвертой таблицы показывает, что получен оптимальный план, так как все. –это значения из столбца В, т.е.,,,. Свободные (небазисные) переменные . Итак, = (6; 4; 0; 0; 1; 3), = = 24. Примечание: При переходе от таблицы к таблице для контроля сравнивают , которое должно быть не меньше предыдущего для задачи на максимум и не больше предыдущего – для задачи на минимум. При использовании симплексного метода возможны следующие случаи. 1) Если в оценочной строке симплекс-таблицы оценка = 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план. 2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует. Задания для самостоятельной работы. Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:

а)

max

б)

min

Источник

2.3. Признак оптимальности опорного плана

Теорема 1. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой планоптимален.

Теорема 2.Если исходная задача решается на минимум и для некоторого опорного плана все оценки неположительны, то такой планоптимален.

2.4. Переход к нехудшему опорному плану

Рассмотрим ЗЛП на максимум.Приведем ее к каноническому виду и занесем в симплексную таблицу.

Если все _j0, то начальный опорный планx₀оптимален.

С этой целью выбирают разрешающий элемент.

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

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

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

Выбор разрешающей строки. Находят отношения . Они называютсясимплексными.

Среди симплексных отношений определяют наименьшее, т. е.

.

Если это условие выполняется при нескольких i, то в качествеi₀можно выбрать любое.

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

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

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

Замечание.Поскольку minz= –max (–z), задачу минимизации можно формально заменить задачей максимизации функции –z. Затем полученный максимум следует взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

2.5. Симплексные преобразования

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

1. элементы строкиi₀новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разрешающий элемент.

2. все элементы столбцаj₀новой таблицы равны нулю, за исключением .

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

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

.

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

Источник

2.6. Признак оптимальности опорного плана. Симплексные таблицы

Для того, чтобы было удобнее решать ЗЛП симплексным методом были придуманы симплексные таблицы, которые позволяют максимально алгоритмизировать процесс решения задачи линейного программирования. Симплексная таблица составляется только в том случае, если составлен начальный опорный план.

Пусть ЗЛП представлена в каноническом виде:

при

С помощью метода Гаусса (см. 1.12) преобразуем систему ограничений и приведем ее к следующему виду:

(i=)

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

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

В первом столбце (БП) пишутся базисные переменные. Все базисные переменные пишутся В СООТВЕТСТВИИ С УРАВНЕНИЯМИ, ДЛЯ КОТОРЫХ ДАННЫЕ ПЕРЕМЕННЫЕ ЯВЛЯЮТСЯ ПРЕДПОЧТИТЕЛЬНЫМИ.

Во втором столбце (СБ) пишутся коэффициенты для соответственных базисных переменных в целевой функции.

В третьем столбце (А) пишутся свободные члены в уравнениях системы ограничений.

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

В таблице со второй строки четвертого столбца пишутся все коэффициенты соответственных переменных в системе ограничений.

В последней строке пишутся оценки. Оценки считаются по формулам (см. 1.12):

Оценки для базисных переменных равны 0.

Замечание: Оценки считаются как скалярное произведение соответственного столбца на столбец СБ минус коэффициент в целевой функции для данной переменной.

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

Теорема 1: (признак оптимальности опорного плана при решении задач на максимум) Пусть исходная ЗЛП решается на максимум. Если для некоторого опорного плана в индексной строке симплексной таблицы все оценки () неотрицательны, то такой план будет оптимальным.

Теорема 2: (признак оптимальности опорного плана при решении задач на минимум) Пусть исходная ЗЛП решается на минимум. Если для некоторого опорного плана в индексной строке симплексной таблицы все оценки () неположительны, то такой план будет оптимальным.

Пример 1: Составить симплексную таблицу и посчитать оценки для задачи линейного программирования вида:

Построение начального опорного плана рассмотрено в 2.5.

Базис системы составляют переменные: , , , (представлены в соответствии с уравнениями, предпочтительными переменными которых являются данные переменные).

Источник