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

Посчитаем функцию F:

F=

Переход к Шагу 2.

Шаг 2: Построение потенциалов начнем с присвоения любой, например, 2 строке потенциала (U2=10). Это позволит найти через базисную клетку 2,2 V2=U2+c22=10+3=13, через базисную клетку 2,3 потенциал V3=U2+c23=10+5=15, и так далее. Переход у шагу 3.

Ui/Vj

Ресурсы ai

V1=5

V2=13

V3=15

V4=13

V5=13

V6=13

U1=4

а1=150

1

7

11

6

9

9

119

4

20

7

U2=10

а2=170

8

3

5

11

6

8

37

133

U3=5

а3=120

5

4

12

9

8

16

120

U4=9

а4=130

12

8

6

2

5

4

130

U5=12

а5=130

9

10

3

1

12

7

14

116

Потребности bj

700/700

b1=119

b2=37

b3=151

b4=116

b5=140

b6=137

Шаг 3: Проверку плана начнем с первой небазисной клетки 1,2:

V2-U1=13-4=9>7 – нарушение 2

V4-U1=13-4=9>6 – нарушение 3

V1-U2=5-10=-5<8 удовлетворяет условию оптимальности

V1-U3=5-5=0<5 удовлетворяет условию оптимальности

V4-U2=13-10=3<11 удовлетворяет условию оптимальности

V5-U2=13-10=3<6 удовлетворяет условию оптимальности

V6-U2=13-10=3<8 удовлетворяет условию оптимальности

V2-U3=13-5=8>4 – нарушение 4

V3-U3=15-5=10<12 удовлетворяет условию оптимальности

V4-U3=13-5=8<9 удовлетворяет условию оптимальности

V6-U3=13-5=8<16 удовлетворяет условию оптимальности

V1-U4=5-9=-4<12 удовлетворяет условию оптимальности

V2-U4=13-9=4<8 удовлетворяет условию оптимальности

V3-U4=15-9=6=6 удовлетворяет условию оптимальности

V4-U4=13-9=4>2 – нарушение 2

V5-U4=13-9=4<5 удовлетворяет условию оптимальности

V1-U5=5-12=-7<9 удовлетворяет условию оптимальности

V2-U5=13-12=1<10 удовлетворяет условию оптимальности

V5-U5=13-12=1<12 удовлетворяет условию оптимальности

V6-U5=13-12=1<7 удовлетворяет условию оптимальности

Итак мы нашли нарушения условия оптимальности в четырех клетках. Выбираем наибольшее из них. Это клетка 3,2 V2-U3=13-5=8>4 – нарушение 4. следовательно клетка 3,2 войдет в базис задачи – переход у шагу 4.

Шаг 4: Построение замкнутого контура.