ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Размещено на http://www.allbest.ru/

20

СТЕПАНОВ А.В.

ГЛАВА I. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

I.1 РАЗРАБОТКА МОДЕЛЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

линейный программирование табличный двойственный

Термин “разработка” дословно означает построение моделей ЛП практических задач. Это скорее искусство, которое постигается с опытом.

Отметим основные этапы этой задачи:

определение переменных задачи;

представление ее ограничений в виде линейных уравнений или неравенств;

задание линейной целевой функции, подлежащей минимизации или максимизации.

I.1.1 Пример разработки модели задачи технического контроля

Предположим, что в отделе технического контроля (ОТК) некоторой фирмы работают контролеры двух категорий. Норма выработки ОТК за 8-ми часовую смену - не менее 1800 изделий. Контролер I категории проверяет 25 изделий в час, и не допускает ошибок в 98% случаев. Контролер II категории, соответственно, проверяет 15 изделий в час, его точность составляет 95%.

Зарплата контролера I категории - 4$ в час, контролер II категории получает 3$ в час. Вместе с тем, при каждой ошибке контролера фирма несет убытки в размере 2$.

Фирма может использовать не более 8 контролеров I категории и 10 контролеров II категории.

ЗАДАЧА: подобрать оптимальный состав ОТК, при работе которого, фирма бы несла минимальные затраты.

Разработка модели: Пусть и количество контролеров I и II категории в отделе. Их число ограничено

В смену необходимо проверять не менее 1800 изделий. Следовательно необходимо выполнение неравенства

или, после упрощения

В расходах фирмы отмечаются два момента: зарплата контролера и его ошибки.

Расходы фирмы на контролера I категории: в час, на контролера II категории: в час.

Таким образом, функция

при ограничениях

I.1.2 Общая постановка задачи линейного программирования

Задача, в которой требуется обратить в максимум (минимум) целевую функцию

при условиях

(I. 1.1.)

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

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

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

Допустимый план, обращающий в максимум (минимум) целевую функцию, называется оптимальным планом задачи ЛП.

Теорема (ЛП): Пусть допустимое множество задачи ЛП является многогранником (в обобщенном смысле). Если целевая функция принимает максимальное (минимальное) значение в некоторой точке множества , то она (точка) является крайней точкой для . Если целевая функция принимает максимальное (минимальное) значение более, чем в одной точке, то она принимает это же значение и в любой их выпуклой комбинации: Здесь внутренняя точка отрезка ; граничная точка отрезка или крайняя точка ОДР; некоторый числовой параметр, “пробегающий” все значения из отрезка .

I.2 Методы решения задач линейного программирования

I.2.1 Графический метод решения задачи ЛП

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

Рассмотрим работу метода на примере двумерной задачи. Найдем решение удовлетворяющее системе неравенств

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

Построим на плоскости ОДР задачи. Границей ОДР будет объединение отрезков прямых, получаемых из системы ограничений путем замены знаков неравенств на равенства, рассмотренных в первом координатном углу (см. рисунок I.2.1). Внутренняя часть полученного многоугольника вместе с границей определяют ОДР. Крайние точки ОДР соответствуют допустимым базисным решениям задачи ЛП. Значение целевой функции можно определить в любой точке ОДР. Прямая линия, перпендикулярная вектору с координатами (3;2) будет геометрическим местом точек, в которых целевая функция принимает одинаковые фиксированные значения (в дальнейшем такие геометрические места точек будем называть линиями уровня).

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

Нетрудно проверить, что в точке (3; 2) Максимальное значение функция достигает в крайней точке ОДР (см. рисунок I.2.2).



Это и будет оптимальное решение задачи. Координаты точки легко найти. Это решение системы

Таким образом а

І.2.2 Табличный симплекс-метод

Универсальным вычислительным методом решения задачи ЛП является так называемый симплекс-метод. Идея метода состоит в последовательном “улучшении” планов задачи по определенному критерию до получения оптимального решения.

Как уже было отмечено, оптимальное значение линейная целевая функция может достигать в крайних (граничных) точках ОДР, а именно в угловых точках. Важно заметить, что, если размерность задачи (количество переменных и количество ограничений) велики, то угловых точек может быть очень много и указать нужную становится весьма затруднительным делом, а определять оптимальное решение простым перебором весьма долгое и рутинное занятие.

Этих недостатков и лишен симплекс-метод, согласно которому: находясь в одной из вершин многогранной области - из всех соседних Соседняя вершина ОДР - смежное допустимое решение. вершин выбирается та, которая “улучшает” целевую функцию.

Рассмотрим процесс подготовки исходных данных и алгоритм решения задачи этим методом. Для решения задачи ЛП

необходимо предварительно выполнить следующие процедуры:

привести математическую модель задачи к каноническому виду (систему активных ограничений типа неравенств привести к уравнениям путем введения дополнительных “искусственных” переменных);

определить начальное допустимое решение задачи;

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

весовые коэффициенты переменных целевой функции; переменные текущего базиса; значения базисных переменных (столбец ); элементы матрицы условий задачи (столбцы ); оценки “дефект” -

Оценки определяются по формулам:



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

заносятся в последнюю строку столбца

Алгоритм симплекс-метода.

Шаг I: Выбор начального базисного решения.

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

Шаг III: Продолжение поиска допустимых базисных решений. (Если полученное решение не является оптимальным, то симплекс-метод позволяет перейти к смежному допустимому базисному решению).

