Решение задачи оптимизации

Цель задачи: ознакомиться с технологией решения задачи оптимизации с помощью средств Excel.

Предприятие выпускает 3 вида продукции (вектор-столбец Х_j). Каждый вид продукции может быть получен при помощи трех различных технологических процессов, которые имеют ограничения по размеру затрат ресурсов предприятия по времени производственного процесса (вектор-столбец В_j). Ресурсы, необходимые для производства каждого вида продукции каждой из имеющихся технологий определяется матрицей затрат ресурсов А_і_j. Доход от реализации каждого вида продукции определяется вектором-столбцом С_і.

Предлагается, пользуясь встроенными функциями и мастером поиска решения Excel:

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

2) провести анализ полученных результатов.

Исходные данные для задания 8 представлены в таблице 1.9:

Таблица 1.9

Значение индекса j\i

Элементы матрицы А_і_j

Вектор В_j

-3

-2

-5

Вектор С_j

-10

Для расчетов понадобится следующая функция Excel:

· СУММПРОИЗВ() – для расчета произведения векторов (получения суммы произведения компонент векторов).

Алгоритм расчетов

Рассматриваемая задача относится к классу задач оптимизации, постановка которых сводится к следующему: максимизировать c ₁ x ₁+ c ₂ x ₂+ c ₃ x ₃ при ограничениях:

a₁₁x₁+ a₁₂x₂+. + a₁₃x₃≤ b₁;

a₂₁x₁+ a₂₂x₂+. + a₂₃x₃≤ b₂;

a₃₁x₁+ a₃₂x₂+. + a₃₃x₃≤ b₃,

x_j ≥ 0, j =1, 2,., n.

где a _1j, a _2j, a _3j – ресурсы, необходимые для обработки единицы 1-го вида продукции x_j имеющимися в распоряжении способами (технологиями) соответственно (j= 1,2,3; x_j – принимают целые значения);

b ₁, b ₂, b ₃ – ограничения на ресурсы предприятия для каждой і -й технологии соответственно (і= 1,2,3).

Запишем поставленную задачу в общем виде: максимизировать при ограничениях

, i= 1,2,., m,

x_j ≥ 0, j =1, 2,., n.

В матричном виде задача записывается следующим образом: максимизировать С^TХ при ограничениях:

AХ≤В;

Х ≥ 0.

Для корректного использования мастера поиска решения Excel необходимо проделать следующую подготовку к расчетам (см. рис. 10):

1) На листе Excel расположим ячейки, куда поместим первоначальные значения вектора Х (эти значения, пусть несущественно, влияют на точность расчетов. Поэтому присвоим всем компонентам вектора Х значение 1).

2) На листе Excel расположим ячейку, куда поместим значение целевой функции c ₁ x ₁+ c ₂ x ₂+ c ₃ x ₃, которое рассчитаем по формуле:

=СУММПРОИЗВ(B8:D8;B11:D11),

где B8:D8 – компоненты вектора С в Excel;

B11:D11 – компоненты вектора Х, задаваемого пользователем, в Excel.

3) На листе Excel расположим ячейки, куда поместим построчное перемножение матрицы А и вектора Х. Для первой строки формула Excel имеет вид:

=СУММПРОИЗВ(B4:D4;B$11:D$11),

где B4:D4 – компоненты первой строки матрицы А в Excel;

B$11:D$11 – компоненты вектора Х, задаваемого пользователем, (для удобства работы в Excel по столбцам используется знак $, фиксирующий строку, в которой помещены значения компонент вектора Х).

Рис. 10. Подготовка к расчетам по 8 заданию

Для расчетов воспользуемся возможностями Excel.

Для этого в закладке «Сервис» мышкой выберем подзакладку «Поиск решения». На экране появится диалоговое окно (см. рис. 11):

Рис. 11. Диалоговое окно подзакладки «Поиск решения»

В окне «Установить целевую ячейку:», нажимая мышкой на цветную кнопку рядом с этим окном, мышкой выделяем ячейку на листе Excel, в которой должно находиться решение (на рис. 10 – это ячейка G3). На рис. 11 показан результат этой операции.

Мышкой поставим условия поиска максимума значения целевой функции, установив требование в закладке «Равной:» в виде точки в окне «максимальному значению». На рис. 11 показан результат этой операции.

В окне «Изменяя ячейки:» аналогичным способом, с помощью мышки, выберем ячейки на листе Excel, в которых располагаются значения компонент вектора Х (в начале расчетов ячейки пустые: см. рис. 10). На рис. 11 показан результат этой операции.

В окне «Ограничения:», нажимая мышкой на кнопку «Добавить» рядом с этим окном, определяем ограничения по поиску решения задачи. Появляется меню «Добавление ограничения», состоящее из 3 окон и 4 кнопок (см. рис.12).

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

После этого нажимаем кнопку «Добавить» для определения следующего ограничения:

Х ≥ 0.

Нажимаем мышкой цветную кнопку рядом с окном «Ссылка на ячейку» и выделяем ячейки, в которых расположены компоненты вектора Х. В среднем окне, нажимая мышкой на стрелочку, устанавливаем вариант выбора «>=». В окне «Ограничение:» с помощью клавиатуры устанавливаем значение «0». На рис. 13 показан результат этой операции.

Рис. 12. Окно «Добавление ограничения» для первого ограничения задачи

Рис. 13. Окно «Добавление ограничения» для второго ограничения задачи

После этого нажимаем кнопку «Добавить» для определения следующего ограничения:

AХ≤В.

Нажимаем мышкой цветную кнопку рядом с окном «Ссылка на ячейку» и выделяем ячейки, в которых расположены компоненты вектора Х, перемноженные построчно на компоненты матрицы А. В среднем окне, нажимая мышкой на стрелочку, устанавливаем вариант выбора «<=». В окне «Ограничение:» с помощью мышки, нажав на цветную кнопку рядом с окном, выделяем ячейки, в которых расположены компоненты вектора В. На рис. 14 показан результат этой операции.

Рис. 14. Окно «Добавление ограничения» для третьего ограничения задачи

Все ограничения задачи определены – нажимаем на кнопку «ОК» диалогового окна «Добавление ограничений». На рис. 15 показан результаты внесения всех ограничений по задаче.

Рис. 15. Результаты внесения всех ограничений в окне «Поиск решения»

Далее нужно определить параметры решения задачи оптимизации. Для этого нажимаем мышкой на кнопку «Параметры» и назначаем значения параметров поиска решения. После выбора параметров нажимаем на кнопку «ОК» диалогового окна «Параметры поиска решения». На рис. 16 показан результат этой операции.