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

Северо-западным углом в таблице является клетка (1,1). Дадим максимальную поставку в эту клетку, равную спросу первого потребителя. Следующей северо-западной клеткой будет клетка (1,2). Дадим в эту клетку груз, оставшийся у первого поставщика (40 единиц). Запасы первого поставщика реализованы. Переходим ко второй строке. Северо-западным углом во 2-й строке является клетка (2,2), в которую нужно поставить груз в 70 единиц, чтобы обеспечить потребность второго потребителя. Из оставшегося груза в количестве 50 ед. у 2-го поставщика поставляем в клетку (2,3) груз в 40 единиц. Оставшиеся 10 ед. поставляем третьему потребителю (в клетку 2,4). Этим самым запасы второго поставщика реализованы. И, наконец, весь груз третьего поставщика поставляем четвёртому потребителю в клетку (3,4)

Все заполнение клетки являются базисными. Их число равно шести, это соответствует рангу системы m + n – 1 = 3 + 4 – 1 = 6. Базисные клетки обозначим диагоналями.

Затраты на перевозку груза в рассматриваемом случае составляет

                       

7.2.2. Метод наименьших затрат

Определим начальное базисное распределение поставок для задачи, определяемой таблицей  поставок (таблица 7.1) при условии, что поставки будут осуществляться с минимумом затрат.

Таблица 7.3.

           Заявки

 Запасы

20

110

40

110

60

1

 2

          60

5

3

120

 1

          20

6

5

 2

         100

100

6

 3

          50

 7

          40

 4

          10

Наименьший коэффициент затрат (1) имеют клетки (1,1) и(2,1). Даём максимально возможную поставку в одну из этих клеток, например, клетку (2,1). Заявка первого потребителя будет удовлетворена. Следующие клетки с минимумом затрат (2) являются клетки (1,2) и (2,4). Даём максимально возможную поставку в клетку (1,2) в объёме 60ед. груза, в клетку (2,4) – 100 ед. груза. В результате этих операций запасы 1-го и 2-го поставщиков будут реализованы.

Остаётся заполнить 3-ю сроку, в которой последовательно заполняем клетки (3,2), (3,4) и (3,3).

Затраты на перевозку груза составят

                       

7.2.3. Особый случай распределения поставок

В случае, когда некоторые из базисных клеток не заполнены, (поставки в эти клетки равны нулю) план называется вырожденным. Рассмотрим на примере, как от вырожденного плана перейти к невырожденному.

Пример 7.2

Дана транспортная таблица (Таблица 7.4)

Таблица 7.4

           Заявки

 Запасы

10

10

20

35

20

20

30

25

20