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

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

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

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

«____» ___________ 2005 г.

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

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

«____» ___________ 2005 г.

Автор:

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

Нечаев Л. В. ___________

«____» ___________ 2005 г.

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

с оценкой______________

«____» ___________ 2005 г.

Оглавление

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

Условие......................................................................................................................................... 3

Решение....................................................................................................................................... 3

Ответ: ............................................................................................................................................ 5

Задача 2............................................................................................................................................. 6

Условие......................................................................................................................................... 6

Решение....................................................................................................................................... 6

Ответ:............................................................................................................................................. 8

Примечание:................................................................................................................................ 8

Задача 3........................................................................................................................................... 10

Условие....................................................................................................................................... 10

Решение..................................................................................................................................... 10

Ответ:........................................................................................................................................... 14

Задача 4........................................................................................................................................... 15

Условие....................................................................................................................................... 15

Решение..................................................................................................................................... 15

Ответ:........................................................................................................................................... 19

Приложение 1................................................................................................................................ 20

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

Задача 1

Условие

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

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

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

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

Таблица 1

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

ТСОП ≤ 300

ЦС ≤ 120

ТСОП+2*ЦС ≤ 380

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

Решение

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

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

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

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

5. Решим выше представленную задачу графическим методом, так как в задаче присутствуют только 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

Решение

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

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

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

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

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

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

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

Таблица 3

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

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

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

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

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

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

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

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

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

Таблица 4

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

Ответ:

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

Примечание:

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

Задача 3

Условие

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

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

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

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

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

Таблица 5

Решение

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

Таблица 6

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

Таблица 7

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

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

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

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

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

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

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

Таблица 8

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

Таблица 9

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

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

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

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

Таблица 9

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

Ответ:

Таблица 10

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

Задача 4

Условие

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

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

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при условиях

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2 .

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

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

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

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

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

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

Таблица 11

Решение

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

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

,

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

,

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

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

,

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

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

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

А)Б)

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

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

A2)

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

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

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

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

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

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

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

Таблица 12

Таблица 13

Таблица 14

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

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) четвёртой задачи данной курсовой работы.

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

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

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