Работы с ним

Пример для решения. Решить на ПЭВМ задачу ассортимента продукции, математическая модель которой записывается следующим образом:

Найти оптимальное решение (х₁, х₂, х₃, х₄, х₅), позволяющее max суммарную величину прибыли

F= 4,4х₁+5,0х₂+2,6х₃+3,1х₄+3,5х₅ (1)

при условиях:

а) соблюдения ограничений на использование каждого из 4-х видов сырья

51х₁+0х₂+34х₃+0х₄+23х₅ < 7000;

15х₁+53х₂+26х₃+52х₄+27х₅ < 10000; (2)

0х₁+11х₂+0х₃+16х₄+10х₅ = 1500;

5х₁+6х₂+8х₃+10х₄+7х₅ =2000

б) соблюдения условий по неотрицательности всех переменных

х₁ > 0; х₂ > 0; х₃ > 0; х₄ > 0; х₅ > 0. (3)

Для решения задачи в MS Excel целесообразно её модель (см. формулы 1-3) составить в виде таблицы 1 называемой рабочей таблицей.

Инструментарий «Поиск решения…» MS Excel. В процедуре «Поиска решений…» MS Excel используются алгоритмы симплекс-метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями.

Таблица 1

Рабочая таблица (матрица) задачи ассортимента продукции

Работа в процедуре «Поиска решений …» осуществляется следующим образом:

1. В окне MS Excel создается исходная таблица (в нашем примере таблица 1).

2. Вводятся формулы для вычисления:

а) расчетных значений по каждому ограничению (потребность сырья

каждого вида по оптимальному решению), т.е.

i = 1,2,3,4 ;

б) суммарной величины критерия оптимальности, т.е.

3. для переменных X_j в строку оптимальное решение водятся нулевые значения;

4. запускается процедура «Поиск решения…» (Сервис → Поиск решения). Появляется окно «Поиск решения…» (рис.1).

5. В окне «Поиск решения…» следует выполнить следующие действия:

а) установить целевую ячейку, т.е. указать адрес ячейки, куда будет выведена суммарная величина критерия оптимальности;

б) выбрать указатель цели, т.е. max, min или ноль;

Рис. 1. Окно «Поиск решения» MS Excel

в) ввести изменяемые ячейки, т.е. указать диапазон для вывода результата решения (первоначально значения всех переменных принимаются равными нулю);

г) ввести ограничения (с помощью кнопки «добавить»);

д) запустить задачу на решение (выбор кнопки «выполнить»).

После завершения решения на экран выводится окно «Результаты поиска решения» (рис. 2). Это окно используется для вывода итогового сообщения и найденного решения.

Процедура поиск решения позволяет сформировать три типа отчетности, называемые соответственно «Результаты», «Устойчивость», «Пределы».

«Результаты» представляет собой отчет, состоящий из целевой ячейки (критерия оптимальности) и списка влияющих ячеек модели (оптимального

Рис. 2. Окно «Результаты поиска оптимального решения» MS Excel

решения), их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.

«Устойчивость» - это отчет, содержащий сведения о чувствительности решения к малым изменениям в формуле модели: решение, ограничения и двойственные оценки (нормированный градиент (для переменных), множитель Лагранжа (для ограничений)).

Отчет «Пределы» состоит из целевой ячейки, критерия оптимальности и списка влияющих ячеек модели (переменных), их значений, а также нижних и верхних границ. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка при условии фиксированности значений остальных ячеек и их удовлетворения наложенным ограничениям. Соответственно верхним пределом называется наибольшее значение.

Для рассмотренной выше задачи ассортимента продукции получено следующее оптимальное решение.