Быстрый поиск

Контрольная работа: Решение задач исследования операций

Курсовая работа

по дисциплине

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

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

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

«____» ___________ 2005 г.

Автор:

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

Попов А. Е..

«____» ___________ 2005 г.

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

с оценкой

«____» ___________ 2005 г.

Оглавление

1 Условия задач. 3

2 Решение задач исследования операций. 4

2.1 Решение задачи 1. 4

2.2 Решение задачи 2. 8

2.3 Решение задачи 3. 12

2.4 Решение задачи 4. 17

1 Условия задач
2 Решение задач исследования операций

2.1 Решение задачи 1

Для составления математической модели задачи введём переменные:

– количество горючего, доставляемое со склада A на бензоколонку 1

– количество горючего, доставляемое со склада A на бензоколонку 2

x3a – количество горючего, доставляемое со склада A на бензоколонку 3

x1b – количество горючего, доставляемое со склада B на бензоколонку 1

x2b – количество горючего, доставляемое со склада B на бензоколонку 2

x3b – количество горючего, доставляемое со склада B на бензоколонку 3

x1c – количество горючего, доставляемое со склада C на бензоколонку 1

x2c – количество горючего, доставляемое со склада C на бензоколонку 2

x3c – количество горючего, доставляемое со склада C на бензоколонку 3

На складах A, B, C находится 90, 60, 90 тонн горючего соответственно, следовательно, можно записать:

На каждую заправку нужно оправить одинаковое количество горючего, равное (90+60+90)/3:

В соответствии со стоимостями перевозок запишем целевую функцию, которую необходимо минимизировать:

Имеем классическую транспортную задачу с числом базисных переменных, равным n+m–1 , где m–число пунктов отправления, а n – пунктов назначения. В решаемой задаче число базисных переменных равно 3+3-1=5.

Число свободных переменных соответственно 9-4=4.

Примем переменные x1a, x1b, x2a, x2с, x3с в качестве базисных, а переменные x1c, x2b, x3а, x3b в качестве свободных (данный выбор позволяет легко выразить базисные переменные через свободные).

Далее в соответствии с алгоритмом Симплекс метода необходимо выразить базисные переменные через свободные:

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

В задании требуется найти минимум функции L. Так как коэффициент при переменной x1c меньше нуля, значит найденное решение не является оптимальным.

Составим Симплекс таблицу:

x3a

x2b

x3b

x1c

630

-10

-3

-1

-4

-1

x1a

-10

-1

x1b

x2a

-1

x2c

-1

x3c

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

	bi	x3a	x2b	x3b	x2c
L	620	-2	-1	0	-1
x1a	10	1	-1	0	-1
x1b	60	0	1	1	0
x2a	80	0	1	0	1
x1c	10	-1	0	-1	1
x3c	80	1	0	1	0

Все коэффициенты при свободных переменных неположительные, следовательно, найденное решение является оптимальным. Запишем его:

x1a=10; x1b=60; x1c=10;

x2a=80; x2b=0; x2c=0;

x3a=0; x3b=0; x3c=80;

L=620;

Для проверки правильности вычислений можно составить транспортную таблицу:

	A	B	C
1	10	60	10	80
2	80	0	0	80
3	0	0	80	80
	90	60	90

После анализа таблицы можно сделать вывод, что вычислительных ошибок при расчетах сделано не было.

Ответ:

x1a=10 x1b=60 x1c=10

x2a=80 x2b=0 x2c=0

x3a=0 x3b=0 x3c=80

L=620

2.2 Решение задачи 2

Составим систему ограничений исходя из условия задачи

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

Пусть переменные x1 и x2 - свободные, а переменные x3, x4 и x5 базисные.

Далее необходимо представить систему ограничений в стандартном виде. Для этого проведем ряд преобразований:

Подставим выражения для x3 и x4 в третье уравнение системы ограничений:

Упростим полученное выражение и выразим x5:

Теперь можно представить систему ограничений в стандартном виде:

Необходимо также выразить целевую функцию через свободные переменные:

Теперь можно заполнить Симплекс-таблицу

	bi	x1	x2
L	1	-1	-3
x3	2	-1	2
x4	2	1	1
x5	1	1	-1

Исходя из того, что все свободные члены положительны, можно сделать вывод о том принятое решение является опорным.

Далее нужно выбрать разрешающий элемент. В качестве разрешающего столбца целесообразно принять столбец x1, так как коэффициент при x1 в целевой функции меньше коэффициента при x2. Разрешающей строкой будет строка x5, так как отношение свободного члена этой строки к коэффициенту при x1 минимально. Отметим найденный разрешающий элемент в таблице, а также заполним необходимые клетки:

-1

-3

-1

Перерисуем таблицу с учётом замены x2 на x3:

	bi	x5	x2
L	2	1	-4
x3	3	1	1
x4	1	-1	2
x1	1	1	-1

Коэффициент при х2 в целевой функции отрицателен, значит необходимо произвести ещё одну замену. В качестве разрешающей строки примем x3. Таким образом, разрешающим будет элемент, стоящий на пересечении строки x3 и столбца x2.