2015-10-22
684Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, если хотя бы одна зависимость - нелинейная, это будет целочисленная задача нелинейного программирования.
Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используемым методом является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Excel.
Дискретная оптимизация средствами Excel проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается в том, что в диалоговом окне Поиск решения устанавливается требование целочисленности соответствующих переменных (при этом в режиме Параметры устанавливается тип задачи - линейная или нелинейная).
|
|
|
Исходя из требования целочисленности в случае дискретной оптимизации возможен вызов только одного Отчета по результатам.
Пример Задача производства неделимой продукции (оптимизация производственной программы мебельного предприятия).
Мебельное предприятие выпускает книжные полки, тумбу под телевизоры и три вида наборов мебели. Характеристики каждого вида продукции приведены в табл. 7. При условии получения максимальной прибыли объем товарной продукции должен составить не менее 459.31 тыс. руб. Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен, поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели 2 - от 7 до 10 тыс. шт. Спрос на наборы мебели 1 и 3 неограничен, и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, количество которого и нормы затрат времени на изготовление единицы продукции каждого вида приведены в табл. 1.8. Предприятие работает в две смены, эффективное время работы каждой машины – 3945 час (коэффициент сменности 1,9). Оптимизировать производственную программу предприятия.
Таблица 7
| Показатели | Виды продукции | ||||
| Наборы мебели | Книжные полки | Тумба под телевизор | |||
| Оптовая цена единицы изделия, тыс. руб., | 7,2 | 14,3 | 32,5 | 0,182 | 1,5 |
| Прибыль от реализации, тыс. руб. | 2,4 | 4,5 | 8,9 | 0,061 | 0,45 |
Таблица 1.8
| Наименование оборудования | Число, шт. | Виды продукции | ||||
| Набор мебели | Книжные полки | Тумба под телевизор | ||||
| Линия раскроя древесностружечных плит | 0,068 | 0,096 | 0,207 | 0,018 | 0,042 | |
| Гильотинные ножницы | 0,045 | 0,080 | 0,158 | 0,011 | 0,035 | |
| Линия облицовки | 0,132 | 0,184 | 0,428 | 0,020 | 0,060 | |
| Линия обрезки кромок | 0,057 | 0,082 | 0,230 | 0,010 | 0,028 | |
| Лаконаливная машина | 0,063 | 0,090 | 0,217 | 0,010 | 0,032 | |
| Полировальные станки | 0,170 | 0,280 | 0,620 | 0,020 | 0,096 |
|
|
|
