Автор работы: Пользователь скрыл имя, 16 Января 2013 в 01:05, курсовая работа
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
Этот анализ позволяет выяснить, как изменения коэффициентов целевой функции и правых частей ограничений могут повлиять на найденное оптимальное решение. При этом, однако, предполагается, что изменяется только один коэффициент целевой функции или правая часть только одного ограничения. Сведений о том, что произойдет при одновременном изменении нескольких входных данных задачи, сводный отчет не дает.
Сводный отчет состоит из двух таблиц. В первой таблице выводится следующая информация, касающаяся переменных:
В столбце Reduced Cost— нормированные стоимости — двойственные оценки (в нашем случае — 0, 0, 0, 0). Такая оценка может быть отлична от нуля только для переменной, имеющей в оптимальном плане нулевое значение, и показывает, на какую величину следует изменить коэффициент этой переменной в целевой функции, чтобы ее значение стало положительным (например, насколько увеличить цену изделия, чтобы его производить стало выгодно). Кроме того, эта оценка показывает, на какую величину ухудшится значение целевой функции, если уйти от оптимального плана (нулевого значения переменной), добавив в него единицу соответствующей продукции.
• В последней строке таблицы — оптимальное значение целевой функции (в нашей задаче — Objective Function (Max.) = 1 624.2860).
Вторая таблица сводного отчета содержит следующие сведения об ограничениях задачи:
• В столбце Slack or Surplus — остатки или избытки, вычисленные по правилу: «правая часть минус левая» для ограничений типа <= или «левая часть минус правая» для ограничений типа >=. Они могут показывать, например, величину неиспользованного ресурса (для лимитирующих ограничений, то есть ограничений сверху) или превышение требуемого уровня (для ограничений-требований, то есть ограничений снизу). Если остаток или избыток равен нулю, то соответствующее ограничение является связанным (активным), а соответствующий ресурс — дефицитным (используемым полностью). В противном случае ограничение несвязанное, а ресурс недефицитен. В нашей задаче связанным является первое ограничение, а дефицитны трудовые ресурсы.
После нахождения решения становится доступным меню Results. С его помощью можно узнать, сколько итераций и времени работы процессора потрачено на поиск решения (Show Run Time and Iteration), а также впоследствии снова вызвать сводный отчет (Combined Report).
Хотя сводный отчет полностью содержит все сведения о результатах решения и их чувствительности, можно получить и несколько более мелких, частных отчетов, которые выводятся с помощью команд меню Results:
• Отчет по результатам — Solution Summary. Показывает оптимальные значения переменных и их итоговый вклад в оптимальное значение целевой функции, нормированные стоимости, а также состояние переменных: входят они в окончательный базис или нет.
Новый выбранный отчет всегда заменяет предыдущий (старый не сохраняется). Просмотрев сводный или частные отчеты, вы можете с помощью меню Window вернуться в окно с исходными данными. Данные можно изменить и решение повторить, получив при этом новый отчет.
Когда получено оптимальное решение задачи и на экране — окно с ее исходными данными, можно получить альтернативные решения с помощью команды Solve and Analyze, Alternative Solution. Она открывает окно, содержащее два списка: в левом — текущий базис, а в правом — небазисные переменные вместе с двойственными оценками Cj-Zj, указанными в скобках.
В правом списке нужно выбрать переменную, которую следует ввести в базис. После щелчка кнопки ОК программа автоматически выберет переменную, исключаемую из базиса, и найдет новое решение. Если вы выбрали небазисную переменную с Cj-Zj = 0, то значение целевой функции не изменится, то есть будет найдено альтернативное оптимальное решение. Если же вы выбрали переменную с Cj-Zj ≠ 0, то значение целевой функции может измениться. Предупреждение об этом появится после щелчка кнопки ОК.
Рис. 6 Получение альтернативных решений.
Параметрический анализ позволяет выяснить, как изменяется оптимальное значение целевой функции при изменении ее коэффициентов или правых частей ограничений. При этом предполагают, что изменяемые величины зависят от некоторого параметра (например, времени), и находят, как от этого же параметра зависит оптимальное значение целевой функции.
Параметрический анализ можно выполнить с помощью команды Perform Parametric Analysis только после нахождения оптимального решения. Она находится в меню Solve and Analyze, когда на экране открыто окно с исходными данными задачи, или в меню Results, когда на экране - отчет, сводный или частный, о результатах решения. Эта команда открывает окно для выбора варианта параметрического анализа.
Рис. 7. Выбор варианта параметрического анализа.
По умолчанию в этом окне выбран параметр Objective Function, предполагающий анализ изменений коэффициентов целевой функции. Если вы хотите проанализировать изменение одного коэффициента, выберите в списке справа переменную, к которой он относится. После щелчка кнопки ОК появится таблица с результатами параметрического анализа.
Если же одновременно изменяются несколько коэффициентов, то нужно сделать следующее: в списке выбрать пункт Perturbation Vector, щелкнуть кнопку ОК и в открывшемся окне задать вектор изменения, показывающий, как изменяется каждый коэффициент целевой функции.
Рис. 8. Задание вектора изменения правых частей ограничений
Пусть, например, целевая функция нашей задачи изменяется следующим образом: F = (80+μ)x1 + 70x2 + (120+2μ)x3 + (150+3μ)x4, где μ — изменяющийся параметр. Вектор изменения в этом случае — (1,0, 1, 2). Он состоит из коэффициентов параметра μ и задается в окне, показанном на рис. 8. После щелчка в этом окне кнопки ОК появится таблица с результатами параметрического анализа.
Если изменяются правые части ограничений, нужно выбрать параметр Right Hand Side. Если вас интересует изменение одного ограничения, выберите в списке справа его название и щелкните кнопку ОК.
Если одновременно изменяются несколько ограничений, то в этом же списке выберите Perturbation Vector и щелкните ОК. В открывшемся окне задайте вектор изменения, показывающий, как изменяется правая часть каждого ограничения (в том числе и ограничений сверху в граничных условиях задачи).
Рис. 9. Результаты параметрического анализа при изменении правых частей ограничений
В первых трех столбцах полученной таблицы (Рис. 9.)— номера и границы интервалов изменения параметра μ. (Если бы рассматривалось изменение только одного коэффициента целевой функции или одной правой части ограничения, то это были бы интервалы изменения этого коэффициента или этой правой части, а не параметра μ.) Интервалы расположены в следующей последовательности. Сначала перечислены интервалы с μ = 0 до +∞, затем — с μ = 0 до -∞ (в таблице бесконечность обозначается словом Infinity).
В столбцах From OBJ Value и То OBJ Value — значения целевой функции на границах интервалов изменения параметра μ. В столбце Slope — угловой коэффициент целевой функции. Наконец, в последних столбцах Leaving Variable и Entering Variable — имена переменных, которые исключаются из базиса и вводятся в него при переходе к следующему по порядку интервалу изменения параметра μ.
В последних двух столбцах используются следующие обозначения. Буквы UB, добавляемые к именам переменных, обозначают ограничения сверху значений этих переменных, а слова Slack или Surplus перед названиями ограничений — дополнительные переменные, остаточные или избыточные, используемые в симплексном методе для превращения ограничений-неравенств в равенства.
Если в столбце Leaving Variable указана переменная, а в столбце Entering Variable — нет, данный интервал изменения параметра μ является последним, в котором имеется решение, а в следующем — решение отсутствует. Интервалы без допустимых решений обозначаются в столбце From OBJ Value словом Infeasible.
К результатам параметрического анализа можно возвращаться из других окон WinQSB посредством меню Window или с помощью команды Results, Show Parametric Analysis меню.
Результаты предварительно выполненного параметрического анализа можно представить в графической форме. Для этого воспользуйтесь командой Results, Graphic Parametric Analysis. При этом выводится график решающей функции, показывающий зависимость целевой функции от параметра μ (Если изменяется только один коэффициент целевой функции или одна правая часть ограничения, то показывается зависимость именно от этого коэффициента или этой правой части).
Рассмотренные ранее результаты параметрического анализа представлены графически:
Рис. 10. График решающей функции при изменении правых частей ограничений.
Графический анализ чувствительности
Рис. 10. График решающей функции при изменении правых частей ограничений.
Если выбран графический метод решения, то построенное графическое изображение можно использовать для анализа чувствительности модели.
Чтобы выполнить анализ чувствительности, выберите команду Sensitivity, Objective Function and Constraints. Появится окно, в котором можно внести изменения в любые параметры задачи.
Рис. 11. Графическое решение.
На трех лесоводствах в преддверии нового года имеются елки в количестве 200, 300, 400 ед., который необходимо доставить на четыре елочных базара в количестве, соответственно 300, 200, 150, 250 ед. Нужно составить такой план перевозок, при котором общие затраты минимальны.
Затраты на перевозку одну елку заданы матрицей, в которой номер строки соответствует номеру лесоводства, а номер столбца – номеру магазина.