Общие рекомендации к графическому решению задач ЛП

Стр 1 из 7Следующая ⇒

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

Государственное образовательное учреждение
высшего профессионального образования

«Омский государственный технический университет»

А.В. Зыкина

МЕТОДЫ ОПТИМИЗАЦИИ

Конспект лекций

Омск 2007

УДК 007(075)

ББК 32.81я73

З-96

Рецензенты:

О.В. Кириченова, канд. физ.-мат. наук, доц. ОмГПУ;

О.П. Диденко, канд. пед. наук, доц. ОмГИС

Зыкина, А.В.

З-96 Методы оптимизации: конспект лекций /А.В. Зыкина. – Омск: Изд-во

ОмГТУ, 2007. – 37 с.

В конспекте лекций приводятся основные теоретические сведения по линейной оптимизации. Излагается графический метод решения задачи линейного программирования, рассматриваются прямой и двойственный симплекс-методы, метод отсечений для задачи целочисленной оптимизации, метод потенциалов для решения транспортной задачи линейного программирования.

Конспект лекций предназначен для студентов специальности 230102 и направления подготовки 23010062.

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

УДК 007(075)

ББК 32.81я73

технический университет, 2007

Введение

При решении широкого комплекса практических задач, в том числе задач создания и эксплуатации АСОИУ, возникают своеобразные модели оптимизации решений, для которых характерны следующие черты:

1) показатель эффективности (целевая функция) является линейной функцией от элементов решения;

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

Такие задачи называются задачами линейного программирования (ЛП).

Первые исследования по ЛП были проведены в конце 30-х годов в Ленинградском университете академиком Л. В. Кантаровичем (первая публикация – в 1939 году). Л. В. Кантарович предложил легко алгоритмизируемый метод решения задач ЛП – метод последовательного улучшения допустимого вектора. Американский математик Дж. Данциг в 1947 году разработал симплекс-метод решения задачи ЛП. По существу симплекс-метод является табличной формой записи метода последовательного улучшения допустимого вектора. В 1951 году Дж. Данциг ввел термин «линейное программирование» (слово «программирование» в данном случае означает не что иное, как «планирование»).

В настоящее время с точки зрения уровня теоретических разработок, сферы приложений и реализации вычислительных методов ЛП является одним из наиболее развитых направлений в области решения оптимизационных задач. Успехи в использовании методов ЛП во многом обусловлены значительным увеличением быстродействия и объема памяти ЭВМ. Достижения в области ЛП в свою очередь содействовали прогрессу в разработке алгоритмов решения других задач математического программирования. Сущность этих алгоритмов состоит в том, что исходная (в общем случае, нелинейная) задача сводится к одной линейной задаче или их совокупности. Таким образом, линейное программирование выделяется среди других методов программирования как основа для многих процедур решения.

При нахождении решений для моделей математического программирования (МП) применительно к реальным задачам процедуры ручного счета практически никогда не используются. Такого рода работа, как правило, осуществляется с помощью ЭВМ. Возникает вполне законный вопрос: не достаточно ли одного умения строить модели? Нет, не достаточно. Значительный опыт по использованию методов математического программирования при решении производственных задач подтвердил, что руководитель должен понимать принцип работы алгоритмов, чтобы добиться действительно эффективного и обоснованного применения этого инструмента организации управления. При практическом применении МП всегда стремятся получить более содержательную информацию, нежели ответ в числовом выражении. Главная цель расчетов – не цифры, а понимание.

Графическое решение задач ЛП

Каноническая форма задачи ЛП

Для численного решения задачи ЛП требуется предварительно привести ее к каноническому виду:

x²

Каноническая форма (КФ) (1) задачи характеризуется следующими тремя признаками:

― однородная система ограничений в виде системы уравнений;

― однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче;

― минимизация (максимизация) целевой функции.

Известно, что для произвольной задачи ЛП можно построить эквивалентную ей каноническую задачу ЛП (эквивалентность двух задач означает, что оптимальному решению одной задачи соответствует оптимальное решение другой)[1,2,3].

Пример

Привести задачу к КФ на минимум:

(2)

В данной задаче (2) нарушены все три признака КФ.

