ий способ решения (метод потенциалов)

В качестве первоначального плана возьмём план, полученный методом минимальной стоимости

Критерий оптимальности. Чтобы план был оптимальным, необходимо выполнение следующих условий:

а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки груза, стоящей в этой клетке

;

б) для каждой незанятой клетки сумма потенциалов должна быть не больше стоимости единицы перевозки груза, стоящей в этой клетке

.

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

Таким образом, для проверки плана на оптимальность необходимо построить систему потенциалов.

1. Построение системы потенциалов для плана.

Для построения системы потенциалов используем условие для каждой занятой клетки. Систему потенциалов можно построить для невырожденного опорного плана, который содержит (m+n-1) занятых клеток, где m-число поставщиков, n-число потребителей. Для каждой занятой клетки можно составить уравнение (; ). Таких уравнений будет (m+n-1), а неизвестных (m+n). Уравнений на одно меньше, чем число неизвестных, поэтому система имеет бесчисленное множество решений и одному неизвестному придают произвольное значение (обычно нулевое). После этого определяются остальные потенциалы.

В таблице 7 занятых клеток (m+n-1=4+5-1=8), поэтому план вырожденный.

Выбираем строку, в которой имеется наибольшее число занятых клеток. Такая строка А₄, поэтому полагаем в этой строке потенциал u₄=0. Клетка А₄В₂ содержит стоимость с₄₂=8, для неё должно выполняться условие u₄+v₂=8, откуда следует потенциал v₂=8.Далее клетка А₄В₃: u₄+v₃=12, откуда v₃=12. Следующая клетка по этой строке А₄В₅, в которой u₄+v₅=13, с учетом u₄=0 имеем v₅=13. В клетке А₃В₅ u₃+v₅=2 или u₃+13=2, отсюда u₃=-11. Для следующей клетки А₂В₂ u₂+v₂=u₂+8=7, поэтому u₂=-1.

В клетке А₂В₁: u₂+v₁=-1+v₁=2, следовательно, потенциал v₁=3.

Потенциалы u₁ и v₄ остались неопределёнными, это произошло потому, что опорный план вырожденный. Введем клетку с нулевыми перевозками, которую будем называть фиктивно занятой. Фиктивно занятую клетку надо сделать в строке А₁ или в столбце В₄. Задача решается на минимизацию, поэтому целесообразно взять клетку с наименьшей стоимостью А₃В₄ (см. следующую таблицу).

В этой клетке А₃В₄: u₃+v₄=2 или -11+v₄=2, значит, v₄=13. Далее из клетки А₁В₄ находим u₁: u₁+v₄=1 или u₁+13=1, отсюда u₁=-12. Система потенциалов построена.

2 Проверка выполнения условия оптимальности.

Для каждой незанятой клетки проверяем выполнение условия .

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

Это клетки А₂В₃, А₂В₄, А₂В₅. Таким образом, имеются три клетки, в которых нарушено условие оптимальности; разности соответственно равны 1,6 и 1.

3 Выбор клетки, в которую необходимо послать перевозку.

В задаче линейного программирования в базис включается тот вектор, которому соответствует max (Z_j-C_j). Если отождествлять занятые клетки с векторами, составляющими базис; а незанятые клетки – с остальными векторами системы ограничений и если отождествлять Z_j суммой (u_i+v_j), то в транспортной задаче загрузке подлежит клетка, которой соответствует max[(u_i+v_j)-c_ij]. Поэтому клетку А₂В₄ необходимо сделать занятой.

4 Построение цикла и определение величины перераспределения.

Отмечаем знаком (+) незанятую клетку А₂В₄. До этого в таблице было (m+n-1=4+5-1=8) занятых клеток, которые составляли базис. Теперь в таблице стало (m+n=4+5=9) занятых клеток (линейно зависимых), поэтому должен существовать замкнутый цикл. Намечаем его пунктиром, поочерёдно расставляем знаки (+) и (-) на поворотах, начиная с клетки А₂В₄.

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
v1=3	v2= 8	v3= 12	v4=13	v5=13
A1	u1=-12						а1=100
A2	u2=-1		7 50		+ 6		а2=250
A3	u3=-11		5		0	+ 2 200	а3=200
A4	u4=0		+ 8			50 ‒	а4=300
Потребности

