Конспект лекций МЕТОДЫ ОПТИМИЗАЦИИ

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

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

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

 

А.В. Зыкина

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

 

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

 

Омск 2007

ББК 32.81я73 З-96  

УДК 007(075)

ББК 32.81я73

 

 

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

ИД № 06039 от 12,10,2001

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

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

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

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

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

 

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

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

 

 

© А.В. Зыкина, 2007

© Омский государственный

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

Введение

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

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

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

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

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

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

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

 

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

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

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

(1)

………………………

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

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

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

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

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

Пример построения канонической формы

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

(2)

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

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

(3)

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

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

(4)

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

(5)

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

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

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

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

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

Пример графического решения

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

(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), получим оптимальное значение целевой функции и оптимальное решение:

Численные методы решения задач ЛП

Симплекс-метод

(12) ……………………… (13)

Алгоритм симплекс-метода для задачи на минимум

Приводим задачу ЛП к специальной форме (15). Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме: …  

Алгоритм симплекс-метода для задачи на максимум

Алгоритм симплекс-метода для задачи на максимум отличается от алгоритма для задачи на минимум только знаками индексной строки коэффициентов в целевой функции , а именно:

На шаге 2: :

На шаге 3 . Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4: .

Пример решения задачи симплекс-методом

Решить задачу, записанную в виде (15).

Составим симплексную таблицу:

L

 

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базиса L=0.

Выбираем ведущий столбец – это столбец, соответствующий переменной .

Выбираем ведущую строку. Для этого находим . Следовательно, ведущая строка соответствует переменной .

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

 

 

L	-2		-2
			-1

 

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисе L= -2.

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

L

 

Еще одна итерация завершена. Переходим к новой итерации.

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

Метод искусственного базиса

(16) Характерная особенность задачи (16) – известное базисное допустимое решение …

Пример решения задачи методом искусственного базиса

Выделить допустимое базисное решение для задачи ЛП:

Приведем задачу к канонической форме на минимум с неотрицательными правыми частями:

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

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

Полученная вспомогательная задача имеет вид

Приведем задачу к виду (16):

Выпишем соответствующую симплексную таблицу:

	B
				-1
			-2
				-1

 

 

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

Итак, искусственная переменная z выйдет из базиса, а переменная введется в базис.

Симплексная таблица преобразуется к виду:

	B
			-1
		11/2	1/2	-1/2
	5/2	5/4	1/4	-1/4
	5/2	3/4	-1/4	1/4

 

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

Тогда исходная задача будет иметь вид специальной формы задачи ЛП:

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

Двойственный симплекс-метод

Метод работает с теми же симплексными таблицами, что и прямой симплекс-метод для задачи на минимум. Сначала определяется переменная, подлежащая… Вычислительная схема двойственного симплекс-метода Шаг 0. Начинаем с симплексной таблицы, где .   B … L …

Пример решения задачи двойственным симплекс-методом

Решить задачу ЛП двойственным симплекс-методом:

Приводим задачу к каноническому виду:

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

	b
L		-1	-1
	-2	-1		-1
	-1	-2	-1

 

Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку – это строка переменной , ведущий столбец – это столбец переменной . После преобразования таблица принимает вид

	b
L		-1	-1
			-1	-1
	-3	-3

 

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

 

 

	b
L		-1/3	-1	-1/3
		1/3	-1	-2/3
		-1/3		-1/3

 

которая является оптимальной. Соответствующее оптимальное решение имеет вид .

 

Двойственность в ЛП

Постановка задачи

Рассмотрим пару задач ЛП вида:

(I) (II)

… …

… …

… …

… …

.

Задачу (I) называют прямой задачей ЛП, а (II) – двойственной. Неравенства задач (I) и (II), соответствующие друг другу (по стрелке), называются сопряженными. Заметим, что задача двойственная к (II), есть исходная прямая задача, т. е. соотношение двойственности взаимное. Поэтому можно из такой пары задач любую считать прямой, а другую – двойственной.

Пример построения двойственной задачи

Построить двойственную задачу к следующей задаче ЛП:

Прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной: согласовать знаки неравенств в ограничениях задачи с целевой функцией. Так как ЦФ минимизируется, то неравенства должны быть записаны с помощью знака «». Для этого второе неравенство умножим на -1:

Теперь, вводя двойственные переменные , запишем в соответствии с указанным правилом пару двойственных задач:

 

Задача слева – исходная прямая задача, задача справа – двойственная к исходной задаче.

Теоремы двойственности

