Исследование операций (стр. 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. Проверить решение задачи методом потенциалов.