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 меньше нуля, значит найденное решение не является оптимальным.

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

Выбор в качестве разрешающей строки х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

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