Контрольная работа по "Методам принятия оптимальных решений"

Задание 1

Решить  графически: maxF=2x₁+4x₂;

3x₁+6x₂≤12

2x₁-x₂≥-2

-x₁+3x₂≥0

 

x₁≥0, x₂≥0

 

Решение:

Строим прямые по уравнениям:

 

3x₁+6x₂=12

2x₁-x₂=-2

-x₁+3x₂=0

x₁=0

 x₂=0

    x₂

                      2x₁-x₂=-2

  4

  C

 

    3

 

  2        A   3x₁+6x₂=12

    1

 B

 x₁

      1              2              3              4

 

Целевая функция принимает максимальное значение в любой точке отрезка  АВ.

Fmax=8

 

Задание 2

 

Для производства 4-х видов продукции  используется 3 вида сырья. Нормы расхода  сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

Составим план выпуска продукции, обеспечивающий получение максимальной прибыли, используя симплексный  метод, а также построить двойственную задачу и решить ее симплекс-методом.

 

	Нормы расхода ресурсов на единичное  изделие				Запас ресурсов
	Изделие 1	Изделие 2	Изделие 3	Изделие 4
Ресурс 1	4	6	8	10	72
Ресурс 2	10	3	5	9	90
Ресурс 3	1	5	7	2	50
Ценность	5	7	3	8

 

Решение:

 

Fmax=5x₁+7x₂+3x₃+8x₄

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

4x₁+6x₂+8x₃+10x₄≤72

10x₁+3x₂+5x₃+9x₄≤90

x₁+5x₂+7x₃+2x₄≤50

 

Приведем систему неравенств к  системе уравнений путем введения дополнительных переменных:

4x₁+6x₂+8x₃+10x4+x₅=72

10x₁+3x₂+5x₃+9x₄+x₆=90

x₁+5x₂+7x₃+2x₄+x₇=50

 

Запишем преобразованную систему  уравнений в векторной форме:

x₁*P₁+x₂*P₂+x₃*P₃+x₄*P₄+x₅*P₅+x₆*P₆+x₇*P₇=P₀, где

P₁=   ; P₂=;  P₃=   ; P₄= ; P₅=  ; P₆=  ; P₇=  ; P₀=

 

Опорный план: X=(0;0;0;72;90;50)

 

Таблица I итерации:

Базис	P0	x1	x2	x3	x4	x5	x6	x7
x5	72	4	6	8	10	1	0	0
x6	90	10	3	5	9	0	1	0
x7	50	1	5	7	2	0	0	1
zj-cj	0	-5	-7	-3	-8	0	0	0

 

Опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец  X₄, так как это больший коэффициент по модулю.

Определим вектор подлежащий исключению из базиса:

Ѳ₀=min(72/10; 90/9; 50/2;)=72/10=7.2

Следовательно, первая строка является ведущей. Разрешающий элемент равен 10.

Получаем новую симплекс таблицу:

Итерация II

Базис	P0	x1	x2	x3	x4	x5	x6	x7
X4	7,2	0,4	0,6	0,8	1	0,1	0	0
x6	25,5	6,4	-2,4	-2,2	0	-0,9	1	0
x7	35,6	0,2	3,8	5,4	0	-0,2	0	1
zj-cj	57,6	-1,8	-2,2	3,4	0	0,8	0	0

 

Текущий опорный план неоптимален.

Ведущий столбец – x₂

Ѳ₀=min(7.2/0.6; 25.5/-2.4; 35.6/3.8)=35.6/3.8=9

Третья строка является ведущей. Разрешающий  элемент - 3,8.

 

Итерация  III

 

Базис	P0	x1	x2	x3	x4	x5	x6	x7
x4	1		0	-	1		0	-
x6	47	6	0	1	0	-1	1
x2	9		1	1	0	-	0
zj-cj	78	-1,	0	6	0		0

Текущий опорный план неоптимален.

Ведущий столбец – x₁

Ѳ₀=min=1 / = 4

Первая строка является ведущей. Разрешающий  элемент - 

 

Итерация  IV

 

Базис	P0	x1	x2	x3	x4	x5	x6	x7
x1	4	1	0	-	2		0	-
x6	19	0	0	2	-17	-3	1	3
x2	9	0	1	1	-	-	0
zj-cj	85	0	0	6	4	1	0	-

