Решение задач исследования операций (48792)

Посмотреть архив целиком






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

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

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


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

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

«____» ___________ 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 меньше нуля, значит найденное решение не является оптимальным.

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




bi

x3a

x2b

x3b

x1c

L

630

-10

-3

1

-1

0

-4

4

1

-1

x1a

20

-10

0

1

-1

0

-1

1

1

-1

x1b

60

0

0

0

1

0

1

0

0

0

x2a

70

10

1

-1

1

0

1

-1

-1

1

x2c

10

10

-1

-1

0

0

-1

-1

1

1

x3c

80

0

1

0

0

0

1

0

0

0


Выбор в качестве разрешающей строки х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 минимально. Отметим найденный разрешающий элемент в таблице, а также заполним необходимые клетки:



bi

x1

x2

L

1

1

-1

1

-3

-1

x3

2

1

-1

1

2

-1

x4

2

-1

1

-1

1

1

x5

1

1

1

1

-1

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



bi

x5

x2

L

2

12

1

4

-4

4

x3

3

3

1

1

1

1

x4

1

-6

-1

-2

2

-2

x1

1

3

1

1

-1

1


Случайные файлы

Файл
kursovik.doc
70712.rtf
43408.rtf
99751.rtf
72949.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.