Задача линейного программирования
Задача. Фирма выпускает два вида древесно-стружечных плит - обычные и улучшенные. При этом производятся две основные операции - прессование и отделка. Определите, какое количество плит каждого типа следует изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, средства), указанных в таблице 1.
Таблица 1
Известно, что за каждые 100 обычных плит фирма получает прибыль, равную 80 ден. ед., а за каждые 100 плит улучшенного вида - 100 ден. ед.





Экономико-математическая модель задачи
Обозначим через х1 – число партий, каждая из которых состоит из 100 обычных плит, х2 – число партий, каждая из которых состоит из 100 улучшенных плит (количество плит каждого типа, умноженные на 100).
Целевая функция - это математическая запись критерия оптимальности, т.е. выражение, которое необходимо максимизировать:
EMBED Equation.3
Ограничения по затратам:
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Решение ЗЛП с помощью команды Поиск решения в среде MS Excel
Приведем описание технологии получения решения приведенной ЗЛП.
1. Запустить Excel, выбрав Microsoft Excel из подменю Программы главного меню Windows. Открывается чистый лист Excel. Создать текстовую форму - таблицу для ввода условий задачи (рис. 1.1).

Рис. 1.1
2. Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначим через х1, х2 - число партий, каждая из которых состоит из 100 обычных и улучшенных плит соответственно (количество плит каждого типа, умноженные на 100). В нашей задаче оптимальные значения вектора EMBED Equation.3 будут помещены в ячейках ВЗ:С3, оптимальное значение целевой функции - в ячейке D4.
3. Ввести исходные данные задачи в созданную форму-таблицу, представленную на рис. 1.2.

Рис. 1.2
4. Ввести зависимость для целевой функции:
• установить курсор в ячейку D4;
• установить курсор на кнопку «Мастер функций», расположенную на панели инструментов. Щелчком левой кнопки мыши открыть «Мастер функций». На экране появляется диалоговое окно Мастер функций шаг 1 из 2. В окне «Категории» выбираем – Математические, в окне «Функции» выбираем – СУММПРОИЗВ (рис. 1.3). > «ОК».

Рис. 1.3
• На экране появляется диалоговое окно СУММПРОИЗВ (рис. 1.4);
• в строку «Массив 1» ввести $В$З:$С$3; адреса ячеек удобнее вводить не с клавиатуры, а протаскивая мышь по указанным ячейкам.
• в строку «Массив 2» ввести В4:С4;
• нажать кнопку «ОК».
На экране с помощью функции СУММПРОИЗВ в ячейку D4 введена функция (рис. 1.4).

Рис. 1.4
5. Ввести зависимости для ограничений:
• установить курсор в ячейку D4, нажать левую клавишу мыши – откроется контекстное меню, в нем выбрать - копировать;
• установить курсор в ячейку D7, нажать левую клавишу мыши – откроется контекстное меню, в нем выбрать - вставить;
Для ячеек D8, D9, D10 произвести аналогичные ячейке D7 операции.
В результате данных преобразований исходная таблица принимает вид, представленный на рисунке 1.5.

Рис. 1.5
Проверить введенные формулы. На панели инструментов выбрать Сервис> Зависимости формул > Режим проверки формул (рис. 1.6)

Рис. 1.6
6. Запустить команду Поиск решения.
На панели инструментов выбрать Сервис> команда Поиск решения > ОК. Появляется диалоговое окно Поиск решения (рис. 1.7).
7. Назначить ячейку для целевой функции:
• установить курсор в строку Установить целевую ячейку;
• ввести адрес ячейки $D$4, щелкнув по соответствующей ячейке рабочего листа;
• ввести направление целевой функции. В нашей задаче целевая функция равна максимальному значению;
• установить курсор в строку Изменяя ячейки;
• ввести адреса искомых переменных В$3:С$3 (рис. 1.7).

Рис. 1.7
8. Ввести ограничения:
• установить указатель мыши на кнопку Добавить и щелкнуть мышью по ней. Появляется диалоговое окно Добавление ограничения (рис. 1.8);
• в строке Ссылка на ячейку ввести адрес $D$7;
• ввести знак ограничения <=;
• в строке Ограничение ввести адрес $F$7;
• установить указатель мыши на кнопку Добавить и щелкнуть мышью по ней. На экране вновь появляется диалоговое окно Добавление ограничения (рис. 1.8).
• ввести остальные ограничения задачи, по вышеописанному алгоритму;
• после введения последнего ограничения нажать кнопку ОК.

Рис. 1.8
На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.9).

Рис. 1.9
9. Ввести параметры для решения ЗЛП:
• в диалоговом окне Поиск решения установить указатель мыши на кнопку Параметры и щелкнуть мышью по ней. На экране появляется диалоговое окно Параметры поиска решения (рис. 1.10);
• установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения (рис. 1.10);
• нажать кнопку ОК.

Рис. 1.10
На экране опять появляется диалоговое окно Поиск решения;
• установить указатель мыши на кнопку Выполнить.
Через непродолжительное время появляется диалоговое окно Результаты поиска решения (рис 1.11) и исходная таблица с заполненными ячейками ВЗ:С3, в которых указываются максимальные в соответствии со значением целевой функции значения х1, х2, и ячейкой D4, в которой указывается максимальное значение целевой функции (рис. 1.12).

Рис. 1.11

Рис. 1.12
10. Создать отчеты по результатам, устойчивости и пределам.
• В окне Результаты поиска решения в поле тип отчета выбрать – Результаты > ОК. Создается отчет по результатам (рис. 1.13)
В отчет по результатам включаются исходные и конечные значения целевой и изменяемых ячеек, дополнительные сведения об ограничениях.
• Запустить команду Поиск решения> Выполнить> тип отчета – Устойчивость > ОК. Создается отчет по устойчивости (рис. 1.14)
В отчете по устойчивости показывается насколько чувствительно решение к изменениям коэффициентов целевой функции или правых частей ограничений. Для линейных моделей отчет включает нормируемую стоимость, теневые цены и ограничения на изменение правой части равенства.
• Запустить команду Поиск решения> Выполнить> тип отчета – Пределы > ОК. Создается отчет по пределам (рис. 1.15)
В отчете по пределам показываются изменяемые и целевая ячейки вместе с соответствующими значениями, верхние и нижние пределы и целевые значения.

Рис. 1.13

Рис. 1.14

Рис. 1.15
Вывод:
Полученное решение означает, что необходимо в течение месяца изготовить 100 партий обычных плит или 10000 обычных плит, и 50 партий улучшенных плит или 5000 улучшенных плит, что бы обеспечить максимальную прибыль, равную 13000 денежных единиц. При этом материал и время на отделку будут использованы полностью (см. рис. 1.13), а из времени на прессование, равного 900 часов, будет использовано 700 часов, из средств на выполнение работы в размере 6000 денежных единиц будет использовано 5500 денежных единиц. Следователь, 200 часов на прессование и 500 денежных единиц, из имеющихся ресурсов на месяц, для изготовления плит не используются.