Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сочинский государственный университет»

Филиал ФГ БОУ ВПО «Сочинский государственный университет»

в г. Нижний Новгород Нижегородской области

Факультет менеджмент организации

Кафедра Экономики и туризма

Дисциплина Теория оптимального управления

Контрольная работа

Выполнила студентка 5 курса ЗФО

Форма обучения

Группа М-53-09 УП

Комарова А.Н.

Нижний Новгород 2013г.

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

компактно записаны в виде

c₁ c₂ c₃ c₄

а₁₁ а₁₂ а₁₃ а₁₄ b₁

a₂₁ a₂₂ a₂₃ a₂₄ b₂

a₃₁ a₃₂ a₃₃ a₃₄ b₃

34 32 28 36

2 4 5 3 128

3 0 4 1 130

3 5 0 2 142

Определим максимальное значение целевой функции F(X) = 34x₁ + 32x₂ + 28x₃ + 36x₄ при следующих условиях-ограничениях.

2x₁ + 4x₂ + 5x₃ + 3x₄?128

3x₁ + 4x₃ + x₄?130

3x₁ + 5x₂ + 2x₄?142

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x₅. В 2-м неравенстве смысла (?) вводим базисную переменную x₆. В 3-м неравенстве смысла (?) вводим базисную переменную x₇.

2x₁ + 4x₂ + 5x₃ + 3x₄ + 1x₅ + 0x₆ + 0x₇ = 128

3x₁ + 0x₂ + 4x₃ + 1x₄ + 0x₅ + 1x₆ + 0x₇ = 130

3x₁ + 5x₂ + 0x₃ + 2x₄ + 0x₅ + 0x₆ + 1x₇ = 142

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Таблица 1

2	4	5	3	1	0	0
3	0	4	1	0	1	0
3	5	0	2	0	0	1

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

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x₅, x₆, x₇,

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,128,130,142)

Базисное решение называется допустимым, если оно неотрицательно.

Таблица 2

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	128	2	4	5	3	1	0	0
x6	130	3	0	4	1	0	1	0
x7	142	3	5	0	2	0	0	1
F(X0)	0	-34	-32	-28	-36	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i4 и из них выберем наименьшее:

min (128 : 3 , 130 : 1 , 142 : 2 ) = 42²/₃

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 3

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x5	128	2	4	5	3	1	0	0	422/3
x6	130	3	0	4	1	0	1	0	130
x7	142	3	5	0	2	0	0	1	71
F(X1)	0	-34	-32	-28	-36	0	0	0	0

симплексный транспортный программирование

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 1 войдет переменная x₄.

Строка, соответствующая переменной x₄ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₄ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₄ и столбец x₄.

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

Таблица 4

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	422/3	2/3	11/3	12/3	1	1/3	0	0
x6	871/3	21/3	-11/3	21/3	0	-1/3	1	0
x7	562/3	12/3	21/3	-31/3	0	-2/3	0	1
F(X1)	1536	-10	16	32	0	12	0	0

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

min (42²/₃ : ²/₃ , 87¹/₃ : 2¹/₃ , 56²/₃ : 1²/₃ ) = 34

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (1²/₃) и находится на пересечении ведущего столбца и ведущей строки.

симплексный оптимальность транспортный программирование

Таблица 5

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	422/3	2/3	11/3	12/3	1	1/3	0	0	64
x6	871/3	21/3	-11/3	21/3	0	-1/3	1	0	373/7
x7	562/3	12/3	21/3	-31/3	0	-2/3	0	1	34
F(X2)	1536	-10	16	32	0	12	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₇ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₇ плана 1 на разрешающий элемент РЭ=1²/₃

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.

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

Таблица 6

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	20	0	2/5	3	1	3/5	0	-2/5
x6	8	0	-43/5	7	0	3/5	1	-12/5
x1	34	1	12/5	-2	0	-2/5	0	3/5
F(X2)	1876	0	30	12	0	8	0	6

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Таблица 7

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	20	0	2/5	3	1	3/5	0	-2/5
x6	8	0	-43/5	7	0	3/5	1	-12/5
x1	34	1	12/5	-2	0	-2/5	0	3/5
F(X3)	1876	0	30	12	0	8	0	6

Оптимальный план можно записать так:

x₄ = 20

x₁ = 34

F(X) = 36*20 + 34*34 = 1876

2. Решить транспортную задачу линейного программирования

Математическая модель транспортной задачи:

F = ??c_ijx_ij, (1)

при условиях:

?x_ij = a_i, i = 1,2,…, m, (2)

