Прараметрическое программирование

Содержание

 

Введение.

В настоящее время  оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных  решений привели к созданию специальных  математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

В настоящее время  создано множество программ, предназначенных  для использования при выработке управленческих решений.

Исключительно большими возможностями обладают пакеты прикладных программ WinQSB. Эти пакеты наиболее крупная коллекция запрограммированных математических методов для решения многих управленческих задач, а именно:

• линейное и целочисленное программирование;
• сетевое моделирование (транспортная задача, задачи о назначениях, о перевозках с промежуточными пунктами, о кратчайшем пути, о максимальном потоке, о нахождении минимального основного дерева и задача коммивояжера);
• сетевое планирование (методы PERT и СРМ);
• целевое программирование;
• нелинейное программирование;
• квадратичное программирование;
• анализ очередей (теория массового обслуживания);
• имитационное моделирование систем массового обслуживания;
• марковские процессы;
• анализ решений (теория принятия решений и теория игр);
• динамическое программирование;
• прогнозирование и линейная регрессия;
• агрегатное планирование;
• управление запасами;
• планировка и размещение оборудования;
• планирование потребности в материалах, деталях и узлах;
• календарное планирование работ;
• выборочный анализ качества;
• карты контроля качества.

Некоторые модули WinQSB объединяют сразу несколько программ, позволяющих решать родственные задачи (например модуль сетевого моделирования). Кроме того, пакет WinQSB очень удобен для решения задач оптимизации, поскольку предоставляет широкие возможности для послеоптимизационного анализа и параметрического программирования.

В данной курсовой работе детально рассмотрено использование  наиболее доступной в настоящее время первой версии пакета WinQSB находящая широкое применение в управлении.

 

1. Задача линейного программирования.

 Описание ситуации.

Требуется определить план выпуска 4 видов мороженного: рожок, брикет, в стаканчике и на палочке  завода по производству полуфабрикатов глубокой заморозки. На изготовление расходуются трудовые ресурсы, сырье и финансы. Границы выпуска каждого вида продукции, а так же наличие и нормы расхода ресурсов, маржинальная прибыль на единицу продукции  приведены в таблице 1:

 

Ресурсы	Продукт 1	Продукт 2	Продукт 3	Продукт 4	Наличие
Прибыль	80	70	120	150
Труд	2	3	2	3	35
Сырье	8	5	6	5	85
Финансы	6	8	10	9	130
нижн. гр.	1	1	2	3
верхн. гр.	6	-	4	5

Таблица 1. Исходные данные.

 

Необходимо создать  производственный план, обеспечивающий наибольшую прибыль, выполнить параметрический анализ при одновременном изменении нескольких а) коэффициентов, б) правых частей ограничений.

Обозначив количество выпускаемой  продукции через x₁, x₂, x₃, x₄, а целевую функцию (валовую маржинальную прибыль) – через  F, построим математическую модель задачи: F = 80x₁ + 70x₂ + 120x₃ + 150x₄       max,

Три неравенства –  ограничения:

2 x₁ + 3 x₂ + 2 x₃ + 3 x₄ ≤ 35,

8 x₁ + 5 x₂ + 6 x₃ + 5 x₄ ≤ 85,

6 x₁ + 8 x₂ + 10 x₃ + 9 x₄ ≤ 130;

 

три неравенства – граничные  условия:

1 ≤ x₁ ≤ 6,

1 ≤ x_2,

2 ≤ x₃ ≤ 4,

2 ≤ x₄ ≤ 5.

 

1.2 Решение с помощью пакета WinQSB.

Запуск программы

Чтобы запустить программу  для решения задачи линейного  и целочисленного программирования, необходимо в главном меню (Пуск) выбрать программную группу WinQSB и выберите в ней программу Liner and Integer Programming.

Задание параметров задачи

Для ввода новой задачи нужно выбрать команду File, затем New Problem. В открывшемся окне задается:

В поле Problem Title – название задачи,

в поле Number of Variables – количество переменных,

в поле Number of Constrains – количество ограничений,

в поле Maximization/Minimization – вариант оптимизации,

Data Entry Format – форма задачи матричная (Spreadsheet Matrix Form) или стандартная (Normal Model Form)

тип переменных – непрерывные неотрицательные (Nonnegative integer), целые неотрицательные (Nonnegative integer), двоичные (Binary (0,1)) или свободные, то есть произвольного знака (Unsigned/unrestricted).

 

Рис. 1. Ввод параметров решения  задачи линейного программирования.

Ввод числовых данных

Если выбрана матричная форма  задачи, откроется окно с таблицей для ввода данных: коэффициентов  целевой функции и ограничений, правых частей ограничений, а так  же выбора их знаков.

Рис. 2.Задание коэффициентов  целевой функции и ограничений

 

