Методы оптимальных решений (стр. 4 )

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

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

5. В новой таблице, прежде всего, выписываем слева новые базисные неизвестные.

6. Далее в новой таблице заполняем и выделяем ключевую строку. Она получается делением всех элементов соответствующей строки исходной таблицы на ключевой элемент.

7. Остальные элементы новой таблицы подсчитываем по правилу двух перпендикуляров: каждый элемент новой таблицы, за исключением элементов ключевой строки, равен разности между соответствующим элементом исходной таблицы и произведением элементов, оказавшихся в основаниях перпендикуляров, опущенных из “старого” элемента на ключевой столбец и ключевую строку.

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

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

Пример 1. Решить симплекс-методом следующую задачу ЛП:

2x1 + x2 + x4 = 4,

4x1 + x3 + x4 = 12, (7)

xj ³ 0 ( j= 1¸4), (8)

¦(X) = 5 + 4x1 + 2x2 - 3x3 -2x4 - max (9)

Задача является “почти канонической”, так как система уравнений (7) каноническая, а целевая функция (9) выражена не только через свободные неизвестные х1 и х4 но и через базисные неизвестные х2 и x3 поэтому при заполнении исходной симплексной таблицы (табл. 1) индексную строку подсчитаем по правилу цен. С этой целью в верхней части таблицы выпишем все “цены”,то есть коэффициенты при соответствующих неизвестных целевой функции (9), а слева от базисных неизвестных - их “цены”. Тогда нулевой элемент индексной строки будет равен сумме произведений цен слева на свободные члены плюс цена наверху, остальные элементы равны суммам произведений цен слева на элементы соответствующего столбца минус цена наверху. Для индексной строки табл.1 получим

2 × 4 + (-3) × 12 + 5= -23; 2 - 2 + (-3) × 4 - 4= -12; 2 × 1+(-3) × 0 - 2 = 0;

2 × 0 + (-3) × 1 - (-3) = 0; 2 × 1+ (-3) × 4 - (-2) = -8.

			5	4	2	-3	-2
		Баз.	x0	x1	x2	x3	x4
	2	x2	4	2	1	0	1	Табл.1 q = min (4/2,12/4) = 4/2
	-3	x3	12	4	0	1	4
		¦	-23	-12	0	0	-8
®	4	x1	2	1	1/2	0	1/2	Табл. 2 q = min ()
	-3	x3	4	0	-2	1	2
		¦	1	0	6	0	-2
	4	x1	1	1	1	-1/4	0	Табл..3
®	-2	x4	2	0	-1	1/2	1
		¦	5	0	4	1	0

Из табл. 1 можно выписать базисный план Х1 = (0,4, 12,0), для которого значение целевой функции ¦(Х) = -23. В индексной строке табл. 1 есть два отрицательных элемента -12 и -8, над каждым, из которых имеются положительные элементы. Следовательно, план Х1 можно улучшить, построив следующею симплексную таблицу (табл. 2). Мы выбрали -12 и выделили ключевой столбец неизвестного х1 то значит, что неизвестное х1 вводится в базис. Так как ключевое отношение в табл.1 q = min (4/2,12/4) = 4/2