?x_ij = b_j, j = 1,2,…, n, (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

Таблица 8

	1	2	3	4	Запасы
1	3	6	4	3	40
2	2	3	1	3	45
3	6	5	1	4	70
Потребности	48	30	29	40

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 40 + 45 + 70 = 155

?b = 48 + 30 + 29 + 40 = 147

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 8 (155--147). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

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

Таблица 9

	1	2	3	4	5	Запасы
1	3	6	4	3	0	40
2	2	3	1	3	0	45
3	6	5	1	4	0	70
Потребности	48	30	29	40	8

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

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

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

Искомый элемент равен 1

Для этого элемента запасы равны 45, потребности 29. Поскольку минимальным является 29, то вычитаем его.

x₂₃ = min(45,29) = 29.

Таблица 10

3	6	x	3	0	40
2	3	1	3	0	45 - 29 = 16
6	5	x	4	0	70
48	30	29 - 29 = 0	40	8	0

Искомый элемент равен 2

Для этого элемента запасы равны 16, потребности 48. Поскольку минимальным является 16, то вычитаем его.

x₂₁ = min(16,48) = 16.

Таблица 11

3	6	x	3	0	40
2	x	1	x	x	16 - 16 = 0
6	5	x	4	0	70
48 - 16 = 32	30	0	40	8	0

Искомый элемент равен 3

Для этого элемента запасы равны 40, потребности 32. Поскольку минимальным является 32, то вычитаем его.

x₁₁ = min(40,32) = 32.

Таблица 12

3	6	x	3	0	40 - 32 = 8
2	x	1	x	x	0
x	5	x	4	0	70
32 - 32 = 0	30	0	40	8	0

Искомый элемент равен 3

Для этого элемента запасы равны 8, потребности 40. Поскольку минимальным является 8, то вычитаем его.

x₁₄ = min(8,40) = 8.

Таблица 13

3	x	x	3	x	8 - 8 = 0
2	x	1	x	x	0
x	5	x	4	0	70
0	30	0	40 - 8 = 32	8	0

Искомый элемент равен 4

Для этого элемента запасы равны 70, потребности 32. Поскольку минимальным является 32, то вычитаем его.

x₃₄ = min(70,32) = 32.

Таблица 14

3	x	x	3	x	0
2	x	1	x	x	0
x	5	x	4	0	70 - 32 = 38
0	30	0	32 - 32 = 0	8	0

Искомый элемент равен 5

Для этого элемента запасы равны 38, потребности 30. Поскольку минимальным является 30, то вычитаем его.

x₃₂ = min(38,30) = 30.

Таблица 15

3	x	x	3	x	0
2	x	1	x	x	0
x	5	x	4	0	38 - 30 = 8
0	30 - 30 = 0	0	0	8	0

Искомый элемент равен 0

Для этого элемента запасы равны 8, потребности 8. Поскольку минимальным является 8, то вычитаем его.

x₃₅ = min(8,8) = 8.

Таблица 16

3	x	x	3	x	0
2	x	1	x	x	0
x	5	x	4	0	8 - 8 = 0
0	0	0	0	8 - 8 = 0	0

Таблица 17

	1	2	3	4	5	Запасы
1	3[32]	6	4	3[8]	0	40
2	2[16]	3	1[29]	3	0	45
3	6	5[30]	1	4[32]	0[8]	70
Потребности	48	30	29	40	8

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*32 + 3*8 + 2*16 + 1*29 + 5*30 + 4*32 + 0*8 = 459

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₂ + v₁ = 2; 3 + u₂ = 2; u₂ = -1

u₂ + v₃ = 1; -1 + v₃ = 1; v₃ = 2

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₃ + v₄ = 4; 3 + u₃ = 4; u₃ = 1

u₃ + v₂ = 5; 1 + v₂ = 5; v₂ = 4

u₃ + v₅ = 0; 1 + v₅ = 0; v₅ = -1

Таблица 18

	v1=3	v2=4	v3=2	v4=3	v5=-1
u1=0	3[32]	6	4	3[8]	0
u2=-1	2[16]	3	1[29]	3	0
u3=1	6	5[30]	1	4[32]	0[8]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(3;3): 1 + 2 > 1; ?₃₃ = 1 + 2 - 1 = 2

Выбираем максимальную оценку свободной клетки (3;3): 1

Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 19

	1	2	3	4	5	Запасы
1	3[32][-]	6	4	3[8][+]	0	40
2	2[16][+]	3	1[29][-]	3	0	45
3	6	5[30]	1[+]	4[32][-]	0[8]	70
Потребности	48	30	29	40	8

Цикл приведен в таблице (3,3; 3,4; 1,4; 1,1; 2,1; 2,3; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 29. Прибавляем 29 к объемам грузов, стоящих в плюсовых клетках и вычитаем 29 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 20

	1	2	3	4	5	Запасы
1	3[3]	6	4	3[37]	0	40
2	2[45]	3	1	3	0	45
3	6	5[30]	1[29]	4[3]	0[8]	70
Потребности	48	30	29	40	8

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₂ + v₁ = 2; 3 + u₂ = 2; u₂ = -1

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₃ + v₄ = 4; 3 + u₃ = 4; u₃ = 1

u₃ + v₂ = 5; 1 + v₂ = 5; v₂ = 4

u₃ + v₃ = 1; 1 + v₃ = 1; v₃ = 0

u₃ + v₅ = 0; 1 + v₅ = 0; v₅ = -1

Таблица 21

	v1=3	v2=4	v3=0	v4=3	v5=-1
u1=0	3[3]	6	4	3[37]	0
u2=-1	2[45]	3	1	3	0
u3=1	6	5[30]	1[29]	4[3]	0[8]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 3*3 + 3*37 + 2*45 + 5*30 + 1*29 + 4*3 + 0*8 = 401

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (3), в 4-й магазин (37)

Из 2-го склада необходимо весь груз направить в 1-й магазин

Из 3-го склада необходимо груз направить в 2-й магазин (30), в 3-й магазин (29), в 4-й магазин (3)

На 3-ом складе остался невостребованным груз в количестве 8 ед.

Оптимальный план является вырожденным, так как базисная переменная x₃₅=0.

Задача имеет множество оптимальных планов, поскольку оценка для (2;2) равна 0.

3. Решить задачу о распределении ресурсов. Необходимо распределить 500 ден. ед. на три предприятия, прибыль приведена в таблице.

Таблица 22

хj	0 100 200 300 400 500
h1 (xj)	0 20 44 55 63 67
h2 (xj)	0 18 29 49 72 87
h3 (xj)	0 25 41 52 74 82

Таблица 23 Исходные данные

f1	f2	f3	xi
0	0	0	0
20	18	25	100
44	29	41	200
55	49	52	300
63	72	87	82
67	87	82	500

I этап. Условная оптимизация.

1-ый шаг. k = 3.

Таблица 24

e2	u3	e3 = e2 - u3	f3(u3)	F*3(e3)	u3(e3)
100	0	100	0
	100	0	25	25	100
200	0	200	0
	100	100	25
	200	0	41	41	200
300	0	300	0
	100	200	25
	200	100	41
	300	0	52	52	300
82	0	82	0
	100	-18	25
	200	-118	41
	300	-218	52
	82	0	87	87	82
500	0	500	0
	100	400	25
	200	300	41
	300	200	52
	82	418	87	87	82
	500	0	82

2-ый шаг. k = 2.

Таблица 25

e1	u2	e2 = e1 - u2	f2(u2)	F*2(e1)	F1(u2,e1)	F*2(e2)	u2(e2)
100	0	100	0	25	25	25	0
	100	0	18	0	18
200	0	200	0	41	41
	100	100	18	25	43	43	100
	200	0	29	0	29
300	0	300	0	52	52
	100	200	18	41	59	59	100
	200	100	29	25	54
	300	0	49	0	49
82	0	82	0	87	87	87	0
	100	-18	18	52	70
	200	-118	29	41	70
	300	-218	49	25	74
	82	0	72	0	72
500	0	500	0	87	87
	100	400	18	87	105	105	100
	200	300	29	52	81
	300	200	49	41	90
	82	418	72	25	97
	500	0	87	0	87

3-ый шаг. k = 1.

Таблица 26

e0	u1	e1 = e0 - u1	f1(u1)	F*1(e0)	F0(u1,e0)	F*1(e1)	u1(e1)
100	0	100	0	25	25	25	0
	100	0	20	0	20
200	0	200	0	43	43
	100	100	20	25	45	45	100
	200	0	44	0	44
300	0	300	0	59	59
	100	200	20	43	63
	200	100	44	25	69	69	200
	300	0	55	0	55
82	0	82	0	87	87	87	0
	100	-18	20	59	79
	200	-118	44	43	87
	300	-218	55	25	80
	82	0	63	0	63
500	0	500	0	105	105
	100	400	20	87	107	107	100
	200	300	44	59	103
	300	200	55	43	98
	82	418	63	25	88
	500	0	67	0	67

Поясним построение таблиц и последовательность проведения расчетов.

Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).

В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.

Из таблицы 3-го шага имеем F*₁(e⁰ = 500) = 107. То есть максимальный доход всей системы при количестве средств e⁰ = 500 равен 107

Из этой же таблицы получаем, что 1-му предприятию следует выделить u*₁(e⁰ = 500) = 100

При этом остаток средств составит: e¹ = e⁰ - u¹

e¹ = 500 - 100 = 400

Из таблицы 2-го шага имеем F*₂(e¹ = 400) = . То есть максимальный доход всей системы при количестве средств e¹ = 400 равен

Из этой же таблицы получаем, что 2-му предприятию следует выделить u*₂(e¹ = 400) = 0

При этом остаток средств составит: e² = e¹ - u²

e² = 400 - 0 = 400

Последнему предприятию достается 400

Итак, инвестиции в размере 500 необходимо распределить следующим образом:

1-му предприятию выделить 100

2-му предприятию выделить 0

3-му предприятию выделить 400

Что обеспечит максимальный доход, равный 107

Размещено на Allbest.ru

...