Решение. Проверяем задачу на сбалансированность, для чего рассчитываем суммарный объем наличия ресурса XсА и суммарный объем потребности в ресурсе XсВ

Проверяем задачу на сбалансированность, для чего рассчитываем суммарный объем наличия ресурса X_сА и суммарный объем потребности в ресурсе X_сВ

= 15+30+40=80; = 10+10+20+30=70.

После этого сравниваем объемы X_сА и X_сВ. Поскольку они не равны, то задача несбалансирована. Так как X_сА >X_сВ, то вводится фиктивный потребитель В₅ (n=n+1) и по не нему назначается объем ресурса в размере X_В5 = abs(X_сА - X_сВ)=80-70=10. Для фиктивного потребителя назначаются стоимости (расстояния) равными постоянной величине, например, l_ф= = 8*10=80(l_i5 = 80, i=1,2,3). Однако в связи с тем, что транспортные средства 2-го предприятия необходимо использовать в полном объеме, то расстояние l_2-5 следует принять значительно больше других, например, l_2-5=800. Затем по фиктивному пункту назначаются ограничения равными постоянной величине, например, X_oф³ abs(X_сА - X_сВ) ³ 10 (для фиктивного потребителя X_oi5 = 10, i=1,2,3).

Для учета запрещения поставки ресурса от поставщика А₁ потребителю В₄ заменяем реальную стоимость (расстояние) l_1-4 на большое число, например . Принимаем l_1-4=80.

Обеспечение поставки от поставщика А₂ потребителю В₂ в гарантированном объеме X_г2-2=5 производится следующим образом:

в окончательное решение вводится корреспонденция X_2-2 = 5;

корректируются соответствующие размеры наличия и потребности в ресурсе

X_А2 =X_А2 - X_2-2 =30-5=25; X_B2 = X_B2 - X_2-2 =10-5=5.

С учетом исходных условий и последующих изменений составляем распределительную таблицу (таблица 3.5) и производим первоначальное базисное распределение по методу минимального элемента. Для этого назначаем корреспонденции для связей в порядке возрастания по ним стоимостей (расстояний). Связи загружаются в следующей последовательности: А₁-В₃ объемом 10, А₃-В₂ объемом 5, А₃-В₃ объемом 10; А₃-В₄ объемом 25, А₂-В₁ объемом 10, А₂-В₄ объемом 5, А₂-В₅ объемом 10.

Полученное первоначальное распределение проверяем на оптимальность, для чего рассчитываем значения потенциалов u_Ai и u_Bj. При этом значение одного из потенциалов, например для А₁, задаем равным нулю (u_A1 =0). После того, как определены значения потенциалов, для каждой свободной связи рассчитываем оценочный параметр s_ij по формуле (3.6).

Таблица 3.5 – Распределительная таблица (первоначальное базисное распределение)

Поставщики Ai	Потребители Bj	X Ai	uAi
	B1	B2	B3	B4	B5
A1	+3 4	+6 8		+77 80	-716 80
A2		-2 4	-2 4	+ 5	10 –
A3	+3 5			– 25	-717 80 +
X Bj
uBj

Если для свободной связи s_ij ³0, то связь не является потенциальной, s_ij<0 – потенциальна. В первоначальном распределении потенциальными оказались связи A₁-B₅, A₃-B₅, A₂-B₂ и A₂-B₃ соответственно с оценочными параметрами, равными (-716), (-717), (-2) и (-2).

Для связи A₃-B₅, как для наиболее потенциальной, строится контур, и по нему перераспределяются корреспонденции с загрузкой потенциальной связи. Связи A₂-B₄ и A₃-B₅ (связи со знаком +) догружаются объемом по 10 ед. (минимальный для связей со знаком -), а для связей A₂-B₅ и A₃-B₄ (связи со знаком -) снимается объем по 10 ед. В результате получаем улучшенный план закрепления маршрутов за предприятиями (1-е улучшенное базисное распределение) (таблица 3.6).

