Решение задач исследования операций
8
Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра Систем Управления
Челябинск, 2005
Курсовая работа
по дисциплине
Исследование операций
Руководитель:
Плотникова Н. В.
«____» ___________ 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 на бензоколонку 2x3a - количество горючего, доставляемое со склада A на бензоколонку 3x1b - количество горючего, доставляемое со склада B на бензоколонку 1x2b - количество горючего, доставляемое со склада B на бензоколонку 2x3b - количество горючего, доставляемое со склада B на бензоколонку 3x1c - количество горючего, доставляемое со склада C на бензоколонку 1x2c - количество горючего, доставляемое со склада C на бензоколонку 2x3c - количество горючего, доставляемое со склада 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=10x2=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