1.2. Методы получения начального базисного распределения поставок (первоначального опорного плана)

Для решения транспортной задачи в настоящее время используются три метода получения первоначального опорного плана:

- метод северо-западного угла;

- метод наименьших затрат (метод минимального элемента);

- метод аппроксимации Фогеля

Начнем рассмотрение этих методов с метода северо-западного угла.

1.2.1 Получение начального базисного распределения поставок методом «северо-запад­ного» угла.

Существо метода покажем на конкретном примере.

Задача 13.2. Получить методом северо-западного угла первоначальное базисное распределение поставок для транспортной задачи 13.1.

Р е ш е н и е.

Если наложить таблицу 13.1 на карту, то клетка (1.1) таблицы окажется в северо-западном углу. Распределение поставок начинают именно с этой клетки (отсюда и название метода).

Предположим, что поставщик 1, обладающий мощностью доставки 60 единиц груза планирует доставить первому потребителю 20 единиц груза. Формально это реализуется тем, что переменной х₁₁ мы присваиваем значение 20 (т.е. х₁₁ = 20). Покажем это в таблице 13.2.

Таблица 13.2 – Таблица распределения методом «северо-западного угла»

	20	110	40	110
60	1 20	2 40	5	3
120	1	6 70	5 40	2 10
100	6	3	7	4 100

