Экономика и менеджмент \ Модели и моделирование на транспорте

Постановка транспортной задачи в матричной форме. Симплекс метод решения задачи линейного программирования, страница 12

Шаг 4. Выполняется проверка решения на оптимальность. Для задач на max целевой функции должно выполняться условие:

Если условие оптимальности не выполняется, переход к шагу 5; иначе получен оптимальный и допустимый план.

c_i	p_i,	x_i	10	8	9	12	0	0	0	1	1
c_i	p_i,	x_i	X1	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
0	x₅	740	4	2	0	1	1	0	0	0	0
0	x₆	760	2	0	2	1	0	1	0	0	0
0	x₇	770	2	2	2	0	0	0	1	0	0
0	X₈	800	2	2	1	1	0	0	0	1	0
0	X₉	700	0	2	2	2	0	0	0	0	1
z_j-c_j		F=0	-10!	-8!	-9!	-12!	0	0	0	0	0

Шаг 5. Выбор ключевого столбца. Из показателей индексной строки выбирается значение с наибольшим отклонением от условия оптимальности. Соответствующая переменная на следующей итерации входит в базис задачи. Выбор ключевой строки. Находится минимальное отношение показателей столбцов x_iи a_ij при условии , что a_ij>=0

c_i	p_i,	x_i	10	8	9	12	0	0	0	1	1
c_i	p_i,	x_i	X1	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
0	x₅	740	4	2	0	1	1	0	0	0	0
0	x₆	760	2	0	2	1	0	1	0	0	0
0	x₇	770	2	2	2	0	0	0	1	0	0
0	X₈	800	2	2	1	1	0	0	0	1	0
0	X₉	700	0	2	2	2	0	0	0	0	1
z_j-c_j		F=0	-10	-8	-9	-12	0	0	0	0	0

По данным индексной строки выбираем показатель z₉-c₉=-12, как имеющий наибольшее отклонение от условия оптимальности. Это ключевой столбец. Соответствующая переменная, x₄, на следующей итерации войдет в базис задачи.

Выбираем ключевую строку из отношения Мин {x_i/a_i}={740/1,760/1,770/1,800/1,700/2}=700/2. Следовательно строка с переменной x₉ является ключевой. Клетка на пересечении ключевой строки x₉и ключевого столбца x₄ называется ключевой. Её значение равно 2. теперь необходимо ввести переменную x₄ в базис задачи и вывести переменную x_9.Переход к шагу 6.