РефератыИнформатикаИсИсследование операций

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

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

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

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

Курсовая работа по дисциплине «Исследование операций»

Нормоконтроллёр:

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

«____» ___________ 2005 г.

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

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

«____» ___________ 2005 г.

Автор:

Студент группы ПС-346

Нечаев Л. В.

«____» ___________ 2005 г.

Работа защищена

с оценкой

«____» ___________ 2005 г.

Оглавление

Условие 3

Решение 3

Ответ: 6

Задача 2 7

Условие 7

Решение 7

Ответ: 10

Примечание: 10

Условие 11

Решение 11

Ответ: 16

Задача 4 17

Условие 17

Решение 18

Ответ: 22

Приложение 1 23

Список использованной литературы 29

Задача 1

Условие

Оператор связи оказывает 2 вида услуг:

Предоставление одной линии телефонной сети общего пользования (ТСОП) и трёх линий цифровой связи (ЦС);

Предоставление одной линии ЦС и двух линий ТСОП.

Стоимость услуг указана в табл. 1:

Таблица 1

ТСОП ЦС Цена
Услуга 1 1 3 750
Услуга 2 2 1 600

Сети связи и эксплуатируемое оборудование накладывает следующие ограничения на количество используемых линий связи:

ТСОП ≤ 300

ЦС ≤ 120

ТСОП+2*ЦС ≤ 380

Определить оптимальное соотношение услуг 1 и 2, которые оператор должен предоставлять для получения максимальной выручки.

Решение

Обозначим за x1 количество оказанных услуг с номером `1', а x2 – количество оказанных услуг с номером `2'.

Учтём ограничения задачи: .

Составим целевую функцию, которую нужно максимизировать:

Задача сведена к следующей задаче линейного программирования: «Найти значения аргументов x1 и x2, при которых функция принимает наибольшее значение при ограничениях:. Разумеется, x1≥0, x2≥0.

Решим выше представленную задачу графическим методом, так как в задаче присутствуют только 2 переменные x1 и x2. Для этого:

Изобразим многоугольник решений в плоскости x2Ox1:

График представлен на рис. 1.

В начале максимизации наибольшее значение целевой функции равно 0, также F проходит через начало координат (пунктирная линия на рис. 1). Вектор задаёт направление возрастания целевой функции.

Оптимальное решение находится в точке (0; 95), находящейся на

пересечении прямых . Следовательно, наибольшее значение целевой функции F будет равно , достигается при x1 = 0, x2 = 95.

Итак, для получения наибольшей прибыли (57000 ед.) оператор связи должен не предоставлять услуг 1, а услуг 2 предоставить в количестве 95 штук.

Ответ:

Не предоставлять yслуг #1

Yслуг #2 предоставить в количестве 95 штук.

Задача 2 Условие

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

С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции F=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).

Таблица 2

c1 c2 c3 c4 c5 c6 b1 b2 b3 Знаки ограничений
1 2 3
4 -1 12 2 -1 0 2 13 16 = = =
a11 a12 a13 a14 a15 a16 a21 a22 a23 a24 a25 a26 a31 a32 a33 a34 a35 a36 Ext
-1 1 1 0 0 0 4 3 2 1 1 0 3 2 0 0 1 0 max
Решение

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

Целевая функция имеет вид

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

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

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

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

Это решение является допустимым, но не опорным, т.к. присутствует отрицательный свободный член во второй строке. Ликвидируем его путём замены базисных переменных на основные. В строке x4 находится отрицательный элемент a42=-2, следовательно, столбец x2 – разрешающий. Наименьшее отношение между свободным членом и эл-том разрешающего столбца (см. поле «оценка») будет в первой строке и элемент a32 – разрешающий. Получилась таблица 3 (верхние числа).

Таблица 3

Базис Свободный член Переменные Оценка
x1 x2
x3

2

2

-1

-1

1

1

2
x4

-7

4

3

-2

-2

2

-
x5

16

-4

3

2

2

-2

8
F

6

18

13

-9

-9

9

-

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

Выделим разрешающий элемент aij;

Найдём обратную ему величину λ=1/aij и запишем её в правом нижнем углу этой же ячейки;

Все элементы разрешающей строки, кроме разрешающего элемента, умножим на λ и запишем внизу соответствующей ячейки;

Все элементы разрешающего столбца , кроме разрешающего элемента, умножим на -λ и запишем внизу соответствующей ячейки;

Выделим все верхние числа в разрешающей строке, и все нижние - в разрешающем столбце;

Для каждого из остальных элементов запишем в нижнюю часть ячейки произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент;

Перепишем таблицу, заменив переменные: элементы разрешающих строки и столбца – значениями, стоящими в нижних частях этих ячеек; оставшиеся элементы – суммой чисел, стоящих в верхних и нижних частях ячеек.

