48792 (Решение задач исследования операций)
Описание файла
Документ из архива "Решение задач исследования операций", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48792"
Текст из документа "48792"
Курсовая работа
по дисциплине
Исследование операций
Руководитель:
Плотникова Н. В.
«____» ___________ 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 | 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 | 0 |
| x1 | 4 | 2 | 1 |
Коэффициенты при свободных переменных в целевой функции положительны, значит, найденное решение является оптимальным.
