N. Eriashvili Second Edition t e X tb o o k юн ити u n I t y moscow • 2000

2
Ху
= Я(; 
(25.30)
М
2
Ху » b j ; j = T , n ;
 
(25.31)
i=i
Ху
 £ 0.
Условия (25.31) означают полное удовлетворение спроса во 
всех пунктах потребления; условия (25.30) определяют больший 
вывоз продукции от всех поставщиков.
Необходимым и достаточным условием разрешимости зада­
чи (25.29) — (25.31) является условие баланса:
3 U « £' V
(25.32)
/=1 
) = \
Транспортная задача, в которой имеет место равенство 
(25.32), называется закрытой и в качестве ЗЛП может быть ре­
шена с помощью симплексного метода. Однако благодаря осо­
бенностям переменных задачи и системы ограничений разрабо­
таны специальные, менее громоздкие методы ее решения.
Чаще всего применяется метод потенциалов, при котором 
каждой /-Й строке (/-му поставщику) устанавливается потенци­
ал 17/, который можно интерпретировать как цену продукта в 
пункте поставщика, а каждому столбцу 
J
(/-му потребителю) 
устанавливается потенциал 
V/,
 
принимаемый условно за цену 
продукта в пункте потребителя. В простейшем случае цена 
продукта в пункте потребителя равна его цене в пункте по­
ставщика плюс транспортные расходы на его доставку, т.е.:
Vj
 = 
U/ 
+ С у .
(
25
.
33
)
525

---

Алгоритм метода потенциалов для закрытой транспортной 
задачи детально описан в ряде учебных пособий1.
Первым этапом этого алгоритма является начальное рас­
пределение (составление начального плана перевозок). Для 
этого имеется ряд методов: северо-западного угла, наименьших 
стоимостей, аппроксимаций Фогеля и др. Второй этап — по­
строение системы потенциалов на основе равенства (25.33), а 
третий — проверка начального плана на оптимальность, при­
чем в случае его неоптимальности переходят к четвертому эта­
пу, содержание которого заключается в реализации так назы­
ваемых циклов перераспределения плана прикрепления потре­
бителей к поставщикам, после чего переходят опять к третьему 
этапу. Совокупность процедур четвертого и третьего этапов об­
разует одну итерацию, и эти итерации повторяются, пока план 
перевозок не окажется оптимальным по критерию (25.29)
Если баланс (25.32) не выполняется, то ограничения (25.30) 
или (25.31) имеют вид неравенств типа «меньше или равно»; 
транспортная задача в таком случае называется открытой. Для 
решения открытой транспортной задачи методом потенциалов 
ее сводят к закрытой задаче путем ввода или фиктивного по­
требителя, если в неравенства превращаются условия (25.30), 
или фиктивного поставщика в случае превращения в неравен­
ства ограничений (25.31).
Модель оптимизации загрузки производственных мощностей. В 
общем виде задачу оптимальной загрузки производственных 
мощностей можно сформулировать следующим образом.
Имеется