База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

курсовые,контрольные,дипломы,рефераты

Исследование операций — Информатика, программирование

Министерство образования и науки Российской Федерации

Южно-Уральский государственный университет

Кафедра системы управления

Курсовая работа

по дисциплине: исследование операций

Вариант 9

Челябинск

2004 г.
Содержание

Задание 1 3

Задание 2 6

Задание 3 9

Задание 4 11

Литература 17

Задание 1

Задача 9

Условие:

Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.

Вещество	Количество единиц вещества, содержащегося в 1 кг сырья
Вещество	1	2	3
А	d₁₁	d₁₂	d₁₃
В	d₂₁	d₂₂	d₂₃
С	d₃₁	d₃₂	d₃₃
Цена 1 кг сырья	D₁	D₂	D₃

№ вар.	d₁₁	d₁₂	d₁₃	d₂₁	d₂₂	d₂₃	d₃₁	d₃₂	d₃₃
9	1	1	0	2	0	3	1	2	4

D₁	D₂	D₃	а	b	c
5	6	7	26	30	24

Решение:

Составим математическую модель задачи.

Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно.

Тогда, целевая функция будет

L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 →min

Система ограничений:

_ EMBED Equation.3 ___

Приведем систему ограничений к виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L', и новые переменные n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.

L’=0-(5n1+ 6n2+7n3) →max

_ EMBED Equation.3 ___

Выберем n1, n2, n3 свободными переменными, а n4, n5, n6 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:

L’=0-(5n1+ 6n2+7n3)

_ EMBED Equation.3 ___

Составим симплекс-таблицу.

Это решение не опорное, т.к. свободные члены не положительны.

Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент – n5 (минимальный по отношению свободного члена к элементам разрешающего столбца).

Таблица 1.1

	b		n₁		n₂		n₃
L’	0		5		6		7
L’		-75		2,5		0		-8
n₄	-26		-1		-1		0		26/1=26
n₄		15		-1		0		1,5
n₅	-30		-2		0		-3		30/2=15min
n₅		15		-1		0		1,5
n₆	-24		-1		-2		-4		24/1=24
n₆		15		-1		0		1,5

Меняем n₁и n_5.

Таблица 1.2

	b		n₅		n₂		n₃
L’	-75		2,5		6		-0,5
L’		-45		5		-10		25
n₄	-11		-0,5		-1		1,5		11/0,5=22
n₄		9		-1		2		-5
n₁	15		-0,5		0		1,5
n₁		9		-1		2		-5
n₆	-9		-0,5		-2		-2,5		9/0,5=18min
n₆		18		-2		4		5

Меняем n₅и n_6.

Таблица 1.3

	b		n₆		n₂		n₃
L’	-120		5		-4		25
L’		-10		5		5		-18
n₄	-2		-1		1		-4
n₄		2		-1		-1		2,5
n₁	24		-1		2		-3
n₁		2		-1		-1		3,5
n₅	18		-2		4		5
n₅		4		-2		-2		7

Меняем n₄и n₆.

Таблица 1.4

	b	n₄	n₂	n₃
L’	-130	5	1	7
L’
n₆	2	-1	-1	3,5
n₆
n₁	26	-1	-1	0
n₁
n₅	22	-2	2	12
n₅

Т.к. коэффициенты при всех ni положительны, то это и есть оптимальное решение.

Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.

Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.

Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.

Задание 2

Задача 29

Условие:

Решение задачи линейного программирования.

