Маленькая кондитерская фабрика должна закрыться на реконструкцию. Необходимо реализовать оставшиеся запасы сырья, для производства продуктов из ассортимента фабрики, получив максимальную прибыль. Запасы и расход каждого вида сырья для производства единицы продукции каждого вида, а также нормы прибыли для каждого продукта (прибыль на 1 пакет), представлены в таблице.
Сырье Запасы, кг Продукты, расход сырья, кг
| Ореховый звон | Райский вкус | Батончик | Белка | Ромашка | ||
| Темный шоколад | 0.8 | 0.5 | 1.1 | |||
| Светлый шоколад | 0.2 | 0.1 | 0.1 | 0.1 | 0.2 | |
| Сахар | 815.5 | 0.3 | 0.4 | 0.6 | 1.3 | 0.05 |
| Карамель | 0.2 | 0.3 | 0.3 | 0.7 | 0.5 | |
| Орехи | 0.7 | 0.1 | 0.9 | 1.5 | ||
| Прибыль/пакет у.е. | 0.7 | 1.1 | 0.6 |
В разговоре с владельцем фабрики мастер, используя свой 20-летний опыт, предлагает «на глазок» выпустить по 200 пакетов каждого продукта, утверждая, что ресурсов «должно хватить», а прибыль получится, очевидно, 1080 у.е.
При разговоре присутствует сын владельца фабрики, только что закончивший программу «Бакалавр делового администрирования», который утверждает, что такие проблемы надо решать не «на глазок», а с помощью линейного программирования. Умиленный отец обещает сыну всю прибыль сверх
1080 у.е., если он предложит лучший план, чем многоопытный мастер.
Анализ Действия 1-го.
Переменные решения в данном случае - это количество пакетов каждого из 5-ти продуктов, выпускаемых фабрикой.
При этом целевую функцию - прибыль от производства - можно записать как сумму произведений количества произведенных пакетов каждого продукта на норму прибыли каждого продукта
Ограничения состоят в том, что расход каждого из сырьевых ресурсов на весь производственный план не должен превышать запас данного ресурса. Расход каждого вида сырья на производство одного пакета каждого продукта, можно найти на пересечении строчки (сырье) и столбца (продукт) в таблице параметров. Это, так называемые, технологические коэффициенты производства.
Организуем данные на листе MS Excel так, как это показано на рисунке
(Рис. 17) «На кондитерской фабрике».
| A | B | C | D | E | F | G | |
| На кондитерской фабрике | |||||||
| Продукты | |||||||
| Сырье | Запасы | Ореховый звон | Райский вкус | Батончик | Белка | Ромашка | |
| Темный шок. | 0,8 | 0,5 | 1,1 | ||||
| Светлый шок. | 0,2 | 0,1 | 0,1 | 0,1 | 0,2 | ||
| Сахар | 815,5 | 0,3 | 0,4 | 0,6 | 1,3 | 0,05 | |
| Карамель | 0,2 | 0,3 | 0,3 | 0,7 | 0,5 | ||
| Орехи | 0,7 | 0,1 | 0,9 | 1,5 | |||
| Прибыль | 0,7 | 1,1 | 0,6 | ||||
| Ореховый звон | Райский вкус | Батончик | Белка | Ромашка | |||
| Переменные | 454,48 | 58,78 | 0,00 | 503,99 | 9,13 | ||
| Цель | |||||||
| Расход | P = | =СУММПРОИЗВ(C13:G13;C9:G9) | |||||
| Темный шок. | =СУММПРОИЗВ($C$13:$G$13;C4:G4) | ||||||
| Светлый шок. | =СУММПРОИЗВ($C$13:$G$13;C5:G5) | ||||||
| Сахар | =СУММПРОИЗВ($C$13:$G$13;C6:G6) | ||||||
| Карамель | =СУММПРОИЗВ($C$13:$G$13;C7:G7) | ||||||
| Орехи | =СУММПРОИЗВ($C$13:$G$13;C8:G8) |
Рис. 17
В ячейку F16 введена целевая функция, представляющая собой сумму произведений прибылей от продажи одного пакета каждого продукта (строка 9) на произведенное количество каждого продукта (строка 13). В ячейках C13:G13 – содержатся переменные
В ячейках B16:B20- введены формулы, отражающие расход ресурсов на весь производственный план.
Остается сформировать задачу для надстройки Поиск решения. После того, как мы зададим целевую ячейку, цель (поиск максимума), изменяемые ячейки и отметим во вкладке «Параметры», что задача линейная и переменные неотрицательны, останется только задать ограничение. В данном случае оно только одно (если задавать его для группы ячеек): реальный расход ресурсов, рассчитанный в ячейках B16:B20, не должен превышать запасы на складе, записанные в ячейках B4:B8.
После команды «Выполнить» получим решение, приведенное на рисунке
(Рис. 18).
| На кондитерской фабрике | ||||||
| Продукты | ||||||
| Сырье | Запасы | Ореховый звон | Райский вкус | Батончик | Белка | Ромашка |
| Темный шок. | 0,8 | 0,5 | 1,1 | |||
| Светлый шок. | 0,2 | 0,1 | 0,1 | 0,1 | 0,2 | |
| Сахар | 815,5 | 0,3 | 0,4 | 0,6 | 1,3 | 0,05 |
| Карамель | 0,2 | 0,3 | 0,3 | 0,7 | 0,5 | |
| Орехи | 0,7 | 0,1 | 0,9 | 1,5 | ||
| Прибыль | 0,7 | 1,1 | 0,6 | |||
| Ореховый звон | Райский вкус | Батончик | Белка | Ромашка | ||
| Переменные | 454,48 | 58,78 | 0,00 | 503,99 | 9,13 | |
| Цель | ||||||
| Расход | P= | 1509,09 | ||||
| Темный шок. | 1411,00 | |||||
| Светлый шок. | 149,00 | |||||
| Сахар | 815,50 | |||||
| Карамель | 465,89 | |||||
| Орехи | 1080,00 |
Рис. 18
|
Рис. 19
В установках надстройки Поиск решения существует возможность потребовать целочисленности переменных решения. Для этого достаточно в левом поле этого окна указать ячейки, содержащие переменные решения, а из предлагаемых ограничений выбрать ограничение «цел».
Рис. 20
Вопреки тому, что можно было бы ожидать, получаемое целочисленное решение (производственный план) не совпадает с округленным оптимальным решением, полученным без условия целочисленности (Рис. 21).
| Ореховый звон | Райский вкус | Батончик | Белка | Ромашка | |
| Переменные | 450,00 | 60,00 | 10,00 | 500,00 | 10,00 |
| Цель | |||||
| Расход | P= | 1509,00 |
Рис. 21
|
Рис. 22
Тем не менее, в данной задаче отличие целочисленного решения от обычного по величине целевой функции весьма мало. При этом следует иметь в виду, что добавление этого ограничения исключает использование эффективных методов решения задач линейного программирования. В частности, при целочисленных ограничениях невозможно получить отчет об устойчивости, который, как мы уже видели и неоднократно убедимся далее, дает чрезвычайно важную информацию для анализа вопросов «что если», обеспечивает общий взгляд на исследуемую проблему и более глубокое ее понимание. Задача с целочисленными переменными гораздо более сложна для исследования, а алгоритмы ее решения гораздо менее универсальны и эффективны. Поэтому не задавайте без нужды условие целочисленности. Это особенно важно, когда вы исследуете большую модель (несколько десятков и сотен переменных и ограничений). Задавая целочисленное ограничение в подобной задаче, вы обязательно обнаружите, что время поиска решения драматически увеличилось.
Разумеется, в некоторых случаях без условия целочисленности не обойтись (см. предыдущий пример, а также ниже примеры задач с двоичными, логическими переменными).
