<<
>>

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 и выбор наилучшего в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсечений и методы возврата, среди которых наиболее известен метод ветвей и границ.

<< | >>
Источник: Глухов В. В.. Менеджмент: Учебник для вузов. 3-е изд. — СПб.: Питер. — 608 с.. 2008

Еще по теме 8.5. Целочисленное программирование:

  1. 4.2. Основы социального программирования
  2. 8.16. Эвристическое программирование
  3. 8.4. Линейное программирование
  4. 8.14. Стохастическое программирование
  5. Экономическое программирование
  6. 8.13. Динамическое программирование
  7. Метод математического программирования
  8. 8.10. Дробно-линейное программирование
  9. 8.8. Дискретное программирование
  10. Линейное программирование
  11. 5.7.2. Сведение матричной игры к задаче ч: линейного программирования
  12. 7.3. СОЦИАЛЬНОЕ ПРОГРАММИРОВАНИЕ КОМПЛЕКСНЫЕ ЦЕЛЕВЫЕ ПРОГРАММЫ И ПРОЕКТЫ КАК ОРГАНИЗАЦИОННАЯ ФОРМА ЦЕЛЕПОЛАГАНИЯ
  13. 8.6. Метод ветвей и границ
  14. Контрольные вопросы
  15. 4.3. Критерии выбора эффективных решений
  16. 2.2. Технологии решения задач по скалярному критерию
  17. 4.1. Невербальный базисный компонент кода — символический уровень
  18. 1.3.4. Математические методы оценки экономических рисков
  19. Интеграция программ в контекст политических решений