В строке Variable — установленные по умолчанию имена переменных. В строке Maximize (или Minimize) вводятся коэффициенты целевой функции. Обозначения С1, С2, СЗ и т. д. — это установленные по умолчанию названия ограничений. В соответствующих строках вводятся коэффициенты этих ограничений, за которыми следуют их знаки (в столбце Direction) и правые части (в столбце R. H. S.). Ниже — две строки для задания граничных условий: LowerBound и UpperBound. В первой из них вводятся нижние границы переменных, а во второй — верхние. По умолчанию все нижние границы равны 0, а все верхние равны бесконечности, которая обозначается большой латинской буквой М. В строке Variable Туре указан заданный вами тип переменных: Continuous (Непрерывная), Integer (Целая), Binary (Двоичная) или Unrestricted (Свободная).

Примечание: при вводе чисел, имеющих дробную часть, используйте в качестве разделителя целой и дробной части точку, а не запятую.

При вводе  данных, набрав число или знак, следует  нажать клавишу Enter, чтобы перейти на следующую позицию ввода. Кроме того, можно выполнять следующие действия:

• Перемещаться по таблице — с помощью клавиши Tab или клавиш со стрелками.

• Выбрать ячейку таблицы — щелчком этой ячейки.

• Редактировать содержимое ячейки таблицы — после щелчка голубого поля над таблицей. При этом выбранная ячейка выделится цветом и можно редактировать ее содержимое.
• Изменить знак ограничения — двойным щелчком знака.  Если двойной щелчок выполнить несколько раз, знаки будут меняться циклически (<=, >=, =).
• Изменить тип переменной — двойным щелчком слова, обозначающего тип этой переменной в строке Variable Type. При нескольких двойных щелчках названия типов будут меняться циклически (Continuous, Integer, Binary, Unrestricted).

С помощью  указанных далее команд меню Edit можно изменить следующие параметры задачи:

• Название задачи — Problem Name.
• Имена переменных — Variable Names.
• Названия ограничений — Constraint Names.

 

• Вариант оптимизации целевой функции — Objective Function Criterion (максимизация меняется на минимизацию или наоборот).
• Количество ограничений — Insert a Constraint или Delete a Constraint (ограничения добавляются или удаляются).
• Количество переменных — Insert a Variable или Delete a Variable (переменные добавляются или удаляются).

Воспользуемся этими командами, чтобы в нашей задаче ввести русские названия переменных и ограничений (рис. 3).

Рис. 3 Изменение названия переменных и ограничений.

С помощью перечисленных  далее команд меню Format могут быть изменены:

• Форма задачи — Switch to Normal Model Form или Switch to Matrix Form (перейти в стандартную или матричную форму). Выбрав любую форму задачи, вы можете построить задачу, двойственную к ней, с помощью команды Switch to Dual Form.
• Формат чисел— Number.
• Шрифт и цвет — Font.
• Выравнивание—Alignment.
• Высота строк — Row Height.
• Ширина столбцов — Column Width.

Чтобы сохранить  данные воспользуйтесь командой File, Save Problem As.

Нахождение  решения

Чтобы решить задачу, выберите в меню Solve and Analyze один из следующих вариантов действий:

• Решить задачу — Solve the Problem. При этом задача решается симплексным методом, если все переменные определены вами как непрерывные, или методом ветвей и границ, если хотя бы одна из них определена как целая или двоичная. По окончании решения появится сообщение о том, что задача решена (The problem is solved.) и либо получено оптимальное решение (Optimal solution is achieved.), либо допустимых решений нет (However, the problem is infeasible!), либо целевая функция не ограничена (However, the problem is unbounded!). Щелкнув кнопку OK в окне с этим сообщением, вы увидите сводный отчет о решении, или анализ недопустимости (если нет допустимых решений), или анализ неограниченности (если не ограничена целевая функция). В дальнейшем можно открывать сводный отчет либо посредством меню Window, либо с помощью команды Results > Combined Report. 
• Решить с показом шагов — Solve and Display Steps. В этом случае показываются все итерации решения. Если все переменные определены как непрерывные, задача решается симплексным методом и отображаются симплекс-таблицы с указанием переменных, вводимых в базис и исключаемых из него. С помощью меню Simplex Iteration вы можете сами выбрать переменную, вводимую в базис (Choose Entering Variable), a также перейти к следующей итерации (Next Iteration), к последней итерации (Go to the Last Tableau) или к концу решения с выводом сводного отчета (Nonstop to Finish). В дальнейшем можно открывать таблицу с последней итерацией либо посредством меню Window, либо с помощью команды Results, Final Simplex Tableau.

Решить графическим  методом — Graphic Method. При выборе этой команды откроется окно (рис.4), в котором нужно указать, какая переменная будет отображаться на горизонтальной оси (X), а какая — на вертикальной (У) Если в задаче более двух переменных, вам будет предложено положить остальные переменные равными их значению в оптимальном решении (Set to optimal), или нулю (Set to zero) или тем значениям, которые вы сами зададите (Assign variables) (окно для задания значений откроется после щелчка кнопки ОК).

 

 

 

Рис. 4 Задание  данных для графического метода решения 

                                           

Анализ оптимального решения и его чувствительности

 

Рис. 5. Сводный отчет о решении задачи линейного программирования.

 

Сводный отчет, появляющийся после завершения вычислений, содержит наиболее полные сведения о найденном оптимальном решении (рис. 5) Кроме того, вы найдете в этом отчете информацию, необходимую для выполнения анализа чувствительности.