Задача на оптимизацию - файл n1.doc

приобрести
Задача на оптимизацию
скачать (159 kb.)
Доступные файлы (1):

159kb.

05.06.2012 06:51

n1.doc

Задача

Предприятие выпускает продукцию двух типов П₁ и П₂

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

Прибыль от реализации продукции типа П₁ составляет Д₁ денежных единиц, а прибыль от реализации продукции типа П₂составляет Д₂ денежных единиц.

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей.

Вид сырья	Запас сырья	Расходы на единицу продукции		Прибыль от реализации
Вид сырья	Запас сырья	П₁	П₂	Д₁	Д₂
1	20	1	4	3	3
2	40	0	1
3	11	1	1
4	10	1	0

Эту задачу можно представить так:

Сырье	Норма расхода сырья на единицу изделия		Запасы сырья
Сырье	П₁	П₁	Запасы сырья
1	1	4	20
2	0	1	40
3	1	1	11
4	1	0	10
Прибыль от реализации единицы изделия в д.е. (Д)	3	3

1. Математическая модель задачи

аксимизировать: Z = 3 x + 3 у при выполнении условий:

x+ 4 у ≤ 20

у ≤ 40

x + у ≤ 11

x ≤ 10

x, у ≥ 0

можно было взять х₁; х₂тогда:

М

аксимизировать: Z = 3x₁ + 3 х₂ при выполнении условий:

x₁ + 4 x₂ ≤ 20

x₂ ≤ 40

x₁ + x₂ ≤ 11

x₁ ≤ 10

x₁ , x₂ ≥ 0

2. Построение пространства допустимых решений

) x+ 4 у = 20

x= 0 у = 0

у = 5 x= 20
2) у = 40

х=0, у =40

3) x + у =11
x

= 0 x= 11

у = 11 у = 0
3) x =10

x= 10

у = 0

3. Решение задачи графически

На основании полученных данных строим график.

У
20
18
16
14
12
10
8
6 В					А
4
2							С
0	2	4	6	8	10	12	14	16	14	18	20	22	24	26	28	30	32	34	36	38	40	42	Х

По графику у =3; х = 8

Проверяем:

(*) А – точка пересечения прямых (1) и (3):

1) x+ 4 у = 20

3) x + у =11

Вычтем из уравнения (1) уравнение (3):

3у = 9 → у = 3; тогда х = 8

Полученные значения должны удовлетворять условиям

x+ 4 у ≤ 20

у ≤ 40

x + у ≤ 11

x ≤ 10

x, у ≥ 0

проверяем:

8 + 4* 3 =20 ≤ 20

3 ≤ 40

8 + 3 = ≤ 11

8 ≤ 10

Область допустимых решений – пространство, ограниченное ломаной ОВАС. Любая точка, расположенная внутри или на границе области является допустимым решением, т.е. удовлетворяет всем ограничениям.

4. Нахождение оптимального решения

Максимум функции может находиться в вершинах многоугольника ОАВС.

1) Проверим точки А, В, С на оптимальность:

Точка А (8; 3)

Z = 3 x + 3 у =3*8 + 3*3 = 33 д.е. →max

Точка В (0; 5)

Z = 3 x + 3 у =3*0 + 3*5= 15 д.е.

Точка С (11; 0)

Z = 3 x + 3 у =3*11 + 3*0 = 33 д.е. →max

5. Решение задачи симплекс-методом

x+ 4 у ≤ 20

у ≤ 40

x + у ≤ 11

x ≤ 10

x, у ≥ 0

Z = 3x + 3у +0x₂ + 0x₃ + 0x₄ + 0 х₅

при ограничениях:

x+ 4 у + x₂= 20

у + x₃= 40

x + у + x₄= 11

x + x₅= 10

Z - 3x – 3у = 0

