Методы оптимизации в решении задач для MS Excel
Задание 1.
Какие объемы смесей каждого типа надо производить, чтобы доход был максимальным
|
Исходная продукция
|
Расход на 1 т
|
Запасы
|
|
1 тип
|
2 тип
|
3 тип
|
|
|
A
|
1
|
2
|
3
|
6
|
|
B
|
3
|
1
|
2
|
8
|
|
C
|
2
|
2
|
1
|
9
|
Суточный спрос на смесь 3 типа больше, чем на смесь 2 типа на 2 т и на 3
т меньше, чем на смесь 1 типа. Суточный спрос на 1 тип не превышает 4 т.
Оптовые цены: 3, 5 и 7 $ соответственно.
Решение
1. Объявим
переменные 
, 
, 
равные искомым объемам смесей типов 1, 2 и 3
соответственно.
. Накладываем
ограничения, необходимые для выполнения условия
· 
;
· 
;
· 
;
· 
на 2 т 
;
· 
на 3 т 
;
· 
3. Составим целевую функцию
· 
4. Вызываем окно надстройки «Поиск решения»:
В
результате получены значения переменных: 
, 
, 
.
5. Графическая интерпретация:
Ответ
Для максимального дохода необходимо производить 2 т смесей 1-го типа и 2
т - 2-го типа.
Задание 2:
транспортная задача
Имеются n пунктов производства и m пунктов распределения продукции.
Стоимость перевозки единицы продукции с i-го пункта производства в j-й центр распределения cij приведена в таблице, где под строкой понимается пункт
производства, а под столбцом - пункт распределения. Кроме того, в этой таблице
в i-ой строке показан объем производства
в i-ом пункте производства, а j-ом столбце - указан спрос в j-ом центре распределения. Необходимо
минимизировать суммарные транспортные расходы.
|
Стоимость перевозки единицы продукции
|
Объемы производства
|
|
5
|
1
|
7
|
6
|
30
|
|
1
|
5
|
8
|
1
|
40
|
|
5
|
6
|
3
|
3
|
10
|
|
2
|
5
|
1
|
4
|
18
|
|
3
|
7
|
9
|
1
|
10
|
|
Объемы производства
|
20
|
40
|
30
|
|
Решение
1. Из условия задачи видно, что суммарный спрос всех пунктов
распределения превышает суммарное производство продукции всех пунктов производства
на 2 единицы продукции, т.е. существует дефицит продукции. Следовательно,
необходимо ввести фиктивную фабрику, стоимость перевоза продукции из которой
равна стоимости штрафа за просрочку поставки продукции в пункт распределения
(2,5 $) и объем продаж которой равна дефициту продукции (2 единицы).
2. Составим
матрицу переменных 
, элементы которой соответствуют количеству продукции,
перевозимой из i-го пункта производства в j-й пункт
распределения.
3. Составим целевую функцию
4. Накладываем
ограничения на элементы матрицы :
, 
;
где
bj - спрос продукции в j-ом пункте
распределения;
где
ai - спрос продукции в i-ом пункте
производства.
5. Вызываем окно надстройки «Поиск решения»
В
результате получена матрица ,
приведенная в таблице
|
Пункты распределения
|
|
1
|
2
|
3
|
4
|
|
Фабрики производства
|
1-я
|
0
|
30
|
0
|
0
|
|
2-я
|
20
|
10
|
0
|
10
|
|
3-я
|
0
|
0
|
10
|
0
|
|
4-я
|
0
|
0
|
18
|
0
|
|
5-я
|
0
|
0
|
0
|
10
|
|
фиктивная
|
0
|
0
|
2
|
0
|
При этом суммарные транспортные расходы составят 173 у.е.
Ответ
Для минимизации транспортных расходов на перевозку продукции необходимо
из 1-го пункта производства перевезти 30 единиц продукции во 2-й пункт
распределения; из 2-го пункта производства перевезти 20 единиц продукции в 1-й
пункт распределения, 10 единиц - во 2-й и 10 единиц - в 3-й; из 3-го пункта
производства необходимо перевезти 10 единиц продукции в 3-й пункт
распределения; из 4-го пункта производства перевезти 18 единиц продукции в 3-й
пункт распределения; из 5-го пункта производства перевезти 10 единиц продукции
в 4-й пункт распределения. В связи с дефицитом продукции за просрочку поставки
2 единиц продукции в 3-й пункт распределения будет выплачиваться штраф.
Задание 3:
Модель управления запасами
Уличный продавец покупает журналы у издательства по цене 20 руб. за
штуку, а продает по цене 28 руб. за штуку. Если товар не реализован, то
продавец возвращает его издательству по цене 9 руб. за штуку. Считаем, что
продавец реализует журналы пачками по 7 штук. Продавец заметил, что за отчетный
период он не реализовал ни одной пачки 5 раз, одну пачку - 11 раз, две пачки -
15 раз, три пачки - 18 раз, четыре пачки - 11 раз, пять пачек - 3 раза и при
этом более 5 пачек никогда не продавал.
Определить оптимальный объем закупки журналов, максимизирующий
оптимальную прибыль.
Решение
1. Вычислим вероятность событий реализации журналов, результаты
приведены в таблице
|
Объем продаж, шт
|
0
|
7
|
14
|
21
|
28
|
35
|
|
Число событий
|
5
|
11
|
15
|
18
|
11
|
3
|
|
Вероятность событий
|
0,08
|
0,24
|
0,28
|
0,17
|
0,05
|
2. Составим таблицу прибыли возможных событий реализации журналов
|
Продажа журналов
|
|
0
|
7
|
14
|
21
|
28
|
35
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
7
|
-77
|
56
|
56
|
56
|
56
|
56
|
|
14
|
-154
|
-21
|
112
|
112
|
112
|
112
|
|
покупка
|
21
|
-231
|
-98
|
35
|
168
|
168
|
168
|
|
28
|
-308
|
-175
|
-42
|
91
|
224
|
224
|
|
35
|
-385
|
-252
|
-119
|
14
|
147
|
280
|
3. Тогда прибыль с учетом вероятности для каждого варианта оптовой
закупки журналов можно рассчитать путем перемножения массивов прибыли возможных
событий реализации журналов (таблица 2) и вероятности событий реализации
журналов (таблица 1)
Выберем
максимальное значение из полученных результатов: 67,7 руб. Эта прибыль
соответствует событию закупки 14 журналов с вероятностью 0,24.
Ответ:
Оптимальный объем закупки, максимизирующий оптимальную прибыль - 14 журналов с
прибылью 67,7 руб.
Задание 4:
Задача о раскрое и минимизации отходов
Считая, что для раскроя используется стандартные рулоны шириной 30 футов,
определите все возможные варианты установки режущей кромки для получения
рулонов шириной 14, 16, 20 футов (14 - 200, 16 - 150, 20 - 250) и удовлетворите
заказ, минимизируя количество отходов.
Решение
1. Определим все возможные варианты разрезания рулона стандартной
ширины на нестандартные с помощью программы VBA:
|
|
14
|
16
|
20
|
остатки
|
|
Способы разрезания
|
1
|
0
|
0
|
1
|
10
|
1
|
1
|
0
|
0
|
|
3
|
2
|
0
|
0
|
2
|
2. Объявим
переменные , , равные количеству рулонов каждой ширины (14, 16 и 20
футов) для 1-го, 2-го и 3-го метода соответственно.
. Накладываем
ограничения на переменные
· 
;
· 
;
· 
4. Составим целевую функцию
· 
5. Вызываем окно надстройки «Поиск решения»
В результате получено значение целевой функции: 2550 футов2 , при
раскройке стандартных рулонов по 1 рулону шириной 20 футов получено 250 таких
рулонов (первый способ разрезания), при раскройке по 1 рулону шириной 14 футов
и 1 рулону шириной 16 футов - 150 и 150 соответственно (второй способ) и при
раскройке по 2 рулона шириной 14 футов - 50 рулонов шириной 14 футов (третий
способ).
Ответ:
Получено 3 возможных варианта установки режущей кромки
В результате минимизации количества отходов выяснили, что первым способом
нужно раскроить 250 стандартных рулонов по 20 футов, 150 стандартных рулонов по
14 футов и 150 по 16 - вторым способом, 50 стандартных рулонов по 14 футов -
третьим способом.
Задание 5:
Задача о назначениях
Имеются
k рабочих и m видов работ. Стоимость 
выполнения i-м рабочим j-й
работы приведена в таблице 1, где рабочему соответствует строка, а работе -
столбец. Необходимо составить план работ так, чтобы все работы были выполнены,
каждый рабочий был занят только на одной работе, а суммарная стоимость
выполнения всех работ была минимальной.
|
Стоимость выполнения работ
|
|
Рабочие
|
8
|
6
|
2
|
5
|
|
5
|
2
|
9
|
8
|
|
3
|
8
|
1
|
9
|
|
1
|
4
|
2
|
3
|
|
3
|
7
|
10
|
5
|
|
Виды работ
|
Решение
1. Из исходной таблицы видно, что количество рабочих больше количества
видов работ, поэтому введем фиктивную работу со стоимостью выполнения по 100
денежных единиц для каждого рабочего.
2. Составим
матрицу такую, что: если i-й рабочий
выполняет j-ю работу, то 
, если i-й
рабочий не выполняет j-ю работу, то 
.
. Составим
целевую функцию
4. Накладываем
ограничения на элементы матрицы
· 
;
· 
;
· 
5. Вызываем окно надстройки «Поиск решения»
6. В
результате получена матрица ,
приведенная в таблице
|
Вид работы
|
|
1
|
2
|
3
|
4
|
Фиктивная работа
|
|
рабочие
|
1
|
0
|
0
|
0
|
0
|
1
|
|
2
|
1
|
0
|
0
|
0
|
|
3
|
0
|
0
|
1
|
0
|
0
|
|
4
|
1
|
0
|
0
|
0
|
0
|
|
5
|
0
|
0
|
0
|
1
|
0
|
Можно сделать вывод, что фиктивную работу будет выполнять первый рабочий,
следовательно первый рабочий не будет выполнять никакой реальной работы.
Суммарная стоимость работ в этом случае составит 9 у.е.
Ответ: Для
минимизации суммарной стоимости работ необходимо, чтобы: первый рабочий не
выполнял никакую работу, второй рабочий - выполнял вторую работу, третий -
третью, четвертый - первую, и пятый рабочий - пятую работу.
Задание
6. Найдите минимум целевой функции 
при
указанных ограничениях
Решение
1. Объявим
переменные 
и 
.
. Для
заданной целевой функции 
и указанных ограничений найдем минимум функции с помощью надстройки «Поиск решения»
В
результате чего, получены значения переменных 
и 
и значение целевой функции 
.
Ответ:
Минимум целевой функции равен 8.
Задание 7:
Система нелинейных уравнений
Решить систему нелинейных уравнений
Решение
1. Объявим
переменные и .
. Составим
целевую функцию
3. Вычислим
значения целевой функции на промежутках 
:
В результате можем выделить две точки, в которых целевая функция
приблизительно равна 0: (0,6;-0,2) и (0;0,6). Выбор этих точек в дальнейшем
обеспечит точность решения задачи.
. Вызываем окно надстройки «Поиск решения» отдельно для первой и
для второй точки:
В результате получаем с высокой точностью искомые решения заданной
системы
|
x
|
y
|
f
|
|
-0,02398
|
0,706634
|
7,13E-10
|
|
0,587329
|
-0,3123
|
7,8E-08
|
5. Графическая интерпретация
Ответ:
Решению системы удовлетворяют точки: (-0,02398; 0,706634) и (0,587329; -0,3123)
функция управление
распределение уравнение
Задание 8:
Контрольная задача
Фирма производит 2 вида продукции: А и В. Объем сбыта продукции вида А
составляет не менее 60% общего объема реализации продукции обоих видов. Для
изготовления продукции А и В используется одно и то же сырье, суточный запас
которого ограничен величиной 100 фунтов. Расход сырья на единицу продукции В -
4 фунта, а А - 2 фунта. Цены продукции А и В равны 20 и 40 долларам
соответственно. Определите оптимальное распределение сырья для изготовления
продукции А и В.
Решение
1. Объявим
переменные и , равные
количеству производимой продукции вида А и вида В соответственно:
|
Вид продукции
|
Расход сырья, фунтов/ед.прод.
|
Цены, $/ед.прод.
|
Переменные
|
|
А
|
2
|
20
|
|
|
В
|
4
|
40
|
|
2. Накладываем
ограничения на переменные и
;
;
и ̶ целые.
3. Составим целевую функцию
4. Вызываем окно надстройки «Поиск решения»:
В результате получаем нужное количество производимой продукции вида А и
вида В для оптимального распределения сырья на изготовление продукции:
|
Вид продукции
|
Объемы производства
|
Распределение сырья
|
|
А
|
22
|
44
|
|
В
|
14
|
56
|
5. Графическая интерпретация задачи
Ответ:
Оптимальное распределение сырья для изготовления продукции вида А составляет 44
фунта, для изготовления продукции В - 56 фунтов.