Рефетека.ру / Информатика и програм-ие

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

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

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

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


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

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

«____» ___________ 2005 г.


Автор:

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

Попов А. Е..

«____» ___________ 2005 г.


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

с оценкой

«____» ___________ 2005 г.

Оглавление


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

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

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

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

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

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

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


В итоге получим:



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

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

Ответ:

x1=4

x2=3

x3=0

x4=-5

x5=0

L=14


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


Условие задачи задано в виде транспортной таблицы:


ПН

ПО

B1 B2 B3 запасы
A1 50 15 10 300
A2 21 30 20 100
A3 18 40 25 200
A4 23 22 12 800
A5 25 32 45 200
заявки 500 300 800

Применим к задаче метод «Северо-Западного угла». Для этого заполним таблицу начиная с левого верхнего угла без учёта стоимости перевозок:


ПН

ПО

B1 B2 B3 запасы
A1 300

300
A2 100

100
A3 100 100
200
A4
200 600 800
A5

200 200
заявки 500 300 800

В таблице заполнено n+m-1=7 клеток, значит найденное решение является опорным. Далее необходимо улучшить план перевозок в соответствии со стоимостями доставки грузов. Для этого используем циклические перестановки в тех циклах, где цена отрицательна.


ПН

ПО

B1 B2 B3 запасы
A1

50

300

15 10 300
A2

21

100

30 20 100
A3

18

100

40

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

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

200
A4

23


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

200

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

600

800
A5

25


32

45

200

200
заявки 500 300 800

В данной таблице в верхней части ячейки указана стоимость перевозки, а в нижней количество перевозимого груза. Прямоугольником выделен отрицательный цикл γ1=25+22-40-12=-5. Минимальное значение перевозок, стоящих в отрицательных вершинах равно k1=100. В итоге получим уменьшение стоимости перевозки:

ΔL1=-5*100=-500

Транспортная таблица примет следующий вид:


ПН

ПО

B1 B2 B3 запасы
A1

50

300

15 10 300
A2

21

100

30 20 100
A3

18

100

40


25

100

200
A4

23


22

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

12

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

800
A5

25


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

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

200

200
заявки 500 300 800

γ2=12+32-45-22=-23 k2=200 ΔL2=-23*200=-4600


ПН

ПО

B1 B2 B3 запасы
A1

50

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

15

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

300
A2

21

100

30 20 100
A3

18

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

40


25

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

200
A4

23


22

100

12

700

800
A5

25


32

200

45


200
заявки 500 300 800

γ3=10+18-50-25=-47 k3=100 ΔL3=-47*100=-4700


ПН

ПО

B1 B2 B3 запасы
A1

50

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

15

10

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

300
A2

21

100

30 20 100
A3

18

200

40


25


200
A4

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


22

100

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

700

800
A5

25


32

200

45


200
заявки 500 300 800

γ4=10+23-12-50=-29 k4=200 ΔL4=-29*200=-6800


ПН

ПО

B1 B2 B3 запасы
A1

50


15

10

300

300
A2

21

100

30 20 100
A3

18

200

40


25


200
A4

23

200

22

100

12

500

800
A5

25


32

200

45


200
заявки 500 300 800

Отрицательных циклов в транспортной таблице больше нет. Следовательно, можно предположить, что найденное решение является оптимальным. Для проверки применим метод потенциалов.

Составим систему:

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

Положим β2=0, тогда α4=-22

β1=1, α2=-20

β3=-10, α2=-22

α1=-20, α5=-32

Все коэффициенты α отрицательны, значит, найденный план перевозок является оптимальным.

Ответ:

x21=100;

x31=200;

x41=200;

x42=100;

x52=200;

x13=300;

x43=500.


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


Составим математическую модель поставленной задачи.

Найти минимум функции f(x1,x2)

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

При ограничениях Решение задач исследования операций

Заменив знак функции f(x1,x2) на противоположный, перейдем к поиску максимума функции:

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

Теперь задача приведена к стандартному виду задачи квадратичного программирования. Приступим к решению.

1) Определим стационарную точку

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

Решив систему, получим:

x1=10

x2=7

Очевидно, что данные координаты не удовлетворяют условиям ограничений. Поэтому проверять стационарную точку на относительный максимум нет необходимости.

2) Составим функцию Лагранжа:

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

Применив к функции Лагранжа теорему Куна-Таккера, будем иметь систему:

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

3) Преобразуем полученную систему:

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

Из уравнения 3 системы следует, что x2=6-x1:

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

Для обращения неравенств системы в равенства введём V1, V2, W и преобразуем систему:

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

4) Запишем условия дополняющей нежесткости:

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

5) Введем в систему уравнений искусственные переменные z1,z2:

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

Поставим задачу максимизации функции Решение задач исследования операций.

Для решения этой задачи воспользуемся Симплекс-методом. Примем переменные z1 и z2 в качестве базисных:

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

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

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



bi x1 U1 U2 V1 V2
φ

-17M

0

-5M

0

0

0

M

0

M

0

-M

0

z1

9

8

2

3

-1

1

2

-3

-1

0

0

1

z2

8

8

3

3

1

1

-3

-3

0

0

1

1

W

0

0

-1

0

0

0

0

0

0

0

0

0



bi x1 z2 U2 V1 V2
φ

-17M

17M

-5M

M

0

M

M

-M

M

-M

-M

M

z1

17

17/5

5

1/5

1

1/5

-1

-1/5

-1

-1/5

1

1/5

U1

8

-51/5

3

-3/5

1

-3/5

-3

3/5

0

3/5

1

-3/5

W

0

17/5

-1

1/5

0

1/5

0

-1/5

0

-1/5

0

1/5



bi z1 z2 U2 V1 V2
φ 0 M M 0 0 0
x1 17/5 1/5 1/5 -1/5 -1/5 1/5
U1 -11/5 -3/5 -2/5 1/2 3/5 -2/5
W 17/5 1/5 1/5 -1/5 -1/5 1/5

В итоге получим

x1=17/5

x2=6-x1=13/5

Как видно, координаты стационарной точки сильно отличаются от координат, полученных в качестве ответа. Это можно объяснить тем, что стационарная точка не удовлетворяет условиям ограничений.

Условия дополняющей нежесткости

Решение задач исследования операций выполняются.

Следовательно, найденное решение является оптимальным.

Найдем значения целевой функции:

Решение задач исследования операций=- 51/5 - 52/5 + 289/50 – 221/25 + 169/25 =

= -16.9

Ответ:

x1 = 17/5

x2 = 13/5

f(x1,x2) = -16.9

16


Похожие работы:

  1. Методы решения логистических задач
  2. • Оптимальное распределение неоднородных ресурсов
  3. • Матричные антагонистические игры с нулевой суммой в ...
  4. • Проблемы и методы принятия решений
  5. • Технология принятия управленческого решения
  6. • Методы исследования операций
  7. • Системный анализ и проблемы принятия решений
  8. • Решение задачи линейного программирования ...
  9. •  ... на уроках математики при решении текстовых задач в 6 ...
  10. • Решение оптимизационных управленческих задач на ...
  11. • Моделирование ситуаций и выработка управленческих решений
  12. • Исследование задачи оптимизации кооперации ...
  13. • Использование среды MatLAB для решения линейной ...
  14. • Сущность и использование транспортных задач
  15. • Основные понятия и решения моделирования
  16. • Динамическое программирование (задача о загрузке)
  17. • Построение экономической модели с использованием симплекс ...
  18. • Автоматизированные Системы Обработки Информации
  19. • Эффективность менеджмента
Рефетека ру refoteka@gmail.com