Первая теорема двойственности. Если одна из пары двойственных задач (I) и (II) разрешима, то разрешима и другая задача, причем оптимальные значения… где – оптимальные планы задач (I) и (II) соответственно.

Пример решения пары двойственных задач

Используя теоремы двойственности, решить двойственную задачу, если известно решение прямой задачи:

(20)

Пусть решение задачи найдено одним из стандартных методов: . Построим двойственную задачу:

(21)

По первой теореме двойственности задача разрешима, причем . Найдем оптимальный план задачи (21), используя вторую теорему двойственности. Подставим координаты вектора в ограничения задачи (20). Получим

 

 

Следовательно, в силу УДН, неравенство должно выполняться как равенство, т. е. . Далее так как , то в силу УДН

.

Получаем систему линейных уравнений и решаем ее:

 

Планы и удовлетворяют УДН, следовательно, в силу второй теоремы двойственности, являются оптимальными в задачах (20) и (21) соответственно.

 

Пример проверки вектора на оптимальность

Исследовать вектор на оптимальность в задаче ЛП:

Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:

Так как второе ограничение выполняется как строгое неравенство, то в силу УДН для оптимальности вектора необходимо выполнение равенства .

Построим двойственную задачу:

Поскольку , то из третьего и четвертого ограничений получаем . Но по УДН из условия следует, что должно выполняться равенство в первом ограничении двойственной задачи:

Подставляя значения , получим Следовательно, УДН не выполняются и вектор не является оптимальным в исходной задаче.

Метод Гомори

Постановка задачи ЦЛП

(22) Симплекс-метод не гарантирует целочисленности решения задачи (22), поэтому для… С помощью симплекс-метода решается задача ЛП без условия целочисленности. Если оптимальное решение получается…

Алгоритм метода Гомори

Шаг 2. Пусть оптимальная таблица имеет вид:   b … L … …   Если элементы – целочисленные, то оптимальное решение является целочисленным. В этом случае вычисления заканчиваем.…

Замечания

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

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

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

Пример решения задачи ЦЛП

 

Решить задачу ЦЛП:

Решаем задачу без условия целочисленности симплекс-методом. Оптимальная таблица имеет вид

 

	b
L	-14/3	-4/3	-2/3
	5/3	1/3	2/3
	4/3	2/3	-2/3

 

Оптимальное решение не является целочисленным. Выберем среди нецелочисленных переменных переменную с максимальной дробной частью и построим соответствующее отсечение:

Приписывая это ограничение к симплексной таблице, и проводя стандартное преобразование двойственным симплекс-методом, получим:

 

	b
L	-14/3	-4/3	-2/3
	5/3	1/3	2/3
	4/3	2/3	-2/3
	-2/3	-1/3	-2/3

 

 

	b
L	-4	-1	-1
			-1
		1/2	-3/2

 

Полученная таблица является оптимальной. Соответствующее оптимальное решение является целочисленным. Значение функции на этом решении .

 

Транспортная задача ЛП

Постановка задачи

- объем производства (запас) i-го поставщика,; - объем потребления (спрос) j-го потребителя, - стоимость перевозки (транспортные затраты) единицы продукции от i-го поставщика к j-му потребителю.

Построение опорного плана транспортной задачи

    … n … … … … … …   Базисными клетками транспортной таблицы являются клетки с отличными от нуля положительными перевозками, остальные…

Метод северо-западного угла

Возможны три случая: Если , то . Это означает, что первый поставщик отгрузил весь продукт первому… Если , то , то есть спрос первого потребителя полностью удовлетворен и поэтому , а остаток продукта в первом пункте…

Пример построения опорного плана методом северо-западного угла

Найти опорный план транспортной задачи:

				=

 

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

Метод минимальной стоимости

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

Пример построения опорного плана методом минимальной стоимости

Опорный план, построенный по методу минимальной стоимости.

	9	57	301
	152	153	8
				=

 

Метод потенциалов

Ценой цикла называется изменение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме… Идея метода потенциалов состоит в следующем [1,3]. Для любой свободной клетки… Для нахождения циклов с отрицательной ценой вводится система платежей и определяются величины , называемые…

Вычислительная схема метода потенциалов

Шаг 1. Строим опорный план (методом северо-западного угла или методом минимальной стоимости) с базисными клетками.

Шаг 2. Определяем платежи из условий: для всех базисных клеток (ij). Один из платежей (в строке или в столбце которого максимальное число базисных клеток) полагаем равным нулю.

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

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

Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

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

Решить методом потенциалов транспортную задачу:

 

	3	8	2
	7	4	8
				=

 

Опорный план этой задачи найден методом северо-западного угла.

