8.5. Целочисленное программирование
Под целочисленным или дискретным программированием понимают задачи, в которых искомые переменные могут принимать только целые значения: число рабочих, разделяемых по рабочим местам, количество единиц оборудования, устанавливаемых на заданной площади, и т.
п.Аналитическая задача целочисленного программирования формулируется:
п
шах(шт)Х = Е С/Х/;
/=1
п
Е а/х/ < Ьг (г=1... т);
/=1
й/ < X/ < Б/ (/ = 1... п),
где X/ = 0, 1, 2, ... целые (/ = 1,..., п < п).
Если п1 = п, то задачу называют полностью целочисленной; если п1 < п, то частично-целочисленной (ЧЦП).
Предположим, что задача имеет многогранник решений (рис. 8.3). Если наложить требование целочисленности, то допустимое множество решений выразится в системе точек и уже не будет являться выпуклым.
Если добавить новые ограничения, связывающие внешние целочисленные точки, а затем в качестве многогранника использовать все выпуклое множество, ограниченное осями координат и новым контуром, то получим новую задачу линейного программирования со следующими свойствами:
Рис. 8.3 1.
Новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка — целая. 2.
Так как целевая функция достигает оптимума в угловой точке, то построением многогранника обеспечивается целочисленность оптимального решения.
Решение задач целочисленного программирования трудоемко, поэтому по возможности лучше не накладывать ограничений целочисленности переменных.
В ряде случаев задачу целочисленного программирования решают следующими способами: как непрерывную задачу линейного программирования; округляют переменные; проверяют допустимость округленного решения; если решение допустимо, то оно принимается как целочисленное.
При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи — конечно. Например, в задаче с переменными х1, х2: 0 < х1< 4; 0 < х- < 5 число возможных решений — 20. Следовательно, допустим полный перебор возможных сочетаний целочисленных х1, х2 и выбор наилучшего в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсечений и методы возврата, среди которых наиболее известен метод ветвей и границ.
Еще по теме 8.5. Целочисленное программирование:
- 4.2. Основы социального программирования
- 8.16. Эвристическое программирование
- 8.4. Линейное программирование
- 8.14. Стохастическое программирование
- Экономическое программирование
- 8.13. Динамическое программирование
- Метод математического программирования
- 8.10. Дробно-линейное программирование
- 8.8. Дискретное программирование
- Линейное программирование
- 5.7.2. Сведение матричной игры к задаче ч: линейного программирования
- 7.3. СОЦИАЛЬНОЕ ПРОГРАММИРОВАНИЕ КОМПЛЕКСНЫЕ ЦЕЛЕВЫЕ ПРОГРАММЫ И ПРОЕКТЫ КАК ОРГАНИЗАЦИОННАЯ ФОРМА ЦЕЛЕПОЛАГАНИЯ
- 8.6. Метод ветвей и границ
- Контрольные вопросы
- 4.3. Критерии выбора эффективных решений
- 2.2. Технологии решения задач по скалярному критерию
- 4.1. Невербальный базисный компонент кода — символический уровень
- 1.3.4. Математические методы оценки экономических рисков
- Интеграция программ в контекст политических решений