Переход от открытой ТЗ к закрытой ТЗ

Если задача является открытой, то необходимо провести процедуру закрытия задачи. С этой целью при a < b добавляем фиктивного поставщика A'_m+1 с запасом груза a' _m+1 = b – a. Если же a > b, то добавляем фиктивного потребителя B' _n+1 с заказом груза b'_n+1 = a – b. В обоих случаях соответствующие фиктивным объектам тарифы перевозок c'_ij полагаем равными нулю. В результате суммарная стоимость перевозок z не изменяется.

Решение ТЗ разбивается на два этапа:

1. Определение начального допустимого базисного решения (первоначального опорного плана) – первоначального распределения поставок.

2. Посроение последовательных итераций, улучшающих опорный план (каждый новый план не должен увеличивать сумарные затраты).

Существует несколько способов нахождения опорного плана (исходного решения).

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

Заполнение таблицы начнем с клетки (1, 1). Так как х₁₁ = min{300, 200} = 200, то первый столбец закрыт, при этом оста­ток на базе А составляет 100 единиц.

Рассмотрим заполнение второго столбца таблицы. Так как потребности пункта № 2 со­ставляют 250 единиц, то они могут быть удовлетворены поставкой из базы А 100 единиц и из базы В 150 единиц. Таким образом, x₁₂=min{300-200, 250} = 100, a х₂₂ = min{250-x₁₂, 250} = min{150, 250} = 150. Заполнение второго столбца закончено.

Переходим к заполнению третьего столбца. Потребности пункта № 3 составляют 250 единиц, наличие на базе В составляет 350 - х₂₂ = 200 единиц, поэтому удовлетворение потребности пункта № 3 возможно поставками с базы В 200 единиц и с базы С 50 единиц, т. е. х₂₃=200, а х₃₃ = min{250-x₂₃, 250] = 50, остаток на базе С 400 - х₃₃ = 400 - 50 = 350 единиц. Заполнение третьего столбца закончено.

Переходим к заполнению четвертого столбца. Так как потребности пункта № 4 — 350 единиц, то они полно­стью удовлетворяются поставкой с базы С, поэтому х₃₄ = 350 (табл. 1).

Таблица 1

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

L = 1∙ 200 + 2∙ 100 + 8∙ 150 + 4∙ 200 + 9∙ 50 +1∙ 350 = 3200 (денежных единиц).

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

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

2) Метод «минимального элемента»

Построение опорного решения начнем с клетки, имеющей наименьшую стоимость. Таких клеток две: (1, 1) и (3, 4), значение стоимости в каждой из них равно 1. Рассмотрим клетку (1, 1). В эту клетку заносим значение х₁₁ = 200, тем самым полностью закрывая первый столбец. В клетку (3, 4) заносим значение х₃₄ = 350, закрывая четвертый столбец.

Остатки по первой и третьей строкам равны соответственно 100 и 50 единицам (табл. 2).

	Таблица 2	Рассмотрим следующие клетки с наименьшей стоимостью: это клетка (1, 2) со стоимостью в две денежных единицы, клетка (2, 3) со стоимостью в четыре денежных единицы. Рассмотрим клетку (1, 2). Так как остаток по первой строке равен 100, то зна­чение х 12 = 100. Рассмотрим клетку (2, 3), значение х23 = 250. Таким образом, первая строка и третий столбец закрыты полно­стью (табл. 3).
Таблица 3	Из таблицы 3 видно, что необходимо закрыть второй столбец, что достигается значениями х22 = 100 и х32 = 50. Теперь закрыты все строки и столбцы, и найдено опорное решение (ис­ходный план) (табл. 4).

Таблица 4	Этому плану соответствуют затраты: L = 1∙ 200 + 2∙ 100 + 8∙ 100 + 10∙ 50 + 4∙ 250 +1∙ 350 = 3050 (д. ед).
Таким образом, найдены два опорных решения (опорных плана) (см. табл. 1 и 4). Перейдем к нахождению оптималь­ного плана, что достигается построением новых опорных реше­ний, улучшающих друг друга.