Контрольная работа: Исследование операций и теория систем 2

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

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

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

КУРСОВАЯ РАБОТА

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

Вариант 8

Руководитель:

Плотникова Н.В.

«___»__________2004 г.

Автор проекта:

студентка группы

ПС – 317

Куликова Мария

«___»__________2004 г.

Проект защищен

с оценкой

«___»__________2004 г.

Челябинск

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

Задача 1………………………………………………………………….3

Задача 2………………………………………………………………….8

Задача 3…………………………………………………………………10

Задача 4…………………………………………………………………13

Задача 1 (№8)

Условие:

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

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

Решение:

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

пусть x1 –длина 1-ого кабеля (км);

x2 – длина 2-ого кабеля (км);

x3 – длина 3-ого кабеля (км);

x4 – длина 4-ого кабеля (км)

тогда целевая функция L - общая прибыль от реализации изготовляемой продукции, будет иметь следующий вид

L= В1x1 + В2x2 + В3x3 + В4x4 = x1+ 2x2 + 1,5x3 + x4 → max

Получим систему ограничений:

1,5x1 + x2 + 2x3+ x4 £ 6500;

x1 + 2x2 + 0x3+2x4 £ 4000;

4x1 + 5x2 + 5x3+4x4 £11000;

2x1 + x2 +1,5x3+0x4 £ 4500;

x1 + 2x2 +1,5x3+4x4 £ 4500.

Приведём полученную математическую модель к виду ОЗЛП с помощью добавочных неотрицательных переменных, число которых равно числу неравенств:

1,5x1 + x2 + 2x3+ x4 + x5 = 6500;

x1 + 2x2 + 0x3+2x4 + x6= 4000;

4x1 + 5x2 + 5x3+4x4 + x7=11000;

2x1 + x2 +1,5x3+0x4 + x8 =4500;

x1 + 2x2 +1,5x3+4x4 + x9 =4500.

Итак, выберем x1, x2, x3, x4 - свободными переменными, а x5, x6, x7, x8, x9 - базисными переменными (каждая из них встречаются в системе лишь в одном уравнении с коэффициентом 1, а в остальных с нулевыми коэффициентами). Приведём систему к стандартному виду, выразив для этого все базисные переменные через свободные:

x5 = 6500 – (1,5x1 + x2 + 2x3+ x4 );

x6 = 4000 – ( x1 + 2x2 + 0x3+2x4);

x7 =11000 - ( 4x1 + 5x2 + 5x3+4x4);

x8 =4500 – ( 2x1 + x2 +1,5x3+0x4);

x9 =4500 – ( x1 + 2x2 +1,5x3+4x4)

L=0 –(- x1- 2x2 - 1,5x3 - x4)

Решим методом симплекс-таблиц:

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

Выберем столбец в таблице, который будет разрешающим, пусть это будет x1, выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это x8).

Меняем и

Меняем и x9

Видим, что коэффициенты при переменных в целевой функции положительны, значит, найденное решение будет оптимальным.

Итак, =0, =3875/3, =2750/3, =250, L=3500.

Ответ: если предприятие будет изготавливать только три вида проволоки 1,2,3 причем 3875/3 км, 2750/3 км, 250 км соответственно, то общая прибыль от реализации изготовляемой продукции будет максимальной и равной 3500(ед).

Задача 2 (№28)

Условие:

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

где CT = [ c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T ,

XT = [ x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3).

Решение:

Получим систему:

4 x1 + x2 + x3+2x4 + x5 =8;

2x1 - x2 +x4=2;

x1 + x2+x5=3

L= -6x1+ x3 -x4 -x5 → max

Пусть x2, x4 – свободные переменные, а x1, x3, x5 - базисные переменные. Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

x5 =2-(1,5x2 -0,5 x4);

x3 =6-(1,5x2 +0,5 x4);

x1=1-(-0,5x2+0,5x4)

L=-2-(3x2- x4) → max

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

Выберем разрешающим столбцом x4,т.к. только перед этой переменной в целевой функции отрицательное число, выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это x1). Меняем x4 и x1

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