Шаг IV: Смежное допустимое базисное решение отличается только одной базисной переменной (независимая переменная становится базисной, а одна из базисных переменных становится независимой). Тем самым осуществляется переход на соседнюю вершину многогранника ОДР.

Критерий оптимальности. Обозначим относительную оценку небазисной переменной через

оценки базисных переменных.

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

Проиллюстрируем все выше сказанное примером.

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

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

Последовательные итерации удобно вести в компактном виде в таблице (см. таблицу I.).

Таблица I.

№ 1	3	2	0	0	0
0		-1	2	1	0	0	4
0		3	2	0	1	0	14
0		1	-1	0	0	1	3	3
	3	2	0	0	0

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

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

Далее элементарные гауссовы преобразования строк приведут исследователя к новому базису и новой таблице (таблица II).

Таблица II.

№ 2	3	2	0	0	0
0		0	1	1	0	1	7	7
0		0	5	0	1	-3	5	1
3		1	-1	0	0	1	3
	0	5	0	0	-3

Сформулируем последовательность операций перехода к таблице II.

Прибавить разрешающую строку к первой строке таблицы I. Результат записать в первую строку таблицы II.

Умножить разрешающую строку на -3 и прибавить ко второй строке таблицы I. Результат записать во вторую строку таблицы II.

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

Строка так же вычисляется с помощью элементарных преобразований. По-прежнему, и это чрезвычайно важно, - рабочей строкой является разрешающая строка. Умножить третью строку таблицы I на -3 и прибавить к строке . Результат записать в строку таблицы II.

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

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

Далее процесс продолжается до тех пор пока не будет выполнен критерий оптимальности (см. таблицу III).

Таблица III.

№ 3	3	2	0	0	0
0		0	0	1			6
2		0	1	0			1
3		1	0	0			4
	0	0	0	-1	0

Таким образом,

Изобразим графически полученную ситуацию (см. рисунок I. 2.5).

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

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

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

Таблица данных I.

№ Варианта
I	7	6	5	8	3	1	476	364	319	11	10
II	10	9	3	18	15	1	123	111	523	11	13
III	8	7	7	12	9	5	459	379	459	9	9
IV	8	7	7	10	5	2	612	492	562	11	9
V	10	9	5	6	3	1	735	765	455	8	4
VI	5	6	7	7	6	1	256	283	363	9	7
VII	3	9	10	5	3	2	414	723	788	12	16
VIII	7	7	8	5	2	1	347	300	357	11	7
IX	7	7	8	13	8	2	363	327	429	6	4
X	5	9	10	7	9	8	343	587	587	11	7

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

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

Таблица данных II.

№ Варианта
I	20	15	14	28	9	1	758	526	541	10	2
II	15	15	9	33	25	3	571	577	445	8	10
III	11	13	13	21	15	3	741	741	822	5	3
IV	14	12	8	8	4	2	624	541	376	7	3
V	19	16	19	26	17	8	868	638	853	5	4
VI	14	15	20	40	6	4	1200	993	1097	5	13
VII	9	15	15	27	15	3	606	614	575	5	7
VIII	13	13	11	11	23	1	608	802	840	11	6
IX	8	10	14	7	8	1	417	580	591	5	5
X	19	16	19	31	9	1	1121	706	1066	16	19

I.3 ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ

I.3.1 Двойственная задача линейного программирования

Каждой задаче линейного программирования



со смешанными ограничениями вида

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

при ограничениях

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

если прямая задача является задачей максимизации, то двойственная - минимизации и наоборот;

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

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

матрица ограничений двойственной задачи получается транспонированием матрицы ограничений прямой задачи;

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

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

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

		...
		...
		...

Отсюда имеем оптимальный план двойственной задачи.

Если прямая задача решается на максимум:

Если прямая задача решается на минимум:

Рассмотрим пример.

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

Таблица I.

№ 1	8	6	0	0
0		2	5	1	0	11
0		4	1	0	1	10
	8	6	0	0

Здесь в условиях наших обозначений: (количество истинных переменных) и (количество дополнительных переменных = количеству ограничений задачи):

Заметим так же, что задача решается на максимум.

Таблица II.

№ 2	8	6	0	0
0		0		1		6
8		1		0			10
	0	4	0	-2

Таблица III.

№ 3	8	6	0	0
6		0	1				-
8		1	0				-
	0	0

Оптимальный план двойственной задачи, судя по вектору , будет иметь вид

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

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

система ограничений:

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

Введем следующие обозначения:

и в качестве сопряженного базиса возьмем, например, векторы Тогда из системы (см. систему ограничений двойственной задачи):

найдем значение опорного плана двойственной задачи:

Становится очевидным, что данный базис не может быть взят в качестве сопряженного, так как при и второе ограничение системы не выполняется. Тогда, попробуем в качестве сопряженного базиса выбрать векторы Из системы:

находим значения Неравенство

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

Далее, определим коэффициенты разложения небазисных векторов по векторам базиса и найдем псевдоплан исходной задачи:

Очевидно, что базисные векторы будут иметь вид



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

Заполняем первую таблицу (см. таблица I) и приступаем к итерациям.

Таблица I.

№ 1	8	6	0	0
6		4	1	0	1	10
0		-18	0	1	-5	-39
	8	6	0	0
		-	0	0

Результат итераций будем записывать в таблицу II.

Таблица II.

№ 2	8	6	0	0
6		0	1
8		1	0
	0	6
	-	-	-	-

В столбце свободных членов (он выделен в таблице II) нет отрицательных элементов, следовательно, полученный план: - оптимален.

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

Размещено на Allbest.ru

...