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

А.В. Зыкина

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

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

Омск 2007

УДК 007(075)

ББК 32.81я73

З-96

Рецензенты:

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

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

Зыкина, А.В.

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

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

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

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

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

УДК 007(075)

ББК 32.81я73

Редактор Н.Н. Пацула

ИД № 06039 от 12,10,2001

Сводный темплан 2007 г.

Подписано к печати 20.02.07. Бумага офсетная.

Формат 60´84 1/16. Отпечатано на дупликаторе.

Усл. печ. л. 2,25. Уч.-изд. л. 2,25

Тираж . экз. Заказ

Издательство ОмГТУ. 644050, г. Омск, пр-т Мира,11

Типография ОмГТУ

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

Введение

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

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

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

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

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

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

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

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