Оптимизационное моделирование

Постановка задачи 1.

При получении школой нового компьютерного класса необходимо оптимально спланировать использование единственного легкового автомобиля для перевозки 15 компьютеров. Каждый компьютер упакован в две коробки (монитор и системный блок) и существует три варианта погрузки коробок в автомобиль.

Тип коробки Варианты погрузки

1 2 3

Мониторы 3 2 1

Системный блок 1 2 4

Необходимо выбрать оптимальное сочетание вариантов погрузки для того, чтобы перевезти 15 коробок с мониторами и 15 коробок с системными блоками за минимальное количество рейсов автомобиля.

Формальная модель

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

Х1 – количества рейсов автомобиля, загруженного по варианту 1;

Х2 – количества рейсов автомобиля, загруженного по варианту 2;

Х3 – количества рейсов автомобиля, загруженного по варианту 3.

Тогда целевая функция, равная количеству рейсов автомобиля, примет вид: F = X1 + X2 + X3.

Ограничения накладываются количествами коробок с мониторами и системными блоками, которые необходимо перевезти. Должны выполняться два равенства: 3*Х1 + 2*Х2 + 1*Х3 = 15, 1*Х1 + 2*Х2 + 4*Х3 = 15.

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

Х1 >= 0; Х2 >= 0; Х3 >= 0.

Таким образом, необходимо найти удовлетворяющие ограничениям значения параметров, при которых целевая функция принимает минимальное значение.

Компьютерная модель

Ячейки B2, C2, D2 выделить для хранения параметров Х1, Х2, Х3.

В ячейку В4 ввести формулу вычисления целевой функции: =B2+C2+D2.

В ячейку В7 ввести формулу вычисления количества коробок с мониторами: =3*B2+2*C2+1*D2.

В ячейку В8 ввести формулу вычисления количества коробок с системными блоками: =1*B2+2*C2+4*D2.

Исследование модели

В диалогом окне Поиск решения установить:

• адрес целевой ячейки ($B$4);

• вариант оптимизации значения целевой ячейки (максимизации, минимизация или подбор значения);

• адреса ячеек, значения которых изменяются в процессе поиска решения ($B$2 : $D$2);

• ограничения ($B$2>=0, $C$2>=0, $D$2>=0, $B$7=15, $B$8=15, $B$2=целое, $C$2=целое, $D$2=целое).

Выполнить поиск решения.

Ответ

Потребуется 7 рейсов: 3 загружены по первому варианту, 2 – по второму, 2 – по третьему.

Задача2

Фирма выпускает металлические подставки для цветов двух типов. На изготовлении одной подставки первого типа требуется 1 час рабочего времени, на изготовлении одной подставки второго типа требуется 1,5 часа. Имеющийся ресурс времени рабочих за одни сутки составляет 72 часа.

Расход металлического прута на изготовление одной подставки первого типа составляет 1,8 м, второго типа – 3,7 м. суточные запасы металлического прута не могут превышать 190 м.

Затраты на изготовление одной подставки первого типа составляют 150 руб, второго типа – 270 руб. суточные затраты, связанные с изготовлением продукции, не должны превышать 20 000 руб.

Суточный спрос на подставки второго типа не превышает 18 штук и не превышает спрос на подставки первого типа более чем на 5 штук.

Прибыль от реализации каждой подставки первого типа приносит фирме доход 80 руб, а второго типа – 120 руб.

Сколько подставок каждого типа должна изготовить фирма за сутки, чтобы ее прибыль была наибольшей?

Решение

Разработка модели

Обозначение: х1, х2 – количество подставок каждого типа, изготавливаемых фирмой за сутки.

Затраты времени : 1*х1 + 1,5*х2 и не должны превышать 72 часа.

Расход проволоки: 1,8*х1 + 3,7*х2 и не должен превышать 190 м.

Ограничения на величину спроса: х2<=18, х2-х1<=5.

Финансовые затраты: 150*х1 + 270*х2 и не должны превышать 20 000 руб.

Прибыль фирмы: F = 80*х1 + 120*х2 (руб).

Таким образом, задача нахождения наилучшего производственного плана сводится к задаче нахождения таких значений х1 и х2, при которых значение функции F = 80*х1 + 120*х2 минимально и выполняются ограничения:

1*х1 + 1,5*х2 <=72

1,8*х1 + 3,7*х2 <= 190

150*х1 + 270*х2 <= 20 000

х2-х1<=5

х2<=18

х1 >= 0, x2>=0 – целые.

Результат

х1 = 45, х2 = 18.

? Чему равна прибыль за одни сутки?

Определить:

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

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

Количества подставок каждого типа и прибыль предприятия, если запланированный запас денег увеличится до 30 000 руб.

Задача 3

Школьный кондитерский цех готовит пирожки и пирожные. В силу ограниченности емкости склада за день можно приготовить в совокупности не более 700 изделий. Рабочий день в кондитерском цехе длится 8 часов. Если выпускать только пирожные, за день можно произвести не более 250 штук, пирожков же можно произвести 1000, если при этом не выпускать пирожных. Стоимость пирожного вдвое выше, чем пирожка. Требуется составить дневной план производства, обеспечивающий кондитерскому цеху наибольшую выручку.

Пусть цех производит 3 вида изделий: пирожки, булочки, коржики. Вместимость склада – 700 изделий, рабочий день – 8 часов. Если в течение рабочего дня производить только коржики, то можно произвести 1200 штук. Как изменится целевая функция? Какое количество изделий каждого вида будет оптимальным