Итак, x1= x2=0, x3 =5, x4=2, x5 =3, L=0.

Ответ: x1= x2=0, x3 =5, x4=2, x5 =3, L=0.

Задача 3 (№8)

Условие:

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

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

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

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

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

Решение:

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

Количество заполненных ячеек r=m+n-1=6.

Проверим сумму по столбцам, сумму по строкам и количество базисных (заполненных) клеток:

r =6, å ai=å bj=1000, всё выполняется, значит, найденный план является опорным.

L=25*200+30*200+40*100+10*200+12*100+21*200=22400

Постараемся улучшить план перевозок.

1) Рассмотрим цикл (1;1)-(1;2)-(2;2)-(2;1)

Подсчитаем цену цикла: j=15-30+21-25=-19<0

L=21*200+15*200+40*100+10*200+12*100+21*200=18600

2) Рассмотрим цикл (2;1)-(2;2)-(3;2)-(3;1)

j=-15+30+23-40=-2<0

L=21*200+15*100+30*100+23*100+10*200+12*100+21*200=18400

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

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

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

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

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

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

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

L=18400

Ответ:

Задача 4 (№53)

Условие:

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

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

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

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2.

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

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

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

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

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

Решение:

Целевая функция:

F= -2x12-x22-4x1x2+6x1+1,5x2→max

Ограничения g1(x) и g2(x): 2,5x1-x2³7 2,5x1-x2–7³0

3x1+2,5x2³13 3x1+2,5x2-13³0

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

→

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

F11 (х10, х20) = -4 < 0

F12 (х10, х20)=-4

F21 (х10, х20)=-4

F22 (х10, х20)=-2

F11 F12 -4 -4

F21 F22 -4 -2

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

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

L(x,u)=F(x)+u1g1(x)+u2g2(x)=-2x12-x22-4x1x2+6x1+1,5x2+u1 (2,5x1-x2–7)+ u2 (3x1+2,5x2-13).

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

i=1;2

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

Система А:

Система В:

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

6-4x1-4x2+2,5u1+3u2 <0

1,5-4x1-2x2-u1+2,5u2 <0

2,5x1-x2–7³0

3x1+2,5x2–13³0

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

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

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

6-4x1-4x2+2,5u1+3u2 + v1=0

1,5-4x1-2x2-u1+2,5u2 + v2=0

2,5x1-x2–7- w1=0

3x1+2,5x2–13- w2=0

Тогда

- v1=6-4x1-4x2+2,5u1+3u2

- v2=1,5-4x1-2x2-u1+2,5u2

w1=2,5x1-x2–7

w2=3x1+2,5x2–13

Следовательно, система В примет вид:

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

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

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

6-4x1-4x2+2,5u1+3u2 + v1 -y1=0

1,5-4x1-2x2-u1+2,5u2 + v2 -y2=0

2,5x1-x2–7- w1=0

3x1+2,5x2–13- w2=0

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

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

В качестве свободных выберем х1, х2, v1, v2, u1, u2;

а в качестве базисных y1, y2, w1, w2.

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

y1=6-(4x1+4x2-2,5u1-3u2 - v1)

y2=1,5-(4x1+2x2+u1-2,5u2 -v2)

w1=-7-(-2,5x1+x2)

w2=-13-(-3x1-2,5x2)

Y’=-Y=-My1-My2=-7,5M-(-8x1-6x2+1,5u1+5,5u2+ v1+v2) M

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

Меняем и

Меняем и

Меняем и

Меняем и

Итак, =====, =16,785, =11,017, =23,944, =35,07

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

Ответ: существует.

Литература.

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

2) Пантелеев А.В., Летова Т.А. «Методы оптимизации в примерах и задачах».