С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ( (B,

где (( = ( (1 (2 . . . (6 (( , В( = ( b1 b2 . . . b6 (( ,

(( = ( (1 (2 . . . (6(( , А= ((((( ((=1,6; (=1,3).

№ вар.	С₁	с₂	с₃	с₄	с₅	с₆	b₁	b₂	b₃

29	0	5	1	–1	1	0	2	2	10

Знаки ограничений			a₁₁	a₁₂	a₁₃	a₁₄
1	2	3
£	£	£	–1	1	1	0

a₁₅	a₁₆	a₂₁	a₂₂	a₂₃	a₂₄	a₂₅	a₂₆
0	0	1	–2	0	1	0	0

a₃₁	a₃₂	a₃₃	a₃₄	a₃₅	a₃₆	Тип экстрем.
2	1	1	1	2	0	max

Решение:

Составим систему:

_ EMBED Equation.3 ___

Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max

Приведем систему ограничений к виду основной задачи линейного программирования.

_ EMBED Equation.3 ___

Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

Q= 0-(-5x2-x3 +x4- x5)

_ EMBED Equation.3 ___

Составим симплекс-таблицу:

Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.

Таблица 2.1

	b		x₁		x₂		x₃		x₄		x₅
Q	0		0		-5		-1		1		-1
Q		10		-5		5		5		0		0
x₆	2		-1		1		1		0		0		2/1=2min
x₆		2		-1		1		1		0		0
x₇	2		1		-2		0		1		0
x₇		4		-2		2		2		0		0
x₈	10		2		1		1		1		2		10/2=5
x₈		-2		1		-1		-2		0		0

Меняем x₂и x_6.

Таблица 2.2

	b		x₁		x₆		x₃		x₄		x₅
Q	10		-5		5		4		1			-1
Q		4		1,5		-1		-1		0,5			0,5
x₂	2		-1		1		1		0			0
x₂		0		0		0		0		0			0
x₇	6		-1		2		2		1			0
x₇		0		0		0		0		0			0
x₈	8		3		-1		-1		1			2
x₈		4		6		-2		-2		2			0,5

Меняем x₅и x_8.

Таблица 2.3

	b		x₁		x₆		x₃		x₄		x₈
Q	14		-3.5		4,5		3,5		1,5		0,5
Q		21		5,25		-2,625		-2,625		2,625		2,625
x₂	2		-1		1		1		0		0
x₂		8/3		2/3		-1/3		-1/3		1/3		1/3
x₇	6		-1		2		2		1		0
x₇		8/3		2/3		-1/3		-1/3		1/3		1/3
x₅	4		1,5		-0,5		-1		0,5		0,5
x₅		8/3		2/3		-1/3		-1/3		1/3		1/3

Меняем x₅и x_1.

Таблица 2.4

	b	x₅	x₆	x₃	x₄	x₈
Q	35	5,25	1,875	0,875	4,125	3,125
x₂	14/3	2/3	2/3	2/3	1/3	1/3
x₇	26/3	2/3	5/3	5/3	4/3	1/3
x₁	8/3	2/3	-1/3	-1/3	1/3	1/3

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

Следовательно Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.

Ответ: Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.

Задание 3

Задача 9

Условие:

Решение транспортной задачи:

1. Записать условия задачи в матричной форме.

2. Определить опорный план задачи.

3. Определить оптимальный план задачи.

4. Проверить решение задачи методом потенциалов.

Таблица 1

№вар.	а₁	а₂	а₃	b₁	b₂	b₃	b₄	b₅	с₁₁	с₁₂	с₁₃
9	300	700	1000	200	100	400	600	200	23	40	10

с₁₄	с₁₅	с₂₁	с₂₂	с₂₃	с₂₄	с₂₅	с₃₁	с₃₂	с₃₃	с₃₄	с₃₅
12	21	25	21	20	50	18	15	30	32	25	50

Решение:

Составим таблицу транспортной задачи.

Таблица 2

	B1	B2	B3	B4	B5	a
A1
A1	23	40	10	12	21	300
A2
A2	25	21	20	50	18	700
A3
A3	15	30	32	25	50	1000
b	200	100	200	600	200

Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.

Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.

Таблица 3

	B1	B2	B3	B4	B5	В6	a
A1				300
A1	23	40	10	12	21	0	300
A2		100	200		200	200
A2	25	21	20	50	18	0	700
A3	200			300		500
A3	15	30	32	25	50	0	1000
b	200	100	200	600	200	700	2000

Это будет опорный план.

Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___

Таблица 4

	B1	B2	B3	B4	B5	В6	a
A1				300			300
A1	23	40	10	12	21	0
A2		100	200		200	200	700
A2	25	21	20	50	18	0
A3	200			300		500	1000
A3	15	30	32	25	50	0
b	200	100	200	600	200	700	2000

Проверим методом потенциалов:

Примем α1=0, тогда βj = cij – αi (для заполненных клеток).

Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0

Очевидно, что Δij =0 для заполненных клеток.

В результате получим следующую таблицу:

Таблица 5

	β1=2	β2=8	β3=7	β4=12	β5=6	β6=-13	a
α1=0				300			300
α1=0	23-2>0	40-8>0	10-7>0	12-12=0	21-6>0	0-(-13)>0
α2=13		100	200		200	200	700
α2=13	25-13-2>0	21-8-13=0	20-7-13=0	50-12-13>0	18-6-13=0	0-13+13=0
α2=13	200			300		500	1000
α2=13	15-13-2=0	30-13-8>0	32-13-7>0	25-13-2=0	50-13-6>0	0-13+13=0
b	200	100	200	600	200	700	2000

Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.

Тогда сумма всех перевозок:

L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800

Ответ:

	B1	B2	B3	B4	B5	В6	a
A1				300
A1	23	40	10	12	21	0	300
A2		100	200		200	200
A2	25	21	20	50	18	0	700
A3	200			300		500
A3	15	30	32	25	50	0	1000
b	200	100	200	600	200	700	2000

Задание 4

Задача 54

Условие:

Определить экстремум целевой функции вида

( = (11(12+(22(22+(12(1(2+(1(1+(2(2

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

(11(1+(12(2<=>(1

(21(1+(22(2<=>(2 .

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

Составить функцию Лагранжа.

Получить систему неравенств в соответствии с теоремой Куна-Таккера.

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

1. Дать ответ с учетом условий дополняющей нежесткости.

№

b₁

b₂

c₁₁

c₁₂

c₂₂

extr

a₁₁

a₁₂

a₂₁

a₂₂

p₁

p₂

Знаки огр.

1 2

–7

–2

1.5

–2

min

–2

1.5

–3

Решение:

1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min

Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max

Ограничения g1(x) и g2(x): _ EMBED Equation.3 ___ →_ EMBED Equation.3 ___

Определим относительный максимум функции F’, для этого определим стационарную точку (х10, х20):

_ EMBED Equation.3 ___→ _ EMBED Equation.3 ___→ _ EMBED Equation.3 ___

2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции:

F’11 (х10, х20) = -8 < 0

F’12 (х10, х20) = -1,5

F’21 (х10, х20) = -1,5

F’22 (х10, х20) = 4

_ EMBED Equation.3 ___

Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки

3) Составляем функцию Лагранжа:

L(x,u)=F’(x)+u1g1(x)+u2g2(x)=

=-4x12+2x22 -1,5x1x2+7x1+2x2+u1(_ EMBED Equation.3 ___)+u2(_ EMBED Equation.3 ___)

Получим уравнения седловой точки, применяя теорему Куна-Таккера:

_ EMBED Equation.3 ___ i=1;2

Объединим неравенства в систему А, а равенства в систему В:

Система А:

_ EMBED Equation.3 ___

Система В:

_ EMBED Equation.3 ___

Перепишем систему А:

_ EMBED Equation.3 ___

4)Введем новые переменные

V={v1,v2}≥0; W={w1,w2}≥0

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

_ EMBED Equation.3 ___

Тогда

_ EMBED Equation.3 ___.

Значит , система В примет вид:

_ EMBED Equation.3 ___ - это условия дополняющей нежесткости.

5) Решим систему А с помощью метода искусственных переменных.

Введем переменные Y={y1; y2} в 1 и 2 уравнения системы

_ EMBED Equation.3 ___

Затем создадим псевдоцелевую функцию Y=My1+My2→min

Y’=-Y= -My1-My2→max.

Пусть свободные переменные: х1, х2, v1, v2, u1, u2;

а базисные y1, y2, w1, w2.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

_ EMBED Equation.3 ___

Решим с помощью симплекс-таблицы. Найдем опорное решение:

	b		x1		x2		u1		u2		v1		v2
Y'/M	-9		-9,5		2,5		0,5		1		1		1
Y'/M		8,3125		1,1875		1,7813		-2,375		-4,75		-1,188		0
y1	7		8		1,5		-2		-4		-1		0
y1		0,875		0,125		0,1875		-0,25		-0,5		-0,125		0
y2	2		1,5		-4		1,5		3		0		-1
y2		-1,313		-0,188		-0,281		0,375		0,75		0,1875		0
w1	18		-2		1,5		0		0		0		0
w1		1,75		0,25		0,375		-0,5		-1		-0,25		0
w2	9		-4		3		0		0		0		0
w2		3,5		0,5		0,75		-1		-2		-0,5		0

	b		y1		x2		u1		u2		v1		v2
Y'/M	-0,69		1,1875		4,2813		-1,875		-3,75		-0,188		1
Y'/M		0,6875		-0,188		-4,281		1		3,75		0,1875		-1
x1	0,875		0,125		0,1875		-0,25		-0,5		-0,125		0
x1		0,0917		-0,025		-0,571		0,1333				0,025		-0,133
y2	0,688		-0,188		-4,281		1,875		3,75		0,1875		-1
y2		0,3667		-0,1		-2,283		0,5333		2		0,1		-0,533
w1	19,75		0,25		1,875		-0,5		-1		-0,25		0
w1		0,1833		-0,05		-1,142		0,2667		1		0,05		-0,267
w2	12,5		0,5		3,75		-1		-2		-0,5		0
w2		0,3667		-0,1		-2,283		0,5333		2		0,1		-0,533

	b		y1		x2		y2		u2		v1		v2
Y'/M	0		1		0		1		0		0		0
Y'/M
x1	0,967						0,1333
x1
u1	0,367		-0,1		-2,283		0,5333		2		0,1		-0,533
u1
w1	19,93						0,2667
w1
w2	12,87						0,5333
w2

Т. о, u2=x2=y1=y2=v1=v2=0; x1=0,967; u1=0,367; w1=19,93; w2=12,87;

б) Условия дополняющей нежесткости выполняются (u2w2=0), значит решения исходной задачи квадратичного программирования существует.

ОТВЕТ: существует.

Литература

Курс лекций Плотникова Н. В.

Внимание! Представленная Контрольная работа находится в открытом доступе в сети Интернет, и уже неоднократно сдавалась, возможно, даже в твоем учебном заведении.
Советуем не рисковать. Узнай, сколько стоит абсолютно уникальная Контрольная работа по твоей теме:

Новости образования и науки

14:21 05 Июля 2016
Российско-китайский медуниверситет откроет магистерскую программу по TCM
01:21 05 Июля 2016
На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
11:00 04 Июля 2016
Реморенко: "ЕГЭ-туризм" в России сходит на нет
10:52 04 Июля 2016
Летняя российско-австрийская школа откроется в Москве
15:31 01 Июля 2016
В СПбГУ могут воссоздать географический факультет

База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

Исследование операций — Информатика, программирование

Вариант 9

Новости образования и науки

Заказать уникальную работу

Похожие работы: