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

Министерство образования и науки Российской Федерации Южно-Уральский государственный университет Кафедра систем управления Челябинск, 2005

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

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

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

«____» ___________ 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.

Итак, для получения наибольшей прибыли (57 000 ед.) оператор связи должен не предоставлять услуг 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 = c11×12+c22×22+c12x1x2+b1x1+b2x2

при условиях

a11×1+a12×2<=>p1

a21×1+a22×2<=>p2 .

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

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

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

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

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

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

Таблица 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 20 050 519 (Red Hat 4.0.0−8). Её текст приведён ниже:

#include

#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 = 10 000.;

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.co simplex

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

./simplex

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

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

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