Базис	Z	x	у	x₂	x₃	x₄	x₅	Решение	Отношение
Z	1	-3	-3	0	0	0	0	0	-
x₂	0	1	4	1	0	0	0	20	:1= 20
x₃	0	0	1	0	1	0	0	40	:0=∞
x₄	0	1	1	0	0	1	0	11	:1=11
x₅	0	1	0	0	0	0	1	10	:1 =10

ведущая строка

ведущий столбец

Обычно выбирают ведущим тот столбец, где значение минимально, в нашем случае минимальное значение (-3).

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

Таким образом, 1 – ведущий элемент.

Процесс вычисления нового базисного решения основан на методе Гаусса-Жордана, и состоит из двух этапов.

Вычисление элементов новой ведущей строки.

Новая ведущая строка = Текущая строка/ Ведущий элемент.

Вычисление элементов остальных строк, включая Z- строку.

Новая строка = Текущая строка – Ее коэффициент в ведущем столбце* Новая ведущая строка.

Поэтому сначала ведущую строку делим на ведущий элемент:

Новая ведущая строка:

Например:

Текущая Z- строка:	1	-3	-3	0	0
Новая ведущая строка:	0	1	0	1	10
(-3)* Новая ведущая строка:	0	-3	0	-3	-30
(стр.1-стр 3)=Новая Z- строка:	1	0	-3	3	30

Так же с остальными строками:

x₂	1	4	1	0	20
Новая ведущая строка:	1	0	0	1	10
(1)* Новая ведущая строка:	1	0	0	1	10
(стр.1-стр 3)=Новая x₂- строка:	0	4	1	- 1	10

x₃	0	1	1	0	40
Новая ведущая строка:	1	0	0	1	10
(0)* Новая ведущая строка:	0	0	0	0	0
(стр.1-стр 3)=Новая x₃- строка:	0	1	1	0	40

x₄	1	1	1	0	11
Новая ведущая строка:	1	0	0	1	10
(1)* Новая ведущая строка:	1	0	0	1	10
(стр.1-стр 3)=Новая x₄- строка:	0	1	1	0	1

Новое базисное решение:

Так как в Z- строке есть отрицательная величина, то полученное решение не оптимально.

Базис	Z	x	у	x₂	x₃	x₄	x₅	Решение	Отношение
Z	1	0	-3	0	0	0	3	30
х₂	0	0	4	1	0	0	- 1	10	: 4=2,5
x₃	0	0	1	0	1	0	0	40	: 1= 40
x₄	0	0	1	0	0	1	0	1	: 1 =1
х	0	1	0	0	0	0	1	10	:0 = ∞

ведущий столбец

ведущая строка

Новая ведущая строка: у встает на место x₄

Текущая Z- строка:	1	-3	0	3	30
Новая ведущая строка:	0	1	1	0	1
(-3)* Новая ведущая строка:	0	-3	-3	0	-3
(стр.1-стр 3)=Новая Z- строка:	1	0	3	3	33

х₂	4	1	0	- 1	10
Новая ведущая строка:	1	0	1	0	1
(4)* Новая ведущая строка:	4	0	4	0	4
(стр.1-стр 3)=Новая x₂- строка:	0	1	-4	- 1	6

x₃	1	1	0	40
Новая ведущая строка:	1	0	1	1
(1)* Новая ведущая строка:	1	0	1	1
(стр.1-стр 3)=Новая x₃- строка:	0	1	-1	39

х	1	0	0	1	10
Новая ведущая строка:	0	1	1	0	1
(0)* Новая ведущая строка:	0	0	0	0	0
(стр.1-стр 3)=Новая x- строка:	1	0	0	1	10

В итоге получаем:

Базис	Z	x	у	x₂	x₃	x₄	x₅	Решение
Z	1	0	0	0	0	3	3	33
х₂	0	0	0	1	0	-4	- 1	6
x₃	0	0	0	0	1	-1	0	39
у	0	0	1	0	0	1	0	1
х	0	1	0	0	0	0	1	10

Поскольку Z- строка не имеет отрицательных элементов, полученное решение оптимально.

Z = 33 д.е.

При х = 10, у =1

Данное решение входит в область допустимых значений.