Построение математических моделей при решении задач оптимизации - (реферат)
p>Выразив, например, переменную у через переменную х, получим:Так как х, у Є Z, то методом перебора легко найти соответствующие пары значений х и у, которые удовлетворяют уравнение 7х + 5у = 167. (1; 32), (6; 25), (11; 18), (16; 11), (21; 4).
Из этих решений наиболее выгодное последнее, т. е. х = 21, у = 4.
Задача 3 .
Для изготовления двух видов изделий Аи В завод расходует в качестве сырья сталь и цветные металлы, запас которых ограничен. На изготовление указанных изделий заняты токарные и фрезерные станки в количестве, указанном в таблице.
Таблица
Затраты на одно изделие
А
В
Ресурсы
Материалы
Сталь (кг)
10
70
320
Материалы
Цветные металлы (кг)
20
50
420
Оборудование
Токарные станки (станко-ч)
300
400
6200
Оборудование
Фрезерные станки (станко-ч)
200
100
3400
Прибыль на одно изделие (в тыс. руб. )
3
8
Необходимо определить план выпуска продукции, при котором будет достигнута максимальная прибыль, если время работы фрезерных станков используется полностью.
Решение.
Посмотрим математическую модель задачи. Обозначим через х число изделий вида А, а через у–число изделий вида В. На изготовление всей продукции уйдет (10 х +70у)кг стали и (20 х +50у) кг цветных металлов. Так как запасы стали не превышают 320 кг, а цветных металлов– 420 кг, то
10х +70у Ј 320
20х + 50у Ј 420
(300х +400у) ч – время обработки всех изделий на токарных станках: 300х + 400 Ј 6200
Учитывая, что фрезерные станки используются максимально, имеем: 200х +100у = 3400
Итак, система ограничений этой задачи есть:
10х + 70у Ј 320
20х + 50у Ј 420
300х + 400у Ј 6200 (1)
200х + 100у = 3400
х Ј 0, у Ј 0.
Общая прибыль фабрики может быть выражена целевой функцией
F = 3х + 8у. (2)
Выразим у через x из уравнения 200х + 100у = 3400 и подставим полученное выражение вместо у в неравенства и целевую функцию:
х +7(34 –2х) Ј 32
2х + 5(34 – 2х) Ј 42
3х + 4( 43 – 2х) Ј 62
у = 43 – 2х (3)
х і 0
34 – 2х і 0,
F = 3х + 8(34 – 2х) = -13+272 (4)
Преобразуем систему ограничений (3):
11
13х і 206 хі 5 13
8х і 218 х і 16
4
5х і 174 х Ј 4 5
16Ј х Ј 17
5х і 74 Ы 0 Ј х Ј 17 Ы у = 34 – 2х
0 Ј х Ј 17
у =34 - 2х у = 34 – 2х
Очевидно, что F =272 –3х принимает наибольшее значение, если х=16. Fнаиб = 272 – 13 * 16 – 64 (тыс. руб. )
Отдельно следует остановиться на случаях использования ЭВМ при решении задач оптимизации. Рассмотрим это на примере решения следующей задачи:
Задача 4.
В обработку поступила партия из 150 досок длиной по 7. 5 м. каждая, для изготовления комплектов из 4-х деталей. Комплект состоит из: 1 детали длиной 3 м.
2-х деталей длиной 2 м.
1 детали длиной 1. 5 м
Как распилить все доски, получив наибольшее возможное число комплектов? Решение.
Для решения этой задачи воспользуемся редактором электронных таблиц EXCEL Вводим в ячейки B3: D10 варианты возможного распила одной доски. В ячейках E3: E10 ставим по умолчанию количество досок по одной. В ячейках F3: H10 суммируем получившиеся распиленные детали.
Способы
3м
2м
1, 5м
Количество
3м
2м
1, 5м
1
2
0
1
1
2
0
1
2
0
3
1
1
0
3
1
3
0
0
5
1
0
0
5
4
1
0
3
1
1
0
3
5
1
2
0
1
1
2
0
6
0
2
2
1
0
2
2
7
1
1
1
1
1
1
1
8
0
1
3
1
0
1
3
8
5
9
16
1
23
11
В ячейках E11: H11 суммируем количество досок и деталей.
Вводим формулы:
G11 - ABS(2*F11-G11)
G12 - ABS(G11-2*H11)
G13 - ABS(F11-H11)
Входим во встроенную функцию EXCEL Поиск Решения
Устанавливаем Целевую ячейку E11
Ставим ограничения:
E3: E10=>0
E3: E10= ЦЕЛЫЕ
G12 G13 G14 Даем команду Выполнить
Машина выдает разультаты
Способы
3м
2м
1, 5м
Количество
3м
2м
1, 5м
1
2
0
1
34
68
0
34
2
0
3
1
33
0
99
33
3
0
0
5
0
0
0
0
4
1
0
3
0
0
0
0
5
1
2
0
47
47
94
0
6
0
2
2
24
0
48
48
7
1
1
1
12
12
12
12
8
0
1
3
0
0
0
0
150
127
253
127
1
1