После этого спрос l-го потребителя будет полностью удовлетворен (20 = 20) . В результате о первый столбец табли­цы поставок выпадет из последующего рассмотрения (заполнен­ные клетки будем перечеркивать сплошной линией (клетка 1.1 таблицы 13.2). Клетки, выпавшие из последующего рассмотрения, перечеркиваются пунктирной линией (клетки 2.2 и 2.2 первого столбца). У поставщика 1 осталось не распределенными 60 – 20 = 40 единиц груза.

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (1.2) . Второму потребителю требуется доставка 110 единиц груза, а у первого поставщика осталось в запасе 40 единиц груза. Поэтому спланируем: первый поставщик должен перевести второму получателю 40 единиц груза. Формально это означает, что х₁₂ должно принять значение равное 40 (х₁₂ = 40). Запишем это в правом нижнем углу клетки (1.2). Отметим эту клетку сплошной косой чертой, а клетки (1.3) и (1.4) – пунктирной линией (т.к. возможности первого поставщика уже полностью исчерпаны).

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (2.2) . Второму потребителю требуется доставка 110 единиц груза, от первого поставщика ему уже спланировано 40 единиц груза, следовательно, ему не достает 110 – 4 = 70 единиц груза. В то же время у поставщика 2 имеется в наличии 120 (больше, чем 70) единиц груза. Спланируем доставку 70–ти единиц груза от поставщика 2 к потребителю 2. Формально это означает, что х₂₂ должно принять значение равное 70 (х₂₂ = 70). Запишем это в правом нижнем углу клетки (2.2). Отметим эту клетку сплошной косой чертой, а клетку (2.2) – пунктирной линией (т.к. потребности второго потребителя обеспечены полностью) .

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (2.3) . Третьему потребителю требуется доставка 40 единиц груза, в то время как у поставщика 2 остались не спланированными 120 – 70 = 50 единиц груза (больше, чем требуется третьему потребителю). Спланируем доставку 40–ка единиц груза от поставщика 2 к потребителю 3. Формально это означает, что х₂₃ должно принять значение равное 40 (х₂₃ = 40). Запишем это в правом нижнем углу клетки (2.3). Отметим эту клетку сплошной косой чертой, а клетку (3.2) – пунктирной линией (т.к. потребности третьего потребителя обеспечены полностью) .

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (2.4). Четвертому потребителю требуется доставка 110 единиц груза, в то время как у поставщика 2 остались не спланированными 120 – 70 - 40 = 10 единиц груза (меньше, чем требуется четвертому потребителю). Спланируем доставку 10–ти единиц груза от поставщика 2 к потребителю 4. Формально это означает, что х₂₄ должно принять значение равное 10 (х₂₄ = 10). Запишем это в правом нижнем углу клетки (2.4). Отметим эту клетку сплошной косой чертой.

После выполнения всех этих действий не наполненной осталась только клетка (3,4). Анализируя сложившуюся на этом шаге ситуацию, можно обнаружить, что неизрасходованными остались только 100 единиц груза третьего поставщика и четвертому потребителю не достает тоже ровно 100 единиц груза. Поэтому запланируем перевозки: поставщик 3 должен доставить потребителю 4  ровно 100 единиц груза. Формально это означает, что х₃₄ должно принять значение равное 100 (х₃₄ = 100). Запишем это в правом нижнем углу клетки (3.4). Отметим эту клетку сплошной косой чертой.

Отметим, что суммарные возможности всех поставщиков строго совпали с суммарными потребностями всех потребителей. Это не случайно, т.к. мы решали закрытую транспортную задачу.

Кроме того, число заполненных клеток (клеток перечеркнутых сплошной линией) в полученном распределении оказа­лось равным т+п­-1 = 3+4 -1 = 6, т.е. числу основных (базисных) переменных. Это тоже не случайно, т.к. на каждом шаге распределения (кроме последнего) из рассмотрения удалялись одна (один) строка (столбец), кроме последнего шага, где одновременно удалились один столбец и удалилась одна строка. Именно поэтому, число заполненных клеток (число шагов) на единицу меньше, чем сумма числа строк и столбцов таблицы поставок, т.е. равно m + n -1.

Именно эта последняя особенность метода «северо-западного угла» является условием того, что полученное первоначальное распределение является базисным (допустимым) , т.е. опорным планом.

Основными достоинствами метода «северо-западного угла» являются простота и логичность распределения, а важнейшим недостатком то, что это распределение никак не учитывает коэффициенты затрат на перевозки и поэтому полученное опорное решение может оказаться достаточно далеко от оптимального (потребуется много шагов, чтобы от этого первоначального базисного плана перейти к оптимальному).

Недостаток метода «северо-западного угла» устранен в методе, получившем название «метод наименьших затрат».

1. 2.2 Получение начального базисного распределения поставок методом «наименьших затрат»

Покажем существо применения этого метода на примере той же самой задачи 13.1.

Решение. Так как мы должны минимизировать стоимость перевозок, то отыскиваем в таблице поставок (таблица 13.1) клетку (клетки) с наименьшими коэффициентами затрат (в данном случае таких клеток 2 – клетки (1.1) и (2.1). Коэффициенты затрат в этих клетках равны между собой и равны 1.

Сравним максимально возможные поставки для этх клеток между собой. Для клетки (1,1) - х₁₁ = min {60,20} = 20. Для клетки (2,1) - х₂₁ = min {120,20} = 20. Так как они совпадают, то первое распределение поставок можно осуществить в любую из них. Пусть мы отдадим первую поставку поставщику 2. Формально это означает, что х₂₁ должно принять значение равное 20 (х₂₁ = 20). Запишем это в правом нижнем углу клетки (2.1) (таблица 8.3). Отметим эту клетку сплошной косой чертой. Потребности первого получателя полностью удовлетворены, поэтому остальные клетки первого столбца отметим пунктирной линией.

Таблица 8.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.2) и (2.4), (с₁₂ = с₂₄ = 2). Сравним максимально возможные поставки для этих клеток:

Для клетки (1.2) – х₁₂ = min { 120,20} = 20.

Для клетки (2.4) – х₂₄ = min { 120 - 20,110} = 100 . Планируем очередную поставку в клетку (2.4) – для нее максимальные поставки оказались больше.

Формально это означает, что х₂₄ должно принять значение равное 120 – 20 = 100 (х₂₄ = 100). Запишем это в правом нижнем углу клетки (2.1) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Возможности второго поставщика полностью исчерпаны, поэтому вторая строка выпадает из дальнейшего рассмотрения (отметим остальные клетки второй строки (кроме клеток (2.1), (2.4) пунктирной линией.

На третьем шаге из оставшихся клеток отберем те, у которых наименьшие коэффициенты затрат. Это клетка (1.2), оставшаяся от второго шага. У первого поставщика имеется 60 единиц груза, поэтому спланируем : первый поставщик должен поставить второму потребителю 60 единиц груза. т.к. х¹² = min {60,110} = 60/. Формально это означает, что х₁₂ должно принять значение равное 60 (х₁₂ = 60). Запишем это в правом нижнем углу клетки (1.2) (таблица 13.3). Отметим эту клетку сплошной косой чертой. При этом оказывается, что возможности первого поставщика полностью исчерпаны. Первая строка выпадает из дальнейшего рассмотрения (отметим остальные клетки второй строки (кроме клетки (1.2.) пунктирной линией).

На четвертом шаге возможности планирования существенно уменьшились, т.к. все запасы поставщиков 1 и 2 полностью исчерпаны. . Отыскиваем минимальные коэффициенты затрат у поставщика 3. Это клетка (3,2) ( с₃₂ = 3). Произведем планирование. Третий поставщик может поставить второму потребителю в принципе 100 единиц груза, а ему требуется 110, но ему уже спланировано от первого поставщика 60 единиц груза. Следовательно. На этом шаге мы можем спланировать ему только 110 – 60 = 50 единиц груза. Выполним такое планирование. Формально это означает, что х₃₂ должно принять значение равное 50 (х₃₂ = 50). Запишем это в правом нижнем углу клетки (3.2) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Потребности второго потребителя оказались полностью удовлетворены, поэтому из дальнейшего рассмотрения выпадает столбец 2.

На пятом шаге устанавливаем, что наименьший коэффициент затрат имеет клетка (3,4) (с₃₄ = 4). У третьего поставщика осталось 100 – 50 = 50 единиц груза. Однако мы не можем все 50 единиц груза распределить потребителю 4, т.к. ему уже запланировано 100 единиц груза от второго поставщика. Следовательно, запланируем ему 110 – 100 = 10 единиц груза от третьего поставщика. Формально это означает, что х₃₄ должно принять значение равное 10 (х₃₄ = 10). Запишем это в правом нижнем углу клетки (3.4) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Потребности четвертого потребителя оказались полностью удовлетворены, поэтому из дальнейшего рассмотрения выпадает столбец 4.

На очередном шаге свободная клетка (3.1) имеет минимальный коэффициент затрат с₃₁ = 6, но эта клетка уже перечеркнута пунктирной линией, т.к. потребности первого потребителя полностью удовлетворены. Остается только выбрать клетку (3.3) с коэффициентом затрат с₃₃ = 7. спланируем доставку от третьего поставщика третьему потребителю (100 – 50 – 10 = 40 единиц груза). Формально это означает, что х₃₃ должно принять значение равное 40 (х₃₃ = 40). Запишем это в правом нижнем углу клетки (3.3) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Потребности четвертого потребителя оказались полностью удовлетворены т возможности третьего поставщика полностью исчерпаны, поэтому из дальнейшего рассмотрения выпадает строка 3 и столбец 4.

Задача решена. Отметим, что суммарные поставки и суммарные потребности, как и в первом случае, полностью совпадают, так мы решали закрытую транспортную задачу.

Сравним с экономической точки зрения опорные планы, полученные методом северо-западного угла и методом наименьших затрат.

В обоих случаях кортеж опорного плана в общем виде записывается одинаково X⁰ = (x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄ ).

При использовании метода северо-западного угла имеем (таблица 13. 2):

X⁰ _сзу = (20, 40,0, 0, 0,70, 40, 10, 0, 0, 0, 100).

Суммарные затраты в денежных единицах примут значение:

F⁰ _сзу = c₁₁ x₁₁+ c₁₂x₁₂ + c₁₃x₁₃ + c₁₄x₁₄ + c₂₁ x₂₁ + c₂₂ x₂₂ + c₂₃x₂₃ + c₂₄ x₂₄ + + c₃₁ x₃₁ + c₃₂ x₃₂ + c₃₃ x₃₃ + c₃₄ x₃₄ =

= 1*20 + 2*40 + 6*70 + 5*40 +2*10 +4*100 = 1140 ден. ед.

При использовании метода наименьших затрат имеем (таблица 13. 3):

X⁰ _НЗ = (0, 60,0, 0, 20,0, 0, 100, 0, 50, 4, 10).

Суммарные затраты в денежных единицах примут значение:

F⁰ _НЗ = c₁₁ x₁₁+ c₁₂x₁₂ + c₁₃x₁₃ + c₁₄x₁₄ + c₂₁ x₂₁ + c₂₂ x₂₂ + c₂₃x₂₃ + c₂₄ x₂₄ + + c₃₁ x₃₁ + c₃₂ x₃₂ + c₃₃ x₃₃ + c₃₄ x₃₄ =

= 2*60 + 1*20 + 2*100 + 3*50 +7*40 +4*10 = 810 ден. ед.

Как и предполагалось при использовании метода наименьших затрат суммарные затраты значительно меньше, чем при использовании метода северо-западного угла.

По существу это означает, что полученная по методу наименьших затрат угловая точка многогранника решений находится «ближе» к угловой точке оптимума, что потребует при вычислении оптимума меньшего числа шагов.

Таким образом, мы решили двумя различными методами подзадачу отыскания первоначального базисного опорного решения транспортной задачи.

Однако мы еще не получили ответы на следующие вопросы:

1) полученный опорный план является допустимым?

2) не является ли полученный опорный план оптимальным?

3) каким образом перейти от первоначального опорного плана к оптимальному?

Дадим ответ на первый вопрос и покажем некоторые особые случаи, которые могут возникнуть при получении первоначального опорного плана.