Приписываем к таблице строку для платежей и столбец для платежей . Псевдостоимости записываем в левом углу клетки, а стоимости – в правом.

Из условий в базисных клетках получаем систему уравнений:

Полагая , находим платежи и псевдостоимости для свободных клеток. Получаем таблицу

 

	15 3	[-] 20 8	12[+] 2
	-1 7	[+] 0 4	[-] 30 8		-4
				=

Стоимость перевозок по плану этой таблицы:

.

Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки (1,3) цикл. Цена цикла . По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на . Для нового плана вычисляем новые значения платежей и псевдостоимостей:

	[-]15 3	-2 8	[+] 20 2
	9 [+] 7	20 4	[-] 10 8
				=
		-2

 

Стоимость перевозок по плану этой таблицы:

.

Полученная таблица имеет клетку (2,1) с отрицательной ценой . По циклу этой клетки переносим 10 единиц груза, при этом стоимость плана уменьшается на единиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:

 

	5 3	0 8	30 2
	10 7	20 4	5 8
				=

 

Стоимость перевозок по плану этой таблицы:

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

Библиографический список

1. Мину, М. Математическое программирование. Теория и алгоритмы / М. Мину. – М.: Наука, 1990.- 485 с.

2. Оуэн, Г. Теория игр / Г. Оуэн – М.: Мир, 1967.

3. Зайченко, Ю.П. Исследование операций / Ю.П. Зайченко. – Киев: Высш. шк., 1975.

4. Базара, М. Нелинейное программирование. Теория и алгоритмы. / М. Базара, К. Шетти – М.: Мир, 1982.- 583 с.

5. Зыкина, А.В. Задания для самостоятельной работы по курсу «Системный анализ и исследование операций»: метод. указ. /А.В. Зыкина – Омск: ОмГТУ, 1995.- 68 с.

6. Зыкина А.В. Теория игр и исследование операций: метод. указ. и контрольные задания для студентов заочного отделения экономического факультета

/ А.В. Зыкина, Л.А. Заозерская, В.П. Ильев – Омск: ОмГУ, 1999.- 48 с.

7. Теория принятия решений: Сб. заданий для практических занятий / А.В. Зыкина, О.Н. Канева – Омск: ОмГУ, 2006.- 56 с.

 

Оглавление

ВВЕДЕНИЕ……………………………………………………………………………... 3

1. ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧ ЛП……………………………..………….. 4

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

1.2. Пример построения канонической формы………………………………….…...4

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

1.4. Пример графического решения……………………………………………..……8

2. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛП………………………………. 10

2.1. Симплекс-метод ……………………………………………………………...… 10

2.2. Алгоритм симплекс-метода для задачи на минимум………………………… 11

2.3. Алгоритм симплекс-метода для задачи на максимум …………………………12

2.4. Пример решения задачи симплекс-методом…………………………………...13

2.5. Метод искусственного базиса…………………………………………….……..14

2.6. Пример решения задачи методом искусственного базиса…………………….16

2.7. Двойственный симплекс-метод…………………………………………………19

2.8. Пример решения задачи двойственным симплекс-методом…………………..20

3. ДВОЙСТВЕННОСТЬ В ЛП…………………………………………………………21

3.1. Постановка задачи………………………………………………………………..21

3.2. Пример построения двойственной задачи……………………………………...22

3.3. Теоремы двойственности………………………………………………………...22

3.4. Пример решения пары двойственных задач……………………………………23

3.5. Пример проверки вектора на оптимальность…………………………………..24

4. МЕТОД ГОМОРИ……………………………………………………………………25

4.1. Постановка задачи ЦЛП…………………………………………………………25

4.2. Алгоритм метода Гомори………………………………………………………..26

4.3. Пример решения задачи ЦЛП…………………………………………………...27

5. ТРАНСПОРТНАЯ ЗАДАЧА ЛП…………………………………………………….28

5.1. Постановка задачи………………………………………………………………..28

5.2. Построение опорного плана транспортной задачи…………………………….29

5.3. Метод северо-западного угла……………………………………………………30

5.4. Пример построения опорного плана методом северо-западного угла………..31

5.5. Метод минимальной стоимости…………………………………………………31

5.6. Пример построения опорного плана методом минимальной стоимости…….31

5.7. Метод потенциалов………………………………………………………………32

5.8. Вычислительная схема метода потенциалов…………………………………...32

5.9. Пример решения транспортной задачи методом потенциалов………………..33

БИБЛИОГРАФИЧЕСКИЙ СПИСОК…………………………………………………..35