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

11

Министерство общего и профессионального образования РФ

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

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

КУРСОВАЯ РАБОТАПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙВариант 14Группа ПС-317Выполнил: Родионова Е.В.Проверил: Плотникова Н.В.Челябинск, 2004СодержаниеЗадача 1 2Задача 2 4Задача 3 6Задача 4 8 Задача 1№14Условие:Нефтеперерабатывающий завод получает 4 полуфабриката: x1 тыс. л. алкилата, x2 тыс. л. крекинг-бензина, x3 тыс. л. бензина прямой перегонки и x4 тыс. л. изопентана. В результате смешивания этих четырех компонентов в разных пропорциях образуется три сорта авиационного бензина: бензин А (а1:а2:а3:а4), бензин В (b1:b2:b3:b4) и бензин С (с1:с2:с3:с4). Стоимость 1 тыс. л. бензина каждого сорта равна y1 руб., y2 руб. и y3 руб.Определить соотношение компонентов, при котором будет достигнута максимальная стоимость всей продукции.Решение:Составим математическую модель задачи.Обозначим через t1 количество бензина А; через t2 количество бензина В; через t3 количество бензина С.Тогда, целевая функция будет L=y1t1+ y2t2+ y3t3=120t1+100t2+150t3 >max Система ограничений: Приведем систему ограничений к виду основной задачи линейного программирования (введем новые переменные t4 , t5 ,t6 ,t7, которые входят в целевую функцию с нулевыми коэффициентами):Выберем t1 , t2 ,t3 свободными переменными, а t4 , t5 ,t6 ,t7 - базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:L=0-(-120t1-100t2-150t3)Составим симплекс-таблицу.Это решение опорное, т.к. все свободные члены положительны.Т. к. все коэффициенты в целевой функции отрицательные, то можно взять любой столбец разрешающим (пусть t1). Выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это t7)Далее меняем t2 и t1 .Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.Таким образом, t1 = t3 =0; t2=100; L=10000.Т.е. для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.ОТВЕТ: для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.Задача 2№34Условие:С помощью симплекс-таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax B, где = 1 2 . . . 6 , В = b1 b2 . . . b6 , = 1 2 . . . 6 , А= (=1,6; =1,3).Решение:Исходная система:Целевая функция Q= x1+3x2+x3+3x5.Пусть х3, х4 - свободные переменные, х1, х2, х5 - базисные.Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы: Q=9 - (9/2x3-1/2x4)Составим симплекс-таблицу:Это опорное решение, т.к. свободные члены положительны.Т.к. коэффициент при х4 отрицательный, то это и будет разрешающий столбец. В качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это х5).Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.Т. о. Q=29/3x3=x5=0; x1=4/3; x2=7/3; x4=4/3.ОТВЕТ: Q=29/3жx3=x5=0; x1=4/3; x2=7/3; x4=4/3.Задача 3№14Условие:Решение транспортной задачи:

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

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

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

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

Решение:

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

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

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

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

с1,2+с2,3>c1.3+c3.2 (60+55>30+40)

Количество единиц товара, перемещаемых по циклу: min (с1,2 ; с2,3)=15

2) Рассмотрим цикл (2,4)-(2,5)-(3,5)-(3,4):

c2,4+с3,5>c2.5+c3.4 (30+40>30+100)

Количество единиц товара, перемещаемых по циклу: min (с2,4 ; с3,5)=15

В результате получится следующий план:

Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение.

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

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

Если решение верное, то во всех пустых клетках таблицы Дij = cij - (бi+ вj) ? 0

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

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

Д1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки.

Таким образом, решение верное, т.к. Дij ?0.

ОТВЕТ:

Задача 4

№59

Условие:

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

= 1112+2222+1212+11+22

при условиях

111+122<=>1

211+222<=>2 .

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

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

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

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

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

Решение:

Целевая функция: F=-5x12-x22-2x1x2+4.5x1+1.5x2

Ограничения g1(x) и g2(x): >

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

> >

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

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

F12 (х10, х20) = -2

F21 (х10, х20) = -2

F22 (х10, х20) = -2

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

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

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

=-5x12-x22-2x1x2+4.5x1+1.5x2+u1(2x1-3x2-9)+u2(5x1+4x2-13)

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

i=1;2

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

Система А:

Система В:

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

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

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

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

Тогда

.

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

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

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

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

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

Y'=-Y= -My1-My2>max.

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

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

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

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

Примечание: вычисления производились программно, см Приложение

Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413043; u2=5,934783; x1=4.5; w2=9.5.

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

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

Приложение

#include <math.h>

#include <stdio.h>

main()

{

int i,j,k,m;

double h,n,a[5][7],b[5][7];

clrscr();

printf ("Введите числа матрицы А ");

for (i=0; i<5; i++){for(j=0; j<7; j++) {scanf ("%lf",&n); a[i][j]=n;}}

printf ("Введите координаты разрешающего элемента\n");

scanf("%d",&k) ;

scanf ("%d",&m);

printf (" матрицa A \n");

for (i=0; i<5; i++)

{for(j=0; j<7; j++) printf (" %lf",a[i][j]);printf ("\n");}

printf (" координаты \n ");

printf("%d %d",k,m) ;

h=1/a[k][m];

b[k][m]=h;

printf ("\n h=%lf",h);

for (i=0; i<7; i++)

{ if (i!=m) b[k][i]=a[k][i]*b[k][m]; }

for (i=0;i<5; i++)

{ if (i!=k) b[i][m]=-a[i][m]*b[k][m];}

for (i=0;i<5;i++)

{

for (j=0;j<7;j++)

if ((i!=k)&&(j!=m)) b[i][j]=a[i][j]+a[k][j]*b[i][m];

}

printf ("\n результат ");

printf (" матрицa B \n");

for (i=0; i<5; i++)

{for(j=0; j<7; j++) printf (" %lf",b[i][j]);printf ("\n");}

getch();

}