Таблица 3.6 – Распределительная таблица (1-е улучшенное базисное распределение)

В улучшенном распределении потенциальными оказались связи A₂-B₂ и A₂-B₃ соответственно с оценочными параметрами, равными (-2) и (-2).

Для связи A₂-B₂, как одной из наиболее потенциальных, строится контур, и по нему перераспределяются корреспонденции с загрузкой потенциальной связи. Связи A₂-B₂ и A₃-B₄ (связи со знаком +) догружаются объемом по 5 ед. (минимальный для связей со знаком -), а для связей A₃-B₂ и A₂-B₄ (связи со знаком -) снимается объем по 5 ед. В результате получаем 2-е улучшенное базисное распределение (таблица 3.7).

Таблица 3.7 – Распределительная таблица (2-е улучшенное базисное распределение)

Поставщи- Ки Ai	Потребители Bj	X Ai	uAi
	B1	B2	B3	B4	B5
A1	+3 4	+8 8		+77 80	+1 80
A2		-2 4	-2 4 +	– 10	717 800
A3	+3 5		– 3	+ 4
X Bj
uBj

Производим проверку полученного распределения на оптимальность.

В улучшенном распределении потенциальной оказалась связь A₂-B₃ с оценочным параметром, равным (-2).

Для связи A₂-B₃, как потенциальной, строится контур, и по нему перераспределяются корреспонденции с загрузкой потенциальной связи. Связи A₂-B₃ и A₃-B₄ (связи со знаком +) догружаются объемом по 10 ед. (минимальный для связей со знаком -), а для связей A₃-B₃ и A₂-B₄ (связи со знаком -) снимается объем по 10 ед. В результате получаем 3-е улучшенное базисное распределение (таблица 3.8).

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

Проверяем выполнение ограничений на размер корреспонденций. Сравнивая в последней таблице значения X_ij (центр клетки связи) и X_oij (правый нижний угол клетки связи) устанавливаем, что нарушено ограничение только для связи A₁-B₃ (X_1-3 =10>X_o1-3 =5). Для связи A₁-B₃ реализуем следующие действия:

в окончательное решение вводится корреспонденция X_1-3 =5;

корректируются соответствующие размеры наличия и потребности в ресурсе

X_А1=X_А1–X_1-3=10-5=5;

X_B3=X_B3–X_1-3=20-5=15;

корректируется соответствующая стоимость (расстояние) поставки l_1-3 путем замены на большое число, например l_1-3 . Принимаем l_1-3=80.

Таблица 3.8 – Распределительная таблица (3-е улучшенное базисное распределение)

Согласно укрупненному алгоритму решения задачи следует с новыми данными вернуться на составление первоначального базисного решения (таблица 3.9).

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

Действуя в ранее изложенном порядке в результате многократных улучшений получаем нижеприведенное оптимальное решение (таблица 3.10).

Согласно общему алгоритму проверяем выполнение ограничений на размер корреспонденций. Поскольку объемы корреспонденций не превышают заданные ограничения на размер поставок, то решение закончено.

Таблица 3.9 – Первоначальное базисное распределение для измененных данных

Таблица 3.10 – Оптимальное распределение для измененных данных

Полное окончательное решение содержит:

ранее включенные корреспонденции в окончательное решение

X_2-2 = 5;

X_1-3 = 5;

и последнее решение для реальных пунктов

X_1-1 = 5;

X_2-1 = 5;

X_2-2 = 5;

X_2-3 = 15;

X_3-4 = 30.

Ответ: исходя из минимума нулевых пробегов и других дополнительных условий оптимально закрепить за 1-м предприятием 1-й и 3-й маршрут с выделением по 5 единиц, за 2-м – 1-й, 2-й и 3-й с выделением соответственно 5, 10 и 15 единиц, за 3-м – 4-й маршрут с выделением 30 единиц транспортных средств.

Поиск по сайту: