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

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

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

ci

pi,

xi

10

8

9

12

0

0

0

1

1

X1

X2

X3

X4

X5

X6

X7

X8

X9

0

x5

740

4

2

0

1

1

0

0

0

0

0

x6

760

2

0

2

1

0

1

0

0

0

0

x7

770

2

2

2

0

0

0

1

0

0

0

X8

800

2

2

1

1

0

0

0

1

0

0

X9

700

0

2

2

2

0

0

0

0

1

zj-cj

F=0

-10!

-8! 

-9!

-12! 

0

0

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

ci

pi,

xi

10

8

9

12

0

0

0

1

1

X1

X2

X3

X4

X5

X6

X7

X8

X9

0

x5

740

4

2

0

1

1

0

0

0

0

0

x6

760

2

0

2

1

0

1

0

0

0

0

x7

770

2

2

2

0

0

0

1

0

0

0

X8

800

2

2

1

1

0

0

0

1

0

0

X9

700

0

2

2

2

0

0

0

0

1

zj-cj

F=0

-10

-8

-9

-12

0

0

0

0

0

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

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

Шаг 6. Выполняются симплекс- преобразования:

- значение элемента в новом базисе

- значение элемента ключевой строки в новом базисе

- значение элемента в текущем базисе

- значение элемента ключевой строки в текущем базисе

- значение элемента ключевого столбца в текущем базисе

- значение ключевого элемента в текущем базисе