Примеры выполнения задач

ПРИМЕР № 1

Для изготовления четырёх видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице.

Какое количество продукции каждого вида должно изготовляться, чтобы доход от реализации был максимальным?

Решение.

• 1. Формулировка математической модели задачи:
  • · переменные для решения задачи: x₁ — суточный объём изготовления продукции А, x₂ — суточный объём изготовления продукции Б, x₃ — суточный объём изготовления продукции В, x₄ — суточный объём изготовления продукции Г;
  • · определение функции цели (критерия оптимизации). Суммарная суточная прибыль от изготовления всех видов продукции равна:

F=12* x₁ +7* x₂ +18* x₃ +10* x_4,

поэтому цель состоит в том, чтобы среди всех допустимых значений x_1, x_2, x_3, x₄ найти такие, которые максимизируют суммарную прибыль от изготовления продуктов F:

F=12* x₁ +7* x₂ +18* x₃ +10* x₄ max;

• · ограничения на переменные:
  • 1. объём производства продукции не может быть отрицательным, т. е.

x₁? 0, x₂? 0, x₃? 0, x₄? 0;

• 2. расход исходного продукта для изготовления всех видов продукции не может превосходить максимально возможного запаса данного исходного продукта, т. е.
• 1* x₁ +2* x₂ +1* x₃ +0* x₄? 18,
• 1* x₁ +1* x₂ +2* x₃ +1* x₄? 30,
• 1* x₁ +3* x₂ +3* x₃ +2* x₄? 40,

Таким образом, получаем следующую математическую модель задачи:

· Найти максимум следующей функции:

F=12* x₁ +7* x₂ +18* x₃ +10* x₄ max;

• · При ограничениях вида:
  • 1* x₁ +2* x₂ +1* x₃ +0* x₄? 18,
  • 1* x₁ +1* x₂ +2* x₃ +1* x₄? 30,
  • 1* x₁ +3* x₂ +3* x₃ +2* x₄? 40,

x₁? 0, x₂? 0, x₃? 0, x₄? 0;

2. Подготовка листа рабочей книги MS Excel для вычислений — на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7. Переменные задачи x1, x2, x3, x4 находятся соответственно в C3, С4, С5, С6. Целевая функция находится в ячейке С8 и содержит формулу:

=12*C3+7*C4+18*C5+10*C6.

Ограничения на задачу учтены в ячейках С10: С12.

3. Работа с надстройкой Поиск решения — воспользовавшись командой Сервис | Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рис. 8). Результат работы по поиску решения помещён на рис. 9 — 14.

Рис. 10. Отчёт по результатам поиска решения.

ВЫВОД: из решения видно, что оптимальный план выпуска предусматривает изготовление продукции видов «А» и «Г». А продукцию видов «Б» и «В» производить не стоит. Полученная Вами прибыль составит 326 усл. ед.

ПРИМЕР № 2.

Задача распределения ресурсов Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется два исходных продукта A и B. Расходы продуктов A и B на 1 т. соответствующих красок и запасы этих продуктов на складе приведены в таблице:

Таблица

Продажная цена за 1 тонну краски для внутренних работ составляет 2 000 рублей, краска для наружных работ продается по 1 000 рублей за 1 тонну. Требуется определить, какое количество краски каждого вида следует производить предприятию, чтобы получить максимальный доход.

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

I. Составление математической модели задачи.

1) Переменные задачи.

Обозначим: x₁ — количество производимой краски для внутренних работ;

x₂ — соответствующее количество краски для наружных работ.

2) Ограничения, которым должны удовлетворять переменные задачи:

x₁, x₂ 0;

по расходу продукта A: x₁ + 2x₂ 3;

по расходу продукта B: 3x₁ + x₂ 3;

В левых частях последних двух неравенств определены расходы продуктов A и B, а в правых частях неравенств записаны запасы этих продуктов.

3) Целевая функция задачи.

Обозначим Z доход от продажи краски (в тысячах рублей), тогда целевая функция задачи записывается так:

Z = 2x₁ + x₂ ,.

таким образом, задача состоит в том, чтобы найти max Z=2×1+x2, при ограничениях:

x₁ + 2x₂ 3 (A).

3x₁ + x₂ 3 (B).

x₁, x₂ 0 .

Так как переменные задачи x₁ и x₂ входят в целевую функцию и ограничения задачи линейно, то соответствующая задача оптимизации называется задачей линейного программирования (ЛП) В рассматриваемом примере содержатся только две переменные x₁ и x₂, поэтому задачу можно решить графически.

1) На плоскости x₁, x₂ строим область допустимых значений переменных, определяемую ограничениями задачи:

x₁ + 2x₂ 3 (A).

3x₁ + 1x₂ 3 (B).

x₁, x₂ 0 .

Последнее ограничение определяет первый квадрант плоскости. Чтобы построить множество точек удовлетворяющих неравенству (А) нанесем на плоскость график прямой, определяющий границу этого множества: x₁+2x₂=3 (A).

Приведем это уравнение к виду:. А это уравнение прямой «в отрезках» и для построения этой прямой используются две точки (a, 0) и (0, b). (См. рисунок 11).

Проведя уравнение (A) к виду прямой в отрезках, получим:

Аналогично, для ограничения (B) уравнение прямой в отрезках будет:

Построим обе прямые на плоскости. Множества точек, удовлетворяющие неравенствам (A) и (B) будут полуплоскости, лежащие под соответствующими прямыми, а множество допустимых значений переменных будет пересечением (общей частью) этих полуплоскостей, лежащее в первом квадранте: четырехугольник ABCD (см. рис.12).

2) На множестве допустимых решений (ABCD) найдем точку, в которой целевая функция Z=2x₁+x₂ имеет максимальное значение. Для этого посмотрим линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:

Z = 2x₁ + x₂ = К ,.

где К — задаваемая постоянная.

При К = 1 уравнение линии уровня будет:

2x₁ + x₂ = 1.

или (в отрезках) :

При К = 2, аналогично:

2x₁ + x₂ = 2, или .

Нанеся линии уровня на область допустимых решений (рис.13), получим, что при увеличении значения Z соответствующая линия уровня перемещается параллельно предыдущей вправо и вверх. Таким образом, точкой из многоугольника ABCD в которой целевая функция Z имеет максимальное значение будет вершина С. Эта точка и определяет решение задачи.

3) Вычисление координат оптимальной точки ©.

Точка C лежит на пересечении прямых (A) и (B), поэтому, чтобы определить ее координаты надо решить систему уравнений:

x₁ + 2x₂ = 3 (A).

3x₁ + x₂ = 3 (B).

Решение.

x₁^* = 0.6; x₂^* = 1.2 ;

максимальное значение Z:

Z^* = 2*0.6 + 1.2 = 2.4.