Применительно к текущему шагу, разрешающий элемент a32, λ = 1 / a32 = 1. После указанных выше преобразований, получим новую таблицу (табл. 4):

Таблица 4

Базис Свободный член Переменные
x1 x3
x2 2 -1 1
x4 -3 1 2
x5 12 5 -2
F 24 4 9

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

Ответ:

Система уравнений несовместима в области положительных значений переменных.

Примечание:

Этот же результат получен и при решении данной задачи в пакете Mathematica:

Задача 3

Условие

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

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

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

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

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

Таблица 5

B1 B2 B3 ai
A1 10 20 32 700
A2 12 50 25 600
A3 21 18 50 200
A4 25 15 23 200
A5 21 30 40 100
bj 300 700 1000
Решение

Заметим, что общее количество запасов (700+600+200+200+100=1800) меньше количества заявок (300+700+1000=2000), следовательно имеем открытую транспортную задачу с избытком заявок. Добавим строку с фиктивными запасами для дополнения задачи до задачи закрытого типа. После корректировки получаем транспортную задачу с правильным балансом (табл. 6):

Таблица 6

B1 B2 B3 ai
A1 10 20 32 700
A2 12 50 25 600
A3 21 18 50 200
A4 25 15 23 200
A5 21 30 40 100
A6 0 0 0 200
bj 300 700 1000 2000

Найдём опорное решение методом наименьших затрат (табл. 7):

Таблица 7

B1 B2 B3 ai
A1

10

300

20

400

32

-

700 -10 (2)
A2

12

-

50

-

25

600

600 -7 (7)
A3

21

-

18

200

50

-

200 -8 (4)
A4

25

-

15

100

23

100

200 -5 (5)
A5

21

-

30

-

40

100

100 -22 (8)
A6

0

-

0

-

0

200

200 18 (9)
Bj 300 700 1000 2000
0 (1) -10 (3) -18 (6)

Выбранный план перевозок является допустимым, т.к. при нём все заявки удовлетворены и все запасы израсходованы, сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу – заявке соответствующего пункта назначения. Сумма запасов равна сумме заявок, и выражается числом 2000, стоящим в правом нижнем углу таблицы. Данное распределение является базисным (заполнено m+n-1=8 ячеек таблицы), следовательно, задача готова к решению.

Первоначально затраты на перевозку составят:

Составим матрицу оценок методом потенциалов:

Начнём с первого столбца. Пусть потенциал этого столбца равен нулю. Рядом с потенциалом в скобках записываем номер шага. После прибавления потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (1;1) не изменится; чтобы полученный после сложения коэффициент стал равен 0, потенциал первой строки таблицы должен быть равен -10; для обнуления коэффициента затрат клетки (1;2) потенциал второго столбца должен быть -10 и т.д.

Изменённые коэффициенты выписываются в виде матрицы оценок:

Критерий оптимальности (базисное распределение поставок верно тогда и только тогда, когда оценки всех свободных клеток неотрицательны) на данном шаге не выполнен – присутствуют 2 свободные клетки с отрицательными оценками.

Продолжим оптимизацию (табл. 8). Составим цикл пересчёта для клетки (5;2) и дадим поставку неё:

Таблица 8

B1 B2 B3 ai
A1

10

300

20

400

32

-

700
A2

12

-

50

-

25

600

600
A3

21

-

18

200

50

-

200
A4

25

-

15 -

100

23 +

100

200
A5

21

-

30 +

-

40 -

100

100
A6

0

-

0

-

0

200

200
Bj 300 700 1000 2000

В верхнем правом углу знаком «+» отмечаются те клетки, поставки в которые увеличатся, а знаком «-» - те, в которые уменьшатся. Наибольшая возможная поставка, исходя из текущего цикла пересчёта равна min {100, 100, 100} = 100. Передвигаем её по циклу (табл. 9):

Таблица 9

B1 B2 B3 ai
A1

10

300

20

400

32

-

700 -10 (2)
A2

12

-

50

-

bottom: 1px solid #000000; border-left: 1px solid #000000; border-right: none; padding-top: 0in; padding-bottom: 0.04in; padding-left: 0.04in; padding-right: 0in;">

25

600

600 -7 (8)
A3

21

-

18

200

50

-

200 -8 (4)
A4

25

-

15

0

23

200

200 -5 (5)
A5

21

-

30

100

40

-

100 -20 (6)
A6

0

-

0

-

0

200

200 18 (9)
Bj 300 700 1000 2000
0 (1) -10 (3) -18 (7)

После передвижения освободились сразу 2 клетки, решение перестало быть базисным. Для того, чтобы оно осталось базисным, дадим фиктивную поставку в клетку (4;2).

Снова составляем матрицу оценок по вышеприведённому алгоритму:

На текущем шаге клеток с отрицательной оценкой нет, следовательно, критерий оптимальности выполнен.

