 |
 |
 |
|
|||||||||
|
 | |||||||||||
|
 |
||||||||
|
МЕНЮ
|
БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Решение задач исследования операцийРешение задач исследования операций8 Министерство образования и науки Российской Федерации Южно-Уральский государственный университет Кафедра Систем Управления Челябинск, 2005 Курсовая работа по дисциплине Исследование операций Руководитель: Плотникова Н. В. «____» ___________ 2005 г. Автор: Студент группы ПС-346 Попов А. Е.. «____» ___________ 2005 г. Работа защищена с оценкой «____» ___________ 2005 г.
Выбор в качестве разрешающей строки х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:Теперь можно представить систему ограничений в стандартном виде:Необходимо также выразить целевую функцию через свободные переменные:Теперь можно заполнить Симплекс-таблицу
Коэффициент при х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=10x2=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 |
РЕКЛАМА
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА | ||
 |
© 2010 | |