Решение задач исследования операций
Целевая функция. Базисная переменная. Симплекс метод, таблица. Коэффициенты при свободных переменных в целевой функции. Задача квадратичного программирования, максимизации функции. Функция Лагранжа. Координаты стационарной точки. Система ограничений.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 29.09.2008 |
| Размер файла | 48,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
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 на бензоколонку 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 |
11 |
-11 |
-3-1 |
|
|
x3 |
21 |
-11 |
2-1 |
|
|
x4 |
2-1 |
1-1 |
11 |
|
|
x5 |
11 |
11 |
-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
Подобные документы
Математическая модель задачи. Симплекс-таблица. Решение задачи линейного программирования. коэффициенты при переменных в целевой функции. Метод северо-западного угла. Система неравенств в соответствии с теоремой Куна-Таккера. Функция Лагранжа.
контрольная работа [59,5 K], добавлен 29.09.2008Число линейно независимых уравнений. Отрицательная базисная переменная. Симплекс-метод решения задач линейного программирования. Экстремальное значение целевой функции. Метод северо-западного угла. Задачи нелинейного программирования. Функция Лагранжа.
контрольная работа [257,5 K], добавлен 29.09.2008Математическая модель задачи. Целевая функция. Симплекс метод, таблица. Оптимальное решение симплекс-метода. Метод северо-западного угла, потенциалов. Определение стационарной точки. Проверка стационарной точки на относительный минимум и максимум.
контрольная работа [1000,1 K], добавлен 29.09.2008Математическая модель задачи. Целевая функция, ее экстремальное значение и экстремум. Cвободные переменные. Метод симплекс-таблиц. Коэффициенты при переменных в целевой функции. Линейное программирование. Матричная форма. Метод северо-западного угла.
контрольная работа [72,0 K], добавлен 29.09.2008Определение стационарной точки. Проверка стационарной точки на относительный максимум или минимум. Составление функции Лагранжа. Применение к функции Лагранжа теорему Куна-Таккера. Метод потенциалов, северо-западного угла. Свободные переменные.
курсовая работа [466,4 K], добавлен 29.09.2008Математическая модель задачи. Система ограничений. Составление симплекс-таблиц. Разрешающий элемент. Линейное программирование. Коэффициенты при свободных членах. Целевая функция. Метод потенциалов, северо-западного угла. Выпуклость, вогнутость функции.
контрольная работа [47,2 K], добавлен 29.09.2008Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.
реферат [478,6 K], добавлен 29.09.2008Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Целевая функция с определенным направлением экстремума и система ограничений для нее. Разработка алгоритма программы, ее листинг.
курсовая работа [385,6 K], добавлен 15.05.2014Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013