Проверим решение с помощью метода потенциалов (табл. 10). Примем a1 = 0, тогда bj = cij – ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Δij = cij – (ai + bj ) ≥ 0, и Δij = 0 в заполненных клетках. Получим следующую таблицу (в скобках показаны оценки клеток):

Таблица 9

B1 B2 B3 ai
A1

10 (0)

300

20 (0)

400

32 (4)

-

700 -10 (2)
A2

12 (5)

-

50 (33)

-

25 (0)

600

600 -7 (8)
A3

21 (13)

-

18 (0)

200

50 (24)

-

200 -8 (4)
A4

25 (20)

-

15 (0)

0

23 (0)

200

200 -5 (5)
A5

21 (1)

-

30 (0)

100

40 (2)

-

100 -20 (6)
Bj 300 700 1000
0 (1) -10 (3) -18 (7)

Условие Δij ≥ 0 выполняется, следовательно, решение верное.

Ответ:

Таблица 10

B1 B2 B3 ai
A1

10

300

20

400

32

-

700
A2

12

-

50

-

25

600

600
A3

21

-

18

200

50

-

200
A4

25

-

15

-

23

200

200
A5

21

-

30

100

40

-

100
Bj 300 700 1000 1800/2000

Суммарные затраты на перевозку составляют:

Задача 4 Условие

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

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

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при условиях

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2 .

Данные располагаются в табл. 11.

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

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

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

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

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

Таблица 11

b1 b2 c11 c12 c22 extr a11 a12 a21 a22 p1 p2 Знаки огр.
1 2
1 8 -1 0.5 -1 max 1 1 0 1 7 5
Решение

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

Ограничения:

,

Определим относительный максимум функции. Для этого необходимы координаты стационарной точки .

,

Получили стационарную точку (1.6;4.4).

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

,

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

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

Составим систему неравенств в соответствии с теоремой Куна-Таккера.

А)Б)

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

A1).Вводим дополнительные переменные v1, v2, w1, w2, превращающие неравенства системы А1 в равенства:

A2)

перепишем систему Б:

Б2)- условия дополняющей нежёсткости

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

Вводим псевдоцелевую функцию

базисные переменные: y1, y2, w1, w2

свободные переменные: x1, x2, v1, v2, u1, u2

Решаем эту задачу симплекс-методом с помощью таблиц и небольшой программы на языке Си, текст которой приведён в Приложении 1.

Таблица 12

bi x1 x2 u1 u2 v1 v2
y1

1

0.5

2

0.5

-0.5

-0.25

1

0.5

0

0

-1

-0.5

0

0

y2

8

0.25

-0.5

0.25

2

-0.125

1

0.25

1

0

0

-0.25

-1

0

w1

7

-0.5

1

-0.5

1

0.25

0

-0.5

0

0

0

0.5

0

0

w2

5

0

0

0

1

0

0

0

0

0

0

0

0

0

Y'

9M

0.75M

-1.5M

0.75M

-1.5M

-0.375M

-2M

0.75M

-1M

0M

1M

-0.75M

1M

0M

Таблица 13

bi y1 x2 u1 u2 v1 v2
x1

0.5

1.1

0.5

0.03333

-0.25

0.1333

0.5

0.1667

0

0.1333

-0.5

-0.03333

0

-0.1333

y2

8.25

4.4

0.25

0.1333

1.875

0.5333

1.25

0.6667

1

0.5333

-0.25

-0.1333

-1

-0.5333

w1

6.5

-5.5

-0.5

-0.1667

1.25

-0.6667

-0.5

-0.8333

0

-0.6667

0.5

0.1667

0

0.6667

w2

5

-4.4

0

-0.1333

1

-0.5333

0

-0.6667

0

-0.5333

0

0.1333

0

0.5333

Y'

9.75M

8.25M

0.75M

0.25M

-1.875M

1M

-1.25M

1.25M

-1M

1M

0.25M

-0.25M

1M

-1M

Таблица 14

bi y1 y2 u1 u2 v1 v2
x1 1.6 0.5333 0.1333 0.6667 0.1333 -0.5333 -0.1333
x2 4.4 0.1333 0.5333 0.6667 0.5333 -0.1333 -0.5333
w1 1 -0.6667 -0.6667 -1.333 -0.6667 0.6667 0.6667
w2 0.6 -0.1333 -0.5333 -0.6667 -0.5333 0.1333 0.5333
Y' 18M 1M 1M 0M 0M 0M 0M

Оптимальное решение:

y1=y2=u1=u2=v1=v2=0

x1=1.6

x2=4.4

w1=1

w2=0.6

Проверим условие дополняющей нежёсткости:

xi*vi=0

ui*wi=0