Затем находим , где - перевозки, стоящие в вершинах цикла, отмеченные знаком (-). Величина определяет количество груза, которое надо перераспределить по циклу. Величина прибавляется к перевозкам, отмеченным знаком (+), и вычитается от перевозок, отмеченным знаком (-). Имеем . Следовательно, нулевую перевозку перемещаем в клетку А₂В₄, остальные не изменяются.

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

4 Изменение системы потенциалов.

Для клетки А₂В₄ должно выполняться условие u₂+v₄=6, на самом деле

u₂+v₄=-1+13=12, следовательно, потенциалы нужно уменьшать. Лучше

уменьшить v₄ на 6. Надо теперь переоценить потенциалы в клетке А₁В₄. Имеем u₁+v₄=1 или u₁+7=1, откуда следует u₁=-6 (см. следующую таблицу).

Проверяем на оптимальность незанятые клетки. В первой строке клетки А₁В₃ и А₁В₅, во второй строке клетки А₂В₃ и А₂В₅ не удовлетворяют условию оптимальности; находим для них величины разностей и записываем в нижние левые углы этих клеток. Максимум разности находится в клетке А₁В₅, поэтому эта клетка подлежит загрузке; отмечаем эту клетку знаком (+) и строим цикл (см. следующую таблицу)

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
v1=3	v2= 8	v3= 12	v4=7	v5=13
A1	u1=-6				100 (-)	4 (+)	а1=100
A2	u2=-1		7 50 (-)		0 (+)		а2=250
A3	u3=-11						а3=200
A4	u4=0		150 (+)			13 50 (-)	а4=300
Потребности

Затем находим по клеткам, отмеченным знаком (-), величину = min (100;50;50)=50. Перераспределяем перевозки: прибавляем 50 единиц груза в клетки со знаком (+) и вычитаем такой же груз из клеток со знаком (-).

Получим следующую таблицу

В полученном опорном плане изменяем систему потенциалов. У нас появилась новая клетка с грузом А₁В₅.Чтобы выполнялось условие u₁+v₅=4, лучше уменьшить потенциал v₅=13 до v₅=10, оставив неизменным потенциал u₁=-6. В последнем столбце В₅ есть ещё одна клетка с грузом А₃В₅, в которой должно выполняться условие u₃+v₅=2. Так как v₅=10, то u₃=-8. Система потенциалов установлена. Проверяем незанятые клетки на оптимальность.

Клетки А₁В₃, А₂В₃, А₃В₃ не удовлетворяют условию оптимальности; находим для них величины разностей и записываем в нижние левые углы этих клеток. Максимум разности находится в клетке А₁В₃, поэтому эта клетка подлежит загрузке; отмечаем эту клетку знаком (+) и строим цикл (см. следующую таблицу)

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
v1=3	v2= 8	v3= 12	v4=7	v5=10
A1	u1=-6			(+)	(-)		а1=100
A2	u2=-1		(-)		(+)		а2=250
A3	u3=-8						а3=200
A4	u4=0		(+)	12 (-)			а4=300
Потребности

Находим величину =min (0;100;50)=0. Нулевой груз перемещаем в клетку А₁В₃, остальные клетки без изменения. Получили новый опорный план и изменяем систему потенциалов (см. следующую таблицу):

Пересчёт потенциалов: из клетки А₁В₃ получим v₃=10; из клетки А₄В₃ следует u₄=2; из клетки А₄В₂ вычислим v₂=6.

Далее проверяем незанятые клетки на оптимальность. Все клетки удовлетворяют условию оптимальности, следовательно, план оптимальный.

Найдём общую стоимость составленного плана как сумму произведений объёмов перевозок на соответствующие стоимости в этих же клетках:

(ед. стоимости).

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

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