Постановка линейной задачи оптимизации

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

(ВлГУ)

 

Кафедра «Автоматизация технологических процессов»

 

Оптимизация процессов обработки

 

Методические указания к выполнению

лабораторных работ

 

Составитель к.т.н. доцент каф. АТП

Шлегель А.Н.

 

Владимир, 2002

Лабораторная работа №1

Решение и анализ оптимизационных задач средствами Excel

Введение

Важность принятия оптимальных решений не только в экономике при распределении ресурсов, но и в технике при проектировании и эксплуатации технических объектов, не вызывает сомнений. Но найти оптимальное решение для реальной задачи вручную, без применения компьютера, практически невозможно из-за очень большого объёма вычислений. Наличие компьютера является необходимым, но не достаточным условием нахождения оптимального решения. Для успешного решения необходимы три составляющие:

· математическая модель;

· компьютер с соответствующим программным обеспечением;

· достоверные исходные данные.

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

Для решения системы уравнений можно использовать различные пакеты прикладных программ (MathCad, MatLab, Maple, Mathematica и др.), но наибольший эффект при решении оптимизационных задач дает использование ЭТ Excel. Этот пакет прикладных программ даёт возможность не только найти оптимальное решение, но и исследовать полученное решение, пользователь может проанализировать решение, изменять значения исходных данных, снять или ослабить какие-то ограничения и повторить решение.

В данном методическом пособии рассматриваются вопросы решения линейных оптимизационных задач симплекс-методом с помощью электронной таблицы (ЭТ) Excel.

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

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

Для выполнения данной работы пользователь должен иметь основные навыки работы с ЭТ Excel, т.к. в данной работе эти вопросы не рассматриваются. В соответствии с вышесказанным, в данных методических указаниях поиск оптимального решения находится в результате выполнения трех частей данной лабораторной работы:

- Часть 1 – Поиск оптимального решения для контрольного примера;

- Часть 2 – Анализ полученного решения (в том числе, отсутствия подходящего решения), допустимые изменения исходных данных и ограничений и нахождение оптимального решения для изменённых данных.

- Часть 3 – Решение и анализ индивидуальной задачи.

Часть 1. Поиск оптимального решения (для контрольного примера)

Постановка линейной задачи оптимизации

Оптимизационными задачами называются такие задачи, в которых требуется найти экстремальное значение некоторой функции при заданных ограничениях. Такими ограничениями могут быть граничные значения (верхние и/или нижние) переменных или функции этих переменных. Функцию, экстремум которой ищется, принято называть целевой функцией. Если целевая функция и ограничения линейны, данная задача относится к разделу математики носящему название линейного программирования. В свою очередь, линейное программирование является частью одного из разделов прикладной математики – математического программирования.

Для аналитического решения задачи линейного программирования, которая является частным случаем оптимизации, разработан специальный алгоритм, который называется симплекс-методом. Описание аналитического метода весьма сложно, поэтому в данных методических описывать его не будем (см. [3]), а рассмотрим лишь те его основные положения, которые используются в Excel

В общем виде задачу оптимизации можно сформулировать так.

· Имеется некая функция F искомых переменных x_j, называемая целевой функцией (ЦФ), экстремум которой требуется найти.

· На искомые переменные накладываются определенные ограничения (ОГР), которые могут быть как односторонними g_i(x_j)<=b_i, так и двусторонними a_i<= g_i(x_j)<= b_i.

· Искомые переменные в оптимальном решении должны находится в определенных граничных условиях (ГРУ) - k_j<=x_j<=v_j.

Целевая функция или критерий оптимизации, показывает в каком смысле решение должно быть оптимальным, т.е. наилучшим – максимальным, минимальным или равным заданной величине.

В общем виде математическую модель оптимизации можно записать:

 

ЦФ F=f(x_j) = ® max (min, const)

ОГР <= b_i..........................(1.1.1)

ГРУ k_j<=x_j<=v_j

 

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

Важной характеристикой задачи оптимизации является её размерность, определяемая числом переменных n и числом ограничений m. Возможны три соотношения этих величин:

- n<m - в этом случае задача не имеет решения;

- n=m -, задача имеет только одно решение и вряд ли такую задачу можно считать оптимизационной;

- n>m - задача имеет бесчисленное множество допустимых решений, из которых надо выбрать оптимальное.