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

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

n1.doc

Задача

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

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

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

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

Вид сырья

Запас сырья

Расходы на единицу продукции

Прибыль от реализации

П1

П2

Д1

Д2

1

20

1

4


3


3

2

40

0

1

3

11

1

1

4

10

1

0


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

Сырье

Норма расхода сырья на единицу изделия

Запасы сырья

П1

П1

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

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

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

x1 + 4 x2 ≤ 20

x2 ≤ 40

x1 + x2 ≤ 11

x1 ≤ 10

x1 , x2 ≥ 0

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


1) 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у +0x2 + 0x3 + 0x4 + 0 х5

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

x+ 4 у + x2 = 20

у + x3= 40

x + у + x4= 11

x + x5 = 10

Z - 3x – 3у = 0

Базис

Z

x

у

x2

x3

x4

x5

Решение

Отношение

Z

1

-3

-3

0

0

0

0

0

-

x2

0

1

4

1

0

0

0

20

:1= 20

x3

0

0

1

0

1

0

0

40

:0=∞

x4

0

1

1

0

0

1

0

11

:1=11

x5

0

1

0

0

0

0

1

10

:1 =10


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


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


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

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

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

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


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

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

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

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

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


0

1

0

0

0

0

1

10


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

0

1

0

0

0

0

1

10


Например:

Текущая Z- строка:

1

-3

-3

0

0

0

0

0

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

0

1

0

0

0

0

1

10

(-3)* Новая ведущая строка:

0

-3

0

0

0

0

-3

-30

(стр.1-стр 3)=Новая Z- строка:

1

0

-3

0

0

0

3

30


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


x2

0

1

4

1

0

0

0

20

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

0

1

0

0

0

0

1

10

(1)* Новая ведущая строка:

0

1

0

0

0

0

1

10

(стр.1-стр 3)=Новая x2- строка:

0

0

4

1

0

0

- 1

10



x3

0

0

1

0

1

0

0

40

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

0

1

0

0

0

0

1

10

(0)* Новая ведущая строка:

0

0

0

0

0

0

0

0

(стр.1-стр 3)=Новая x3- строка:

0

0

1

0

1

0

0

40



x4

0

1

1

0

0

1

0

11

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

0

1

0

0

0

0

1

10

(1)* Новая ведущая строка:

0

1

0

0

0

0

1

10

(стр.1-стр 3)=Новая x4- строка:

0

0

1

0

0

1

0

1



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

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

Базис

Z

x

у

x2

x3

x4

x5

Решение

Отношение

Z

1

0

-3

0

0

0

3

30




х2

0

0

4

1

0

0

- 1

10

: 4=2,5

x3

0

0

1

0

1

0

0

40

: 1= 40

x4

0

0

1

0

0

1

0

1

: 1 =1

х

0

1

0

0

0

0

1

10

:0 = ∞



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

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


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

у

0

0

1

0

0

1

0

1




Текущая Z- строка:

1

0

-3

0

0

0

3

30

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

0

0

1

0

0

1

0

1

(-3)* Новая ведущая строка:

0

0

-3

0

0

-3

0

-3

(стр.1-стр 3)=Новая Z- строка:

1

0

0

0

0

3

3

33




х2

0

0

4

1

0

0

- 1

10

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

0

0

1

0

0

1

0

1

(4)* Новая ведущая строка:

0

0

4

0

0

4

0

4

(стр.1-стр 3)=Новая x2- строка:

0

0

0

1

0

-4

- 1

6




x3

0

0

1

0

1

0

0

40

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

0

0

1

0

0

1

0

1

(1)* Новая ведущая строка:

0

0

1

0

0

1

0

1

(стр.1-стр 3)=Новая x3- строка:

0

0

0

0

1

-1

0

39




х

0

1

0

0

0

0

1

10

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

0

0

1

0

0

1

0

1

(0)* Новая ведущая строка:

0

0

0

0

0

0

0

0

(стр.1-стр 3)=Новая x- строка:

0

1

0

0

0

0

1

10


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

Базис

Z

x

у

x2

x3

x4

x5

Решение

Z

1

0

0

0

0

3

3

33

х2

0

0

0

1

0

-4

- 1

6

x3

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

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

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации