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

Министерство образования и науки Российской Федерации Южно-Уральский государственный университет Кафедра Систем Управления Челябинск, 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 меньше нуля, значит найденное решение не является оптимальным.

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

Выбор в качестве разрешающей строки х2с обусловлен тем, что именно в этой строке отношение свободного члена к переменной х1с минимально. Выполним необходимые преобразования над элементами Симплекс таблицы:

Все коэффициенты при свободных переменных неположительные, следовательно, найденное решение является оптимальным. Запишем его:

x1a=10; x1b=60; x1c=10;

x2a=80; x2b=0; x2c=0;

x3a=0; x3b=0; x3c=80;

L=620;

Для проверки правильности вычислений можно составить транспортную таблицу:

После анализа таблицы можно сделать вывод, что вычислительных ошибок при расчетах сделано не было.

Ответ:

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:

Теперь можно представить систему ограничений в стандартном виде:

Необходимо также выразить целевую функцию через свободные переменные:

Теперь можно заполнить Симплекс-таблицу

Исходя из того, что все свободные члены положительны, можно сделать вывод о том принятое решение является опорным.

Далее нужно выбрать разрешающий элемент. В качестве разрешающего столбца целесообразно принять столбец x1, так как коэффициент при x1 в целевой функции меньше коэффициента при x2. Разрешающей строкой будет строка x5-, так как отношение свободного члена этой строки к коэффициенту при x1 минимально. Отметим найденный разрешающий элемент в таблице, а также заполним необходимые клетки:

Перерисуем таблицу с учётом замены x2 на x3:

Коэффициент при х2 в целевой функции отрицателен, значит необходимо произвести ещё одну замену. В качестве разрешающей строки примем x3. Таким образом, разрешающим будет элемент, стоящий на пересечении строки x3 и столбца x2.

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

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

Ответ:

x1=4

x2=3

x3=0

x4=-5

x5=0

L=14

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

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

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

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

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

ДL1=-5*100=-500

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

г2=12+32−45−22=-23 k2=200 ДL2=-23*200=-4600

г3=10+18−50−25=-47 k3=100 ДL3=-47*100=-4700

г4=10+23−12−50=-29 k4=200 ДL4=-29*200=-6800

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

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

Положим в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 в качестве базисных:

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

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

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