Привести задачу ЛП к канонической форме

Методы оптимизации

Сборник заданийдля практических занятий

Омск 2007

Составитель: А. В. Зыкина

Данные методические указания предназначены для обеспечения практических занятий по дисциплине «Методы оптимизации». Предлагаемые задания для практических занятий могут быть использованы как варианты для самостоятельной работы.

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

Для студентов специальности 230102 и направления подготовки 23010062

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

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

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

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

ПРИМЕРЫ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ

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

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

(1)

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

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

(2)

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

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

(3)

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

(4)

(5)

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

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

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

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

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

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

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

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

Решить задачу, записанную в виде:

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

L

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

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

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

L	-2		-2
			-1

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

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

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

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

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

,

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

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

Базиса

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

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

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

Во вторую строку ограничений вводим искусственную переменную 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

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

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

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

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

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

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

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

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

	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

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

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

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

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

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

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

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

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

(12)

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

(13)

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

	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

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

1.10. Пример построения опорного плана методом

Северо-западного угла

=

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

1.11. Пример построения опорного плана методом

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

		9	57	301
		152	153	8
				=

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

Потенциалов

	3	8	2
	7	4	8
				=

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

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

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

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

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

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

.

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

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

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

.

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

		0 8
			5 8
				=

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

.

ЗАДАНИЯ ДЛЯ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

Решить задачу ЛП графически

(во всех заданиях )

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

1. Зыкина, А.В. Математическое программирование: учеб. пособие [Текст] / А.В. Зыкина – Омск: ОмГТУ, 2000. – 64с.

2. Карманов, В.Г. Математическое программирование: учеб. пособие [Текст] / В.Г. Карманов – М.: ФИЗМАТЛИТ, 2000. – 264 с.

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

4. Мину, М. Математическое программирование. Теория и алгоритмы [Текст] / М.Мину. – М.: Наука, 1990. – 488 с.

5. Штойер, Р. Многокритериальная оптимизация. Теория, вычисления и приложения [Текст] / Р. Штойер. – М.: Радио и связь, 1992.

6. Вентцель, Е.С. Исследование операций [Текст] / Е.С. Вентцель. – М.: Сов. радио, 1972.

7. Абрамов, Д.Ц. Математическое программирование [Текст] / Д.Ц. Абрамов, В.Ф. Капустин. – Л.: Изд-во. ЛГУ, 1981.

8. Кузнецов, Ю.Н. Математическое программирование [Текст] / Ю.Н. Кузнецов, В.И. Кузубов, А.В. Волощенко. – М. Высш. школа, 1980.

9. Пшеничный, Б.Н. Численные методы в экстремальных задачах [Текст] / Б.Н. Пшеничный, Ю.Н. Данилин. – М.: Наука, 1975.

10. Химмельблау, Д. Прикладное нелинейное программирование [Текст] / Д. Химмельблау. – М.: Наука, 1974.

11. Вагнер, Г. Основы исследований операций [Текст] / Г. Вагнер. – М.; Мир, 1972. – Т. 1-3.

О Г Л А В Л Е Н И Е

1. ПРИМЕРЫ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ............................................... 3

1.1. Пример построения канонической формы задачи ЛП....................... 3

1.2. Пример графического решения задачи ЛП......................................... 4

1.3. Пример решения задачи в специальной форме симплекс-методом... 6

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

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

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

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

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

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

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

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

стоимости..................................................................................................... 17

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

2. ЗАДАНИЯ ДЛЯ ПРАКТИЧЕСКИХ ЗАНЯТИЙ........................................ 19

2.1. Привести задачу ЛП к канонической форме..................................... 19

2.2. Решить задачу ЛП графически.......................................................... 22

2.3. Определить допустимое базисное решение методом искусственного базиса 25

2.4. Решить задачу ЛП симплекс-методом............................................... 27

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

2.6. Определить задачу, двойственную к исходной................................. 32

2.7. Используя теоремы двойственности, решить исходную и

двойственную задачи........................................................................... 36

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

2.9. Решить задачу ЦЛП методом Гомори............................................... 43

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

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

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

Компьютерная верстка В.С. Николайчук

ИД № 06039 от 12.10.2001 г.

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

Подписано в печать 23.03.2007 г. Формат 60´84 ¹/₁₆. Бумага офсетная.

Отпечатано на дупликаторе. Уч. изд.л. 3,25. Усл.-печ. л. 3,25.

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

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

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

Методы оптимизации

Сборник заданийдля практических занятий

Омск 2007

Составитель: А. В. Зыкина

Данные методи