Курсоваяработа
подисциплине
Исследованиеопераций
Руководитель:
Плотникова Н. В.
«____»___________ 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
1
-1
0
-1
1
1
-1 x1b
60
0
0
1
0
1
0
0 x2a
70
10
1
-1
1
0
1
-1
-1
1 x2c
10
10
-1
-1
0
-1
-1
1
1 x3c
80
0
1
0
0
1
0
0
Выбор в качестве разрешающейстроки х2с обусловлен тем, что именно в этой строке отношение свободного членак переменной х1с минимально. Выполним необходимые преобразования над элементамиСимплекс таблицы: bi x3a x2b x3b x2c L 620 -2 -1 -1 x1a 10 1 -1 -1 x1b 60 1 1 x2a 80 1 1 x1c 10 -1 -1 1 x3c 80 1 1
Все коэффициенты при свободныхпеременных неположительные, следовательно, найденное решение являетсяоптимальным. Запишем его:
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 80 3 80 80 90 60 90
После анализа таблицы можносделать вывод, что вычислительных ошибок при расчетах сделано не было.
Ответ:
x1a=10 x1b=60 x1c=10
x2a=80 x2b=0 x2c=0
x3a=0 x3b=0 x3c=80
L=6202.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 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
M
0
M
0
-M
0 z1
9
8
2
3
-1
1
2
-3
-1
0
1 z2
8
8
3
3
1
1
-3
-3
0
1
1 W
0
-1
0
0
0
0
0 bi x1 z2 U2 V1 V2 φ
-17M
17M
-5M
M
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
3/5
1
-3/5 W
17/5
-1
1/5
1/5
-1/5
-1/5
1/5 bi z1 z2 U2 V1 V2 φ M M 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