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

xv - l ;
< *
1
,и.
7=1
Однако эти ограничения полностью не описывают допусти­
мые маршруты, так как не исключают возможности разрыва 
пути, т.е. появления нескольких не связанных между собой
533

---

подмаршрутов для части городов. Поэтому вводятся дополни­
тельно и переменных 
Ut,
которые принимают только целые не­
отрицательные значения. Тогда можно записать еще (и — I
) 2
— 
(я — 
1
) ограничений:
Нетрудно показать, что ограничения (25.48) не исключают 
допустимый маршрут, но исключают возможность существова­
ния подмаршрутов.
Таким образом, задача о коммивояжере состоит в миними­
зации:
Это действительно при условиях (25.47), (25.48), где пере­
менные 
Ху, Ut
принимают только неотрицательные целые зна­
чения.
Задача о размещении складов. Она является одной из опти­
мизационных задач исследования операций и решается обычно 
методами нелинейного программирования. Надо минимизиро­
вать общую сумму транспортных и складских расходов при сле­
дующих ограничениях:
а) с каждого предприятия должна быть отгружена вся про­
дукция;
б) не может быть превышена емкость ни единого склада;
в) должны быть удовлетворены заявки всех потребителей.
В процессе решения задачи находится оптимальная по ми­
нимуму затрат трехчленная комбинация: предприятие — склад
— потребитель. При некоторых условиях задача о размещении 
складов может сводиться к обычной транспортной задаче ли­
нейного программирования.
Задача о ранце (или о рюкзаке). Так называется задача о 
наилучшем выборе предметов из общего их количества, т.е. та­
ким образом, чтобы суммарный вес (или габариты) отобранных 
предметов не превышал (не превышали) заданную величину, а 
их суммарная полезность или иная общая оценка (количество 
калорий, общая стоимость и т.д.) была максимальной. Задача о 
ранце решается как задача целочисленного линейного про­
граммирования, методами динамического программирования и 
другими. В частности, эта задача применяется при планирова­
нии оптимальной загрузки самолетов, кораблей, складов и др.