14

Решение задачи

оптимального управления

Санкт-Петербург

2006

Содержание

• Содержание
• Введение
• Глава 1. Решение задачи классическим симплекс методом
• Глава 2. Графический метод
• Глава 3. Решение задачи с помощью Excel
• Описание диалога «Поиск решений»
• Решение задачи
• Заключение
• Введение
• Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
• Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
• Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
• количество продукции - расход сырья
• количество продукции - качество продукции
• Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
• При постановке задачи оптимизации необходимо:
• 1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.
• 2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
• 3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
• 4. Учет ограничений.
• Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.
• Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.
• На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
• Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
• В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот - любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
• Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.
• Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
• Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
• Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
• рационального использования сырья и материалов; задачи оптимизации раскроя;
• оптимизации производственной программы предприятий;
• оптимального размещения и концентрации производства;
• составления оптимального плана перевозок, работы транспорта;
• управления производственными запасами;
• и многие другие, принадлежащие сфере оптимального планирования.
• Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.
• В работе используются методы линейного программирования для решения производственной задачи

Вид ресурса

число ресурсов, затрачиваемых на изготовление единицы продукции

всего ресурса

P1

P2

S1

1

3

18

S2

2

1

16

S3

0

1

5

S4

3

0

21

прибыль от одной ед

2

3

• Зная прибыль, получаемую от продажи одной единицы продукции и расход сырья на ее производство, надо составить оптимальный производственны план, дающий максимальную прибыль. В работе мы решим эту задачу классическим симплекс методом, средствами Excel и графическим методом.
• Глава 1. Решение задачи классическим симплекс методом
• Коэффициенты целевой функции
• Переменные целевой функции
• Задача
• при ограничениях
• Введем фиктивные переменные Y, чтобы из неравенств сделать равенства
• Введем в базис
• Решим относительно базисных переменных
• Запишем полученное решение в матричной форме
• Коэффициенты относительных смещений для небазисных переменных отрицательны
• где -коэффициенты целевой функции при базисных переменных
• а - множество индексов при свободных переменных
• Поэтому указанный базис является оптимальным, а оптимальным решением является
• Значение целевой функции
• Глава 2. Графический метод
• Максимизируем функцию
• при ограничениях
• Максимум достигается в точке (отмечена ромбиком)
• Значение целевой функции
• Глава 3. Решение задачи с помощью Excel

Описание диалога «Поиск решений»

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

Поля ввода и кнопки в этом окне выполняют следующие функции:

Установить целевую ячейку служит для указания целевой ячейки, значение которой необходимо максимизировать, мини-мизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.

Равной служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор задан-ного числа). Чтобы установить число, введите его в поле.

Изменяя ячейки служит для указания ячеек, значения кото-рых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимиза-ции значения ячейки, указанной в поле Установить целевую ячейку. Используется для автоматического поиска ячеек, влияю-щих на формулу, ссылка на которую дана в поле Установить це-левую ячейку. Результат поиска отображается в поле Изменяя ячейки.

Ограничения служит для отображения списка граничных условий поставленной задачи.

Добавить служит для отображения диалогового окна Доба-вить ограничение.

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

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

Добавить. Нажатие на эту кнопку позволяет, не возвраща-ясь в окно диалога Параметры поиска решения, наложить новое условие на поиск решения задачи.

Изменить служит для отображения диалогового окна Изме-нить ограничение. Содержание данного окна в точности повто-ряет содержание окна Добавить ограничение.

Удалить служит для снятия указанного ограничения.

Выполнить служит для запуска поиска решения поставлен-ной задачи.

Закрыть служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются ус-тановки сделанные в окнах диалога, появлявшихся после нажа-тий на кнопки Параметры, Добавить, Изменить или Удалить.

Параметры служит для отображения диалогового окна Па-раметры поиска решения, в котором можно загрузить или сохра-нить оптимизируемую модель и указать предусмотренные вари-анты поиска решения.

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

Решение задачи

Средствами Excel мы получили, что надо произвести 6 ед. первой продукции и 4 ед. второй продукции. Максимальная выручка при этом равна 24.

Заключение

В задаче были рассмотрены классические и программные методы решения задачи линейного программирования. Решение задачи во всех случаях было: произвести 6 ед. первой продукции и 4 ед. второй продукции. При этом прибыль составляла 24 ден.ед.