Смекни!
smekni.com

Исследование операций (стр. 1 из 3)

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

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

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

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

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

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

ТСОП ≤ 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

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 -

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

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

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

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

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

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

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

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

Применительно к текущему шагу, разрешающий элемент 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. Проверить решение задачи методом потенциалов.