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

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

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

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

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

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

Вариант 9

_

Челябинск

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

Задание 1 3

Задание 2 6

Задание 3 9

Задание 4 11

Литература 17

Задание 1

Задача 9

Условие:

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

ВеществоКоличество единиц вещества, содержащегося в 1 кг сырья
123
АD11D12D13
ВD21D22D23
СD31D32D33
Цена 1 кг сырьяD1D2D3
№ вар.D11D12D13D21D22D23D31D32D33
9110203124
D1D2D3АBC
567263024

Решение:

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

Обозначим через 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

Bn1N2N3
L’0567
-752,50-8
N4-26-1-1026/1=26
15-101,5
n5-30-20-330/2=15min
15-101,5
N6-24-1-2-424/1=24
15-101,5

Меняем n1 и n5.

Таблица 1.2

Bn5N2N3
L’-752,56-0,5
-455-1025
N4-11-0,5-11,511/0,5=22
9-12-5
N115-0,501,5
9-12-5
n6-9-0,5-2-2,59/0,5=18min
18-245

Меняем n5 и n6.

Таблица 1.3

Bn6N2N3
L’-1205-425
-1055-18
n4-2-11-4
2-1-12,5
N124-12-3
2-1-13,5
N518-245
4-2-27

Меняем n4 и n6 .

Таблица 1.4

BN4N2N3
L’-130517
N62-1-13,5
N126-1-10
N522-2212

Т. к. коэффициенты при всех 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).

№ вар.С1С2С3С4С5С6B1B2B3
29051-1102210
Знаки ограниченийA11A12A13A14
123
£££-1110
A15A16A21A22A23A24A25A26
001-20100
A31A32A33A34A35A36Тип экстрем.
211120Max

Решение:

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

_ EMBED Equation.3 ___

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

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

_ EMBED Equation.3 ___

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

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

Q= 0-(-5×2-x3 +x4- x5)

_ EMBED Equation.3 ___

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

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

Таблица 2.1

BX1x2X3X4X5
Q00-5-11-1
10-55500
x62-111002/1=2min
2-11100
X721-2010
4-22200
X8102111210/2=5
-21-1-200

Меняем x2 и x6.

Таблица 2.2

BX1X6X3X4x5
Q10-5541-1
41,5-1-10,50,5
X22-11100
000000
X76-12210
000000
x883-1-112
46-2-220,5

Меняем x5 и x8.

Таблица 2.3

Bx1X6X3X4X8
Q14-3.54,53,51,50,5
215,25-2,625-2,6252,6252,625
X22-11100
8/32/3-1/3-1/31/31/3
X76-12210
8/32/3-1/3-1/31/31/3
x 541,5-0,5-10,50,5
8/32/3-1/3-1/31/31/3

Меняем x5 и x1.

Таблица 2.4

BX5X6X3X4X8
Q355,251,8750,8754,1253,125
X214/32/32/32/31/31/3
X726/32/35/35/34/31/3
X18/32/3-1/3-1/31/31/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

№вар.А1А2А3B1B2B3B4B5С11С12С13
93007001000200100400600200234010
С14С15С21С22С23С24С25С31С32С33С34С35
122125212050181530322550

Решение:

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

Таблица 2

B1B2B3B4B5A
A1
2340101221300
A2
2521205018700
A3
15303225501000
B200100200600200

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

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

Таблица 3

B1B2B3B4B5В6A
A1300
23401012210300
A2100200200200
25212050180700
A3200300500
153032255001000
B2001002006002007002000

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

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

Таблица 4

B1B2B3B4B5В6A
A1300300
23401012210
A2100 200200 200700
25212050180
A3200 300 5001000
15303225500
B2001002006002007002000

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

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

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

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

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

Таблица 5

β1=2β2=8β3=7β4=12β5=6β6=-13A
α1=0300300
23-2>040-8>010-7>012-12=021-6>00-(-13)>0
α2=13100200200200700
25-13-2>021-8-13=020-7-13=050-12-13>018-6-13=00-13+13=0
α2=132003005001000
15-13-2=030-13-8>032-13-7>025-13-2=050-13-6>00-13+13=0
B2001002006002007002000

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

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

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

Ответ:

B1B2B3B4B5В6A
A1300
23401012210300
A2100200200200
25212050180700
A3200300500
153032255001000
B2001002006002007002000

Задание 4

Задача 54

Условие:

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

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

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

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

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

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

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

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

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

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

2.

B1B2C11C12C22ExtrA11A12A21A22P1P2

Знаки огр.

1 2

31-7-241.5-2Min-21.54-3189£³

Решение:

1) Целевая функция: F=4×12-2×22 +1,5x1x2-7×1-2×2→min

Рассмотрим F’=-4×12+2×22 -1,5x1x2+7×1+2×2→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)=

=-4×12+2×22 -1,5x1x2+7×1+2×2+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 ___

_ EMBED Equation.3 ___

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

BX1X2U1U2V1V2
Y’/M-9-9,52,50,5111
8,31251,18751,7813-2,375-4,75-1,1880
Y1781,5-2-4-10
0,8750,1250,1875-0,25-0,5-0,1250
Y221,5-41,530-1
-1,313-0,188-0,2810,3750,750,18750
W118-21,50000
1,750,250,375-0,5-1-0,250
W29-430000
3,50,50,75-1-2-0,50
BY1X2u1U2V1V2
Y’/M-0,691,18754,2813-1,875-3,75-0,1881
0,6875-0,188-4,28113,750,1875-1
X10,8750,1250,1875-0,25-0,5-0,1250
0,0917-0,025-0,5710,13330,025-0,133
y20,688-0,188-4,2811,8753,750,1875-1
0,3667-0,1-2,2830,533320,1-0,533
W119,750,251,875-0,5-1-0,250
0,1833-0,05-1,1420,266710,05-0,267
W212,50,53,75-1-2-0,50
0,3667-0,1-2,2830,533320,1-0,533
BY1X2Y2U2V1V2
Y’/M0101000
X10,9670,1333
U10,367-0,1-2,2830,533320,1-0,533
W119,930,2667
W212,870,5333

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

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

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

Литература

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


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