Линейное математическое программирование, страница 27

Применяя метод “северо-западного” угла, получим таблицу 7.5.

Таблица 7.3

           Заявки

 Запасы

10

10

20

35

20

20

10

10

30

20

10

25

25

20

20

Ранг системы m+n–1 = 4 + 5 – 1 = 8, заполненных клеток – 6, а должно быть 8. Чтобы ввести две недостающие базисные переменные изменим ничтожно мало запасы в первой строке и положим их равными 20+ε. Кроме того, в третьей строке положим запасы, равные 25+Е

Таблица 7.6

           Заявки

 Запасы

10

10

20

35

20

20+Е

10

10

Е

30

20-Е

10+Е

25+Е

25-Е

20-2Е

20-2Е

Эта таблица содержит столько базисных переменных, сколько требуется –8. После того как план будет минимизирован Е полагается равным нулю.

            7.3. Критерий оптимальности базисного распределения поставок

            Транспортная задача – задача на минимум. При поиске минимального значения целевой функции критерием ее оптимальности является неотрицательность всех коэффициентов при свободных переменных в функции цели.

            Запишем функцию цели в виде

                                   ,

где F0 – суммарные затраты на перевозку данного распределения поставок,

      βij – коэффициент при xij свободной переменной,

xij – свободная переменная, которая в транспортной задаче отождествляется с пустой (i,j)-той клеткой,