Фрагмент для ознакомления
1
Задача 1
Контрольные вопросы 4
1. Всегда ли стоит вводить целочисленные ограничения, чтобы получить целые решения? Есть ли отрицательные последствия введения таких ограничений? Какие?
2. Что такое логические переменные? В каких задачах их применение необходимо? Приведите 2-3 собственных примера.
3. Объясните, почему постоянные издержки нельзя учесть в простой ЛП-задаче (без целочисленных переменных)? Почему для определения оптимального плана неприемлема бухгалтерская практика «размазывания» постоянных издержек по всей партии выпущенных изделий и определение таким образом «удельных» издержек на единицу продукции?
4. Объясните, каким образом введение целочисленных (точнее, логических) переменных помогает решить проблему постоянных издержек в ЛП-задачах?
5. Приведите 2-3 собственных примера, когда дробные решения задач линейного программирования имеют практический смысл и не требуют округления до целых и когда округление до целых необходимо.
Фрагмент для ознакомления
2
Задача.
Ткацкий цех выпускает два вида тканей Т1 и Т2, на двух видах станков С1 и С2. Количество станков первого типа – 103, второго – 210. Станок С1 выпускает 54 м ткани Т1 или 72 Т2, а станок С2 выпускает 34 м ткани Т1 или 65 Т2 за смену.
Производство ткани ограничено ресурсами и складскими помещениями. За смену можно выпустить не более 6000 м ткани Т1 и не более 11000 м ткани Т2.
Доход от продажи ткани Т1 - 7,3 у.е. за 1 м, от продажи ткани Т2 - 4,2 у.е. за 1 м.
Как распределить производство тканей ткани Т1 и Т2 между станками С1 и С2, чтобы максимизировать прибыль?
Для всех вариантов произведенных расчетов введите целочисленное ограничения на переменные – число станков, выпускающих каждый из видов ткани.
//
Ответы на вопросы
1) в ряде случаев совершенно необходимо получить целочисленные значения переменных решения. Надстройка "Поиск решения" MS-Excel позволяет легко ввести требование целочисленности переменных. Однако необходимо ясно осознавать, что введение такого ограничения означает отказ от использования эффективных методов решения задач линейного программирования, если переменные целые "Поиск решения" MS-Excel будет использовать другие, специальные, более сложные алгоритмы, которые требуют существенно больших вычислительных затрат, чем симплекс-метод и другие ЛП-алгоритмы. Кроме того, отказ от обычной ЛП-модели в пользу ЛП-модели с требованием целочисленности переменных делает невозможным получение информации об устойчивости решения и о теневых ценах. Поэтому "Поиск решения" MS-Excel не формирует отчета об устойчивости, если в качестве одного из ограничений введено условие целочисленности хотя бы для одной переменной. Это лишает аналитика и менеджера важного инструмента анализа оптимального решения и определения путей его улучшения через изменение параметров модели.
2) Весьма часто на практике возникают задачи, когда требуется решить, какие элементы из большого их набора нужно выбрать, чтобы оптимизировать целевую функцию и удовлетворить заданным ограничениям, а какие отбросить. Этот класс задач по-английски называют задачами типа "go/no go", что по-русски соответствует дилемме "брать/не брать". Часто также о подобных задачах говорят как о задачах "загрузки вещевого мешка", имея в виду следующую "туристическую" аналогию.
Показать больше