Российский экономический

Рис. 5.7.
Цикл пересчета для клетки(4,3)
 
Таблица 5.20 
Оптимальное распределение поставок 
4 
1 
35 
2 
5 
5 
3 
20 
2 
3 
40 
7 
4 
25 
4 
5 
2 
65 
0 
0 
0 
10 
0 
[
2 0 0 5
0 0 0 6
0 1 1 0
0 1 0 0
]
. 
(5.20) 
Контрольные вопросы 
1. Как формулируется транспортная задача? 
2. Запишите экономико-математическую модель транспортной задачи. 
3. Как строится опорный план в транспортной задаче? 
4. В чем сущность метода потенциалов? 
5. Как проверяется план задачи на оптимальность? 
110

---

6. Опишите, как решаются открытые транспортные задачи. 
7. Каково содержание распределительного метода решения транспортной задачи? 
8. Как найти первоначальное базисное распределение поставок? 
111

---

Глава 6. Целочисленные задачи 
линейного программирования 
6.1. 
Целочисленное программирование 
Целочисленное программирование ориентировано на решение задач ма-
тематического программирования, в которых все или некоторые переменные 
должны принимать только целочисленные значения. Задача называется полно-
стью целочисленной, если условие целочисленности наложено на все ее пере-
менные; когда это условие относится лишь к некоторым переменным, задача 
называется частично целочисленной. Если при этом целевая функция и функ-
ции, входящие в ограничения, линейные, то говорят, что данная задача являет-
ся задачей линейного целочисленного программирования (ЦЛП). 
Наиболее естественным классом практических задач, которые сводятся к 
задачам целочисленного программирования, являются задачи, в которых пере-
менные являются физически неделимыми величинами, например, количество 
человек, автомобилей, бутылок. 
Другим важным классом таких задач являются экстремальные комбина-
торные задачи, переменные которых носят логический характер (
x
= 0 или 
x
= 
1). Такие переменные называются булевыми. К таким задачам относятся, 
например, задачи выбора некоторого подмножества, обладающего какими-
либо экстремальными свойствами. Примеры некоторых таких задач будут рас-
смотрены ниже. 
Кроме этого, существует класс задач, в которых нет явного требования 
целочисленности переменных, но существуют некоторые особенности, позво-
ляющие свести их к задачам целочисленного или частично целочисленного 
программирования. Пример такой задачи также будет рассмотрен.
Несмотря на то что к настоящему времени разработан ряд методов реше-
ния целочисленных задач, ни один из них не обеспечивает желаемой эффек-
тивности соответствующих вычислительных процедур, что особенно проявля-
ется при увеличении размерности задачи. 
Таким образом, в отличие от задач линейного программирования, время 
решения которых относительно невелико, реализация целочисленных алгорит-
мов в ряде случаев весьма затруднительна. В параграфе будет изложена идея 
одного из современных методов целочисленного программирования.