Решение задач исследования операций
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 | | |
Страницы: 1, 2
|
