Тема 2.8 Решение задачи линейного программирования

с использованием симплекс-таблиц

Приводим систему ограничений задачи ЛП к виду:

где – положительные числа. Целевую функцию записываем в виде:

Из коэффициентов системы уравнений и коэффициентов целевой функции составляем первую симплекс-таблицу (таблица 2.2).

Таблица 2.2

Б.п		…		…			…		…		С.к
		…		…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
		…		…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
		…		…			…		…
		…		…			…		…

Числа ,,...,,...,называются индексами; последняя строка таблицы называется индексной.

Полагая переменные (свободные) , ...,x_n равными нулю, получим первое базисное решение (a , a ,…, a 0...,0) и первое значение f целевой функции, соответствующее этому решению. Первый базисный план и первое значение целевой функции образуют последний правый столбец таблицы 2.2. В верхней нулевой строке таблицы 2.2 записаны все переменные задачи ЛП, в левом нулевом столбце записаны базисные переменные. Будем рассматривать задачу на максимум функции f.

Переход ко второй симплекс-таблице осуществляется следующим образом: выбираем j -й столбец (разрешающий) таблицы 2.2 из условия, что является наибольшим по модулю отрицательным индексом и хотя бы один из элементов a >0;

выбираем i -ю строку (разрешающую) из условия, что:

a / a =для a >0,

принимая a в качестве разрешающего элемента, производим преобразование коэффициентов таблицы

(в том числе элементов индексной строки) так, как это делается при решении системы уравнений методом Жордана-Гаусса:

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

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

Если в очередной симплекс-таблице:

1) найдется хотя бы один отрицательный индекс и в каждом столбце с отрицательным индексом окажется хотя бы один положительный элемент, то план можно улучшить, перейдя к следующей симплекс-таблице;

2) найдется хотя бы один отрицательный индекс и все элементы в столбце, содержащем этот индекс отрицательные, то

fmax =+

3) нет ни одного отрицательного индекса, то достигнут оптимальный план.

Пример. Найти наибольшее значение функции

f = 5 x + 2 x , если x , x неотрицательные и удовлетворяют системе неравенств:

Решение. Вводим балансовые переменные х₃, x , x и получаем систему уравнений:

Целевую функцию представим в форме:

f = 0 - (-5x - 2х ). Составляем первую симплекс-таблицу 2.3:

Таблица 2.3

Б.п.						с.к.
	-2
		-1
f	-5	-2

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

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

где

i = 3, j =1, k 3, p 1.

Формулу эту называют «правилом прямоугольника», ибо ее легко запомнить, пользуясь прямоугольником:

Правило для запоминания формулы: для получения новой вершины а 'прямоугольника надо из старой вершины а вычесть произведение a а двух взаимно противоположных других вершин прямоугольника, деленное на вершину a , противоположную старой вершине а .

В результате получаем следующую таблицу 2.4:

Таблица 2.4

Б.п	х1	х2	х3	х4	х5	С.к
х3					–5
х4
х1		–1
f		–7

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

Так как min , то первая строка будет разрешающей.

Переменную х ₂ вводим в состав базисных вместо х₃. Элементы первой строки делим на разрешающий элемент а₁₂ = 7. Элементы второго столбца, кроме а₁₂, заменяем нулями. Все остальные элементы таблицы 3 преобразуем по «правилу прямоугольника». Получим в результате таблицу 2.5.

Таблица 2.5

Б.п.	х1	х2	х3	х4	х5	С.к.
х 2			1/7		-5/7	5/7
			-1/7		19/7	51/7
			1/7		2/7	12/7
f

Так как в последней строке таблицы 5 нет отрицательных индексов, то f⁼ 10 и (12/7; 5/7) – оптимальный план.

Дата добавления: 2014-10-31