Текущий опорный  план неоптимален.

Ведущий столбец  – x₇

Ѳ₀=min=19/3=5

Разрешающий элемент равен 3

Базис	P0	x1	x2	x3	x4	x5	x6	x7
x1	6	1	0			-		0
x7	5	0	0		-5	-		1
x2	7	0	1	1	1		-	0
zj-cj	86	0	0	6	3	1		0

Индексная строка не содержит отрицательных элементов. Найден оптимальный план.

x₁=6

x₂=7

Fmax=5*6+7*7=86

 

Двойственная  задача:

 

Составим  двойственную задачу к прямой задаче:

4y₁+10y₂+y₃≥5

6y₁+3y₂+5y₃≥7

8y₁+5y₂+7y₃≥3

10y₁+9y₂+2y₃≥8

72y₁+90y₂+50y₃→min

y₁≥0; y₂≥0; y₃≥0

Приведем  систему ограничений к системе  неравенств смысла ≤ , умножив соответствующие строки на (-1)

-4x₁-10x₂-x₃≤-5

-6x₁-3x₂-5x₃≤-7

-8x₁-5x₂-7x₃≤-3

-10x₁-9x₂-2x₃≤-8

F(min)=72x₁+90x₂+50x₃

Приведем систему неравенств к  системе уравнений путем введения дополнительных переменных:

-4x₁-10x₂-x₃+x₄=-5

-6x₁-3x₂-5x₃+x₅=-7

-8x₁-5x₂-7x₃+x₆=-3

-10x₁-9x₂-2x₃+x₇=-8

Матрица коэффициентов  этой системы имеет вид:

 

-4	-10	-1	1	0	0	0
-6	-3	-5	0	1	0	0
-8	-5	-7	0	0	1	0
-10	-9	-2	0	0	0	1

 

Полагая что свободные переменные равны 0, получим первый опорный план:

X=(0,0,0,-5,-7,-3,-8)

 

Базис	Р0	x1	x2	x3	x4	x5	x6	x7
x4	-5	-4	-10	-1	1	0	0	0
x5	-7	-6	-3	-5	0	1	0	0
x6	-3	-8	-5	-7	0	0	1	0
x7	-8	-10	-9	-2	0	0	0	1
F(X)	0	-72	-90	-50	0	0	0	0

 

План в  симплексной таблице является псевдопланом.

Ведущая строка – x₇

Ведущий столбец  – x₁

Разрешающий элемент: -10

 

Выполняем преобразования симплексной таблицы методом  Жордано-Гаусса.

Итерация  I

Базис	Р0	x1	x2	x3	x4	x5	x6	x7
x4	-1	0	-6	-	1	0	0	-
x5	-2	0	2	-3	0	1	0	-
x6	3	0	2	-5	0	0	1	-
X1		1			0	0	0	-
F(X)	57	0	-25	-35	0	0	0	-7

 

План в  симплексной таблице является псевдопланом, так как в базисном столбце имеются отрицательные элементы.

 

Ведущая строка – x₅

Ведущий столбец  – x₃

Разрешающий элемент: -3

 

Итерация  II

 

 

 

 

Базис	Р0	x1	x2	x3	x4	x5	x6	x7
x4	-1	0	-6	0	1	-	0	-
x3		0	-	1	0	-	0
x6	6	0	-1	0	0	-1	1
x1		1	1	0	0		0	-
F(X)	78	0	-47	0	0	-9	0	-1

План является псевдопланом.

Ведущая строка – х₄

Ведущий столбец  – х₇

Разрешающий элемент: -

 

Итерация  III

Базис	Р0	x1	x2	x3	x4	x5	x6	x7
x7	4	0	17	0	-2		0	1
x3	-	0	-	1		-	0	0
x6	6	0	-2	0		-1	1	0
x1	1	1	3	0	-		0	0
F(X)	85	0	-19	0	-4	-9	0	0

План является псевдопланом.

 

Ведущая строка – х₃

Ведущий столбец  – х₂

Разрешающий элемент: -

 

Итерация  IV

Базис	Р0	x1	x2	x3	x4	x5	x6	x7
x7	3	0	0	5	-	-1	0	1
x2		0	1	-	-		0	0
x6	6	0	0	-	-	-1	1	0
x1	1	1	0			-	0	0
F(X)	86	0	0	-5	-6	-7	0	0