1. Начнем с преобразования смешанной системы ограничений в систему уравнений. Для этого введем в первое и второе ограничения неотрицательные переменные y ₁_,y₂, которые называются дополнительными или слабыми. В результате система ограничений запишется в следующем виде:

(3)

2. Условия неотрицательности в (3) не выполняются только для переменной x ₂. Для приведения задачи к однородным условиям неотрицательности можно воспользоваться двумя приемами.

Первый прием. Представим переменную x₂ в виде разности двух неотрицательных переменных: После преобразования системы ограничений и целевой функции получим задачу

(4)

Второй прием. Найдем из какого-либо уравнения (4) переменную x ₂. Пусть из первого уравнения . Подставим это выражение во все уравнения и в целевую функцию, исключив таким образом переменную x ₂ из задачи. Получим

(5)

3. Переход к задаче минимизации целевой функции L в задаче (5) осуществляется путем введения новой функции из равенства

в первом случае,

во втором случае.

Общие рекомендации к графическому решению задач ЛП

1. Графически могут решаться [1]:

a) задачи, заданные в произвольной форме, содержащие не более двух переменных;

b) задачи, заданные в канонической форме, с числом свободных переменных ;

c) задачи в произвольной форме записи, которые после приведения к канонической форме будут содержать не более двух свободных переменных .

2. Основной формой для графического решения является 1-й тип задач. Поэтому, если встречается 2-й или 3-й тип задач, то предварительно их модель должна быть приведена к первому типу.

3. Решение задач 1-го типа выполняется в два этапа:

этап 1 – построение области допустимых решений;

этап 2 – построение в допустимой области оптимального решения.

4. При построении области допустимых решений может встретиться один из трех случаев:

а) пустая область – задача не имеет решения из-за несовместности системы ограничений в области допустимых решений;

б) выпуклый многоугольник – задача всегда имеет оптимальное решение;

в) неограниченная выпуклая многогранная область – в зависимости от направления вектора c (вектора коэффициентов целевой функции L) задача может иметь или не иметь решение. Последнее связано с неограниченностью целевой функции в области допустимых решений.

5. Если оптимальное решение существует, то возможен один из трех исходов:

а) оптимальное решение единственное и совпадает с одной из вершин области;

б) оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины области и :

в) оптимальные решения соответствуют всем точкам допустимого луча, исходящего из вершины области :

Пример

Решить графически задачу ЛП, заданную в канонической форме:

(6)

(7)

(8)

Число уравнений задачи m=3, число неизвестных n=5. Тогда n-m=2 и задача может быть сведена к задаче на плоскости относительно свободных переменных. Возьмем в качестве базисных переменные и выразим их через свободные (небазисные переменные):

(9)

По условию (8) переменные могут принимать только неотрицательные значения, т. е. допустимой областью задачи ЛП (6) - (8) будет область, определяемая условиями (8), (9), или

(10)

Чтобы получить задачу ЛП относительно переменных , подставим значения базисных переменных (9) в целевую функцию (6). В результате получим

(11)

Задача (10), (11) эквивалентна задаче (6) - (8), поэтому решая графически задачу (10), (11), получим решение задачи (6) - (8).

Этап 1. Построение допустимой области.

Каждое из неравенств (10) определяет некоторую полуплоскость :

Так, неравенство определяет правую полуплоскость. Неравенство определяет полуплоскость, лежащую по ту сторону от прямой , где . Подставляя значения в это неравенство, получим 0>-2, значит, координаты (0,0) удовлетворяют первому неравенству (10) и область решений этого неравенства включает начало координат. Аналогично определяют полуплоскости остальных неравенств (10).

На рисунке прямые, соответствующие условию , отмечены цифрой в скобках.

Получили допустимую область M – выпуклый пятиугольник OABCD.

Этап 2. В допустимой области M находим оптимальное решение.

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

В результате получаем искомое оптимальное решение . Подставляя значения и в целевую функцию и в равенства (9), получим оптимальное значение целевой функции и оптимальное решение:

Дата добавления: 2021-12-10; просмотров: 18; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 5 6 7 Следующая ⇒

Мы поможем в написании ваших работ!