Условия выполняются, следовательно, x1=1.6, x2=4.4 являются решением исходной задачи kвадратичного программирования. Координаты стационарной точки совпадают с координатами, полученных в качестве ответа. Стационарная точка удовлетворяет условиям ограничений.

Значение функции в точке (x1;x2) равно 0.

Ответ:

x1=1.6

x2=4.4

f(x1;x2) = 0

Приложение 1

Для решения задачи #4 использована следующая программа на языке Си, скомпилированная gcc (GCC) 4.0.0 20050519 (Red Hat 4.0.0-8). Её текст приведён ниже:

#include <stdio.h>

#define x 7

#define y 5

double mc[x*y] =

{

1, 2, -0.5, 1, 0, -1, 0,

8, -0.5, 2, 1, 1, 0, -1,

7, 1, 1, 0, 0, 0, 0,

5, 0, 1, 0, 0, 0, 0,

9, -1.5, -1.5, -2, -1, 1, 1

};

double mt[x*y];

void mprint (double* m, int xs, int ys)

{

int i, j;

printf ("n");

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

{

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

{

printf ("%10.4lg ", m[j*xs+i]);

}

printf ("n");

}

}

int main (void)

{

int i, j, i1, j1, it, jt;

double msx, msx1;

// Выбираем разрешающий эл-т

nextmtx:

printf ("nИсходная матрица коэффициентов:"); mprint (mc, x, y);

getch ();

msx = 10000.;

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

{

if (mc[(y-1)*x+i] < 0)

{

// Возможно, найден разрешающий столбец

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

{

// Ищем наименьшее отношение своб. члена к эл-ту разр. столбца

if (mc[j*x+i] < 1e-32)

continue; // Нулевой или отрицательный

msx1 = mc[j*x] / mc[j*x+i];

if (msx > msx1) // Частное св.ч / р.эл

{

msx = msx1; // наименьшее ищем

it = i; jt = j; // координаты р.эл.

}

}

if (msx > 9999.) continue; // Нет положительных эл-тов

else // найден р.эл., mx != 0

{

i = it; j = jt; // его координаты

}

printf ("n Разрешающий элемент: a(%d;%d) = %lg", j+1, i+1, mc[j*x+i]);

if (mc[j*x+i] > 0)

{

// Это и есть разрешающий элемент (s_el), находим обратную величину

mt[j*x+i] = 1. / mc[j*x+i];

for (i1 = 0; i1 < x; i1++)

{

// Разрешающая строка ( 1/s_el)

if (i1 == i) continue; // Пропустить сам s_el

mt[j*x+i1] = mt[j*x+i] * mc[j*x+i1];

}

for (j1 = 0; j1 < y; j1++)

{

// Разрешающий столбец (-1/s_el)

if (j1 == j) continue; // Пропустить сам s_el

mt[j1*x+i] = - mt[j*x+i] * mc[j1*x+i];

}

// успешно составлены разр. строка и столбец.

// теперь составляем остальные коэфф-ты

for (j1 = 0; j1 < y; j1++)

{

if (j1 == j) continue; // Пропустить всю разреш. строку

for (i1 = 0; i1 < x; i1++)

{

if (i1 == i) continue; // И столбец тоже

// Произведение нижней части столбца

// на верхнюю часть строки

mt[j1*x+i1] = mt[j1*x+i] * mc[j*x+i1];

}

}

/*

* Всё. Готова матрица нижних значений, теперь нужно

* поместить всё на свои места в mc

*/

printf ("nМатрица нижних значений:"); mprint (mt, x, y);

getch ();

for (j1 = 0; j1 < y; j1++)

{

for (i1 = 0; i1 < x; i1++)

{

if ((j1 == j) || (i1 == i))

{

/*

* Разрешающая строка или столбец

* просто ложим элементы в mc

*/

mc[j1*x+i1] = mt[j1*x+i1];

}

else

// иначе - сумму

mc[j1*x+i1] += mt[j1*x+i1];

}

}

// Всё готово к очередному шагу.

goto nextmtx; // след. матрица

}

// Этот эл-т не подходит, т.к. он отрицательный

}

// Если так и не было подходящего эл-та, то проверяем след. столбец

}

// отрицательны коэфф-тов при целевой ф-ции не найдено, следовательно, решение оптимально

printf ("nОптимизировано. Ответ:"); mprint (mc, x, y);

return 0;

}

Программа компилировалась командной строкой:

gcc simplex.c -o simplex

, запускалась:

./simplex

и выдавала на консоль пошаговое решение задачи, которое было занесено в симплекс-таблицы (см. табл. 12-14) четвёртой задачи данной курсовой работы.

Список использованной литературы

Кремер Н. Ш., Путко Б. А., Трощин И. М. «Исследование операций в экономике» - М.: ЮНИТИ, 2004. - 407 с.

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

Челябинск, 2005

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Исследование операций

Слов:24084
Символов:158022
Размер:308.64 Кб.