Схема решения задач линейного программирования в MS Excel 2007 следующая:
1. Составить математическую модель.
2. Ввести на рабочий лист Excel условия задачи:
а) создать форму на рабочем листе для ввода условий задачи;
б) ввести исходные данные, целевую функцию, ограничения и граничные условия.
3. Указать параметры в диалоговом окне Поиск решения.
4. Проанализировать полученные результаты.
Рассмотрим решение задачи оптимизации на примере.
Пример. Задача определения оптимального ассортимента продукции
Предприятие изготавливает два вида продукции – П1 и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья – А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 ед. соответственно. Расход сырья на единицу продукции вида П1 и П2 – табл. 1.
Таблица 1
| Сырье | Расход сырья на 1 ед. продукции | Запас сырья, ед. | ||
| П1 | П2 | |||
| А | ||||
| В | ||||
Опыт работы показал, что суточный спрос на продукцию П1 никогда не превышает спроса на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. – для П1 и 4 д. е. – для П2.
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
Решение. Построим математическую модель для решения поставленной задачи.
Предположим, что предприятие изготовит x1 единиц продукции П1 и x2 единиц продукции П2. Поскольку производство продукции ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства:
|
|
Доход от реализации x1 единиц продукции П1 и x2 единиц продукции П2 составит 
Cреди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значения Fmax.
Рассматриваемая задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени.
Создадим на рабочем листе форму для ввода исходных данных (рис. 1). Заливкой выделены ячейки для ввода функций.
Рисунок 1
В ячейку E5 введем формулу для целевой функции (рис. 1). Используя обозначения
Используя обозначения соответствующих ячеек в Excel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенной для значений переменных задачи (B3, C3), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B5, C5).
Рисунок 2
Аналогично в ячейки D10:D11 введены формулы для расчета левой части ограничений (рис. 3).
Рисунок 3
На вкладке Данные в группе Анализ выберем команду Поиск решения.
В диалоговом окне Параметры поиска решения установим следующее (рис. 4):
Рисунок 4
· в поле Оптимизировать целевую функцию выбираем ячейку со значением целевой функции – Е5;
· выбираем, максимизировать или минимизировать целевую функцию;
|
|
· в поле Изменяя ячейки переменных выбираем ячейки со значениями искомых переменных B3:C3 (пока в них нули или пусто);
· в области В соответствии с ограничениями с помощью кнопки Добавить размещаем все ограничения нашей задачи (рис. 7);
· в поле Выберите метод решения указываем Поиск решения линейных задач симплекс-методом;
· нажимаем кнопку Найти решение.
Добавляем ограничения для нашей задачи. Для неравенств
указываем в поле Ссылка на ячейки диапазон D10:D11, выбираем в раскрывающемся списке знак неравенства, в поле Ограничение выделяем диапазон F10:F11 и нажимаем кнопку Добавить (рис. 5), чтобы принять ограничение и добавить следующее ограничение. Для принятия ограничения и возврата к диалоговому окну Поиск решения нажмите кнопку Ok.
Рисунок 5
Покажем окна для добавления ограничений:
преобразуем в (рис. 6);
Рисунок 6
6х2≤2 (рис.7)
Рисунок 7
х1≥0, х2≥0 (рис.8)
Рисунок 8
После выбора кнопки Найти решение появляется окно Результаты поиска решения (рис. 9).
Рисунок 9
Для сохранения полученного решения необходимо использовать переключатель Сохранить найденное решение в открывшемся окне диалога Результаты поиска решения. После чего рабочий лист примет вид, представленный на рис. 10.
Рисунок 10
Сохранить модель поиска решения можно следующим образом:
1) при сохранении книги Excel после поиска решения все значения, введенные в окнах диалога Поиск решения, сохраняются вместе с данными рабочего листа. С каждым рабочим листом в рабочей книге можно сохранить один набор значений параметров Поиска решения;
|
|
2) если в пределах одного рабочего листа Excel необходимо рассмотреть несколько моделей оптимизации (например, найти максимум и минимум одной функции или максимальные значения нескольких функций), то удобнее сохранить эти модели, используя кнопку Загрузить/Сохранить окна Параметры поиска решения. Диапазон для сохраняемой модели содержит информацию о целевой ячейке, об изменяемых ячейках, о каждом из ограничений и все значения диалога Параметры. Выбор модели для решения конкретной оптимизационной задачи осуществляется с помощью кнопки Загрузить/сохранить диалогового окна Параметры поиска решения;
3) сохранить модель можно в виде именованных сценариев, для этого необходимо нажать на кнопку Сохранить сценарий диалогового окна Результаты поиска решений (см. рис. 9).
Кроме вставки оптимальных значений в изменяемые ячейки, Поиск решения позволяет представлять результаты в виде трех отчетов (Результаты, Устойчивость и Пределы). Для генерации одного или нескольких отчетов необходимо выделить их названия в окне диалога Результаты поиска решения (рис. 9). Рассмотрим более подробно каждый из них.
Отчет по устойчивости (рис. 11) содержит информацию о том, насколько целевая ячейка чувствительна к изменениям ограничений и переменных. Этот отчет имеет два раздела: один – для изменяемых ячеек, а второй – для ограничений. Правый столбец в каждом разделе содержит информацию о чувствительности. Каждая изменяемая ячейка и ограничения приводятся в отдельной строке. При использовании целочисленных ограничений Excel выводит сообщение Отчеты об устойчивости и Пределы не применимы для задач с целочисленными ограничениями.
Рисунок 11
Отчет по результатам (рис. 12) содержит три таблицы: в первой приведены сведения о целевой функции до начала вычисления, во второй – значения искомых переменных, полученные в результате решения задачи, в третьей – результаты оптимального решения для ограничений.
Этот отчет также содержит информацию о таких параметрах каждого ограничения, как статус и разница. Статус может принимать три состояния: связанное, несвязанное или невыполненное. Значение разницы – это разность между значением, выводимым в ячейке ограничения при получении решения, и числом, заданным в правой части формулы ограничения. Связанное ограничение – это ограничение, для которого значение разницы равно нулю. Несвязанное ограничение – это ограничение, которое было выполнено с ненулевым значением разницы.
Рисунок 12
Отчет по пределам (рис. 13) содержит информацию о том, в каких пределах значения изменяемых ячеек могут быть увеличены или уменьшены без нарушения ограничений задачи. Для каждой изменяемой ячейки этот отчет содержит оптимальное значение, а также наименьшие значения, которые ячейка может принимать без нарушения ограничений.
Рисунок 13
Полученное решение означает, что объем производства продукции вида П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. продукции. Доход, получаемый в этом случае, составит 12,8 д. е.
Допустим, что к условию задачи добавилось требование целочисленности значений всех переменных. В этом случае описанный выше процесс ввода условия задачи необходимо дополнить следующими шагами.
В окне Поиск решения нажмите кнопку Добавить и в появившемся окне Добавление ограничений введите ограничения следующим образом (рис. 14:
· в поле Ссылка на ячейки введите адреса ячеек переменных задачи B3:C3;
· в поле ввода знака ограничения установите целое;
· подтвердите ввод ограничения нажатием кнопки OK.
Рисунок 14
Решение задачи при условии целочисленности ее переменных – рис. 15.
Рисунок 15
Задание
Найти максимум линейной функции при заданной системе ограничений.
Задание
1. Построить математическую модель задачи.
2. Представить ее в табличной форме на листе Excel.
3. Найти решение задачи средствами надстройки Поиск решения.
4. Вывести отчеты по результатам и устойчивости.
Вариант 1
Для производства столов и шкафов мебельная фабрика использует необ-ходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, при-быль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида – табл. 2.
Определить, сколько столов и шкафов следует изготавливать фабрике, чтобы прибыль от их реализации была максимальной.
Ответ. Прибыль 1 940 р. при количестве столов и шкафов 102 и 166.
Вариант 2
Для производства двух видов изделий A и В используется токарное, фре-зерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида, общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации од-ного изделия – табл. 3.
Найти план выпуска изделий А и В, обеспечивающий максимальную при-быль от их реализации.
Ответ. Прибыль 276 р. при выпуске изделий 12 и 6.