Графический метод решения задач линейного программирования

Наиболее простым и наглядным методом решения задачи линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.

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

Положим n=2, т.е. рассмотрим эту задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a_i1 x₁ + a_i2 x₂ = b_i, i=1, 2, …m. Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x1=0, x2 =0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости. Определим, какую часть плоскости описывает неравенство 2х₁+3х₂£ 12. Во-первых, построим прямую 2х₁+3х₂=12. Эта прямая проходит через точки (6, 0) и (0, 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет

неравенству. Удобной для использования при подстановке в неравенство является начало координат. Подставим х₁=х₂=0 в неравенство 2х₁+3х₂£ 12. Получим 2´ 0+3´ 0£ 12. Данное утверждение является верным, следовательно, неравенству 2х₁+3х₂£ 12 соответствует нижняя полуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на рис.1.

Рис. 1. Неравенству 2х₁+3х₂£ 12 соответствует нижняя полуплоскость.

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

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (x_j ³ 0, j=1, …, n). Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

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

.

Этот вектор показывает направление наискорейшего изменения це­левой функции. Прямая , перпендикулярная вектору–градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине “a”. Меняя значение “a”, получим семейство параллельных прямых, каждая из которых является линией уровня.

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

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

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

1. Строится многоугольная область допустимых решений ЗЛП – ОДР,

2. Строится вектор-градиент ЦФ в какой-нибудь точке Х₀ принадлежащей ОДР –

.

3. Линия уровня C₁x₁+C₂x₂ = а (а –постоянная величина) - прямая, перпендикулярная вектору –градиенту – передвигается в направлении этого вектора в случае максимизации f(x_1, x₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x_1, x₂).

4. Для нахождения ее координат достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x_1, x₂), найденное в получаемой точке, является максимальным.

При минимизации f(x_1, x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x_1, x₂) не существует.

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

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

Задача. о планировании выпуска продукции пошивоч­ному предприятию.

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3, 5 м шерсти, 0, 5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Модель задачи.

Введем следующие обозначения: х₁ - число женских костюмов; x₂ - число мужских костюмов.

Прибыль от реализации женских костюмов составляет 10х₁, а от реализации мужских 20х₂, т.е. необходимо максимизировать целевую функцию

f(x) = 10´ х₁ + 20´ х₂ -> max.

Ограничения задачи имеют вид:

х₁ + х₂ £ 150

2 х₁ + 0.5 х₂ £ 240

х₁ + 3.5 х₂ £ 350

х₂³ 60

х₁ ³ 0

Первое ограничение по труду х₁ + х₂ £ 150. Прямая х₁ + х₂ = 150 проходит через точки (150, 0) и (0, 150).

Рис. 2. Решением первого неравенства является нижняя полуплоскость.

Второе ограничение по лавсану 2 х₁ + 0.5 х₂ £ 240. Прямая 2 х₁ + 0.5 х₂ = 240 проходит через точки (120, 0) и (0, 480). Третье ограничение по шерсти х₁ + 3.5 х₂ £ 350. Добавим четвертое ограничение по количеству мужских костюмов х2 ³ 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х2 = 60. На рис.3. заштрихована область допустимых решений.

Рис. 3. Заштрихована область допустимых решений.

Для определения направления движения к оп­тимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. = (10; 20).

Что бы построить этот вектор, нужно соединить точку (10; 20) с началом координат. При макси­мизации целевой функции необходимо двигаться в направ­лении вектора-градиента, а при минимизации — в противо­положном направлении. Для удобства можно строить век­тор, пропорциональный вектору Ñ. Так, на рис. 2.1.6. изобра­жен вектор градиент (30; 60).

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

х₁ + 3.5 х₂ = 350

х₁ + х₂ = 150.

Отсюда лег­ко записать решение исходной ЗЛП: max f(x) = 2300 и дости­гается при x₁=70 и x₂=80 (рис. 4.)

Рис.4. Максимум целевой функции достигается в точке (70, 80).

Задача. Для изготовления двух видов продукции А₁ и А₂ используют три вида ресурсов S₁, S₂, S₃, запасы которых составляют 18, 16 и 5 усл.ед. Расход ресурсов на 1 ед. продукции приведен в таблице:

Необходимо составить такой план производства продукции, который обеспечит наибольшую прибыль от ее реализации.

Составим экономико-математическую модель (ЭММ) задачи.

Пусть надо выпустить изделий A₁ - x₁ шт., а изделий А₂ - x₂ шт. Тогда прибыль F = 2x₁ + 3x₂ Þ max

x1 + 3x2 £	18
2x1 + x2 £	16
x2 £	5
x1 ³ 0,	x2 ³ 0

Решим задачу графически.

1)	x1 + 3x2 £ 18
	x1 + 3x2 = 18 (0; 6) (18; 0)
	к.т. (0; 0), 0 + 3*0 < 18 (в) – входит
2)	2x1 + x2 £ 16
	2x1 + x2 = 16 (0; 16) (8; 0)
	к.т. (0; 0), 2*0 + 0 < 16 (в) – входит
3)	x2 £ 5
	x2 = 5, x2 < 5 - ниже прямой
4)	x1 ³ 0 - правее ОX2
5)	x2 ³ 0 - выше ОX1
Линия уровня	F = 2x1 + 3 x2 F = 0
	2x1 + 3x2 = 0 (0; 0) (3; -2)
	q = {2; 3} - указывает направление возрастания F.

max F достигается в т. С

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

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

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):

В теории линейного программирования (ЛП) показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2, …, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний С_nm.

Задача. Получить решение по модели задачи об оптимальном использовании ограниченных ресурсов (решить ЗЛП):

Приведем задачу к каноническому виду путем введения дополнительных переменных x ₃ и x₄:

Найдем все опорные планы КЗЛП. Используя метод Жордана-Гаусса выписываем все базисные решения системы уравнений:

Последовательно будем иметь:

Х₁ = (0, 0, 300, 150); Х₂= (150, 0, 150, 0); Х₃= (0, 150, -150, 0); Х₄= (75, 75, 0, 0); Х₅= (300, 0, 0, -150); Х₆= (0, 100, 0, 50).

Среди этих базисных решений четыре опорных:

Х₁ = (0, 0, 300, 150); Х₂= (150, 0, 150, 0); Х₄= (75, 75, 0, 0); Х₆= (0, 100, 0, 50).

Указанным опорным планам на рис.5 отвечают соответственно следующие угловые точки и значения ЦФ в них:

А(0, 0) и f(0, 0)=0; Д(150, 0) и f(150, 0)=300; С(75, 75) и f(75, 75)=375; В(0, 100) и f(0, 100)=300.

Согласно теории ЛП оптимальное решение содержится среди опорных планов.

Таким образом, максимальное значение, равное 375, целевая функция f (x1, x2) достигает на опорном плане Х4= (75, 75, 0, 0), т.е. оптимальное решение рассматриваемой ЗЛП: x1 = 75, x2 = 75.

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

Симплекс-метод с естественным базисом

Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).

Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден – (b1, b2, …, bm, 0, …, 0).

Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и так далее. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ.

Математический признак оптимальности состоит из следующих двух теорем:

1. Если для всех векторов А₁, А₂, …, А_n выполняется условие

где ,

то полученный опорный план является оптимальным.

2. Если для некоторого вектора, не входящего в базис, выполняется условие , то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:

- если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);

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

На основании признака оптимальности в базис вводится вектор А_к , давший минимальную отрицательную величину симплекс разности:

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А_r, который дает минимальное положительное оценочное отношение

Строка А_r называется направляющей, столбец А_к и элемент a_{r к} – направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

а элементы i-й строки – по формулам:

Значения нового опорного плана рассчитываются по формулам:

для i = r;

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

Примечание. Для использования приведенной процедуры к минимизации линейной функции f (x₁, x₂, …, x_n) следует искать максимум - f (x₁, x₂, …, x_n), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.

Пример. Получить решение по модели:

Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x 3 и x4:

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0, 0, 300, 150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

Номер			В
симплекс-	Базис		план					Q
таблицы
	А3
	А4
		f(x)		-2	-3
	А2			1/3		1/3
I	А4			2/3		-1/3
		f(x)		-1
	А2					1/2	-1/2
II	А1					-1/2	3/2
		f(x)				1/2	3/2

В симплекс-таблице II получен оптимальный опорный план, поскольку все симплекс-разности (оценки) j. Оптимальные значения переменных равны: x1*=75, x2* =75 (основные переменные), x3* =0, x4* =0 (дополнительные переменные). Максимальное значение целевой функции равно 375.

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

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

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

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

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оцен­ками, или «ценами» ресурсов, или теневыми ценами.

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

Двойственная задача по отношению к исходной состав­ляется согласно следующим правилам:

1) целевая функция исходной задачи формули­руется на максимум, а целевая функция двойственной задачи— на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум — вид ³;

2) матрица А, составленная из коэффициентов при неизвестных в сис­теме ограничений исходной задачи и аналогич­ная матрица А^т в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;

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

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записан­ному в виде неравенства £, соответствует переменная, связанная условием неотрицательности. Если функцио­нальное ограничение исходной задачи является равенст­вом, то соответствующая переменная двойственнвой; задачи может принимать как положительные, так и отрицательные значения

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:

Модель двойственной задачи имеет вид:

Две приведенные задачи образуют пару симметричных двойственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности.

Для взаимно двойственных задач имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные реше­ния, при этом значения целевых функций на оптимальных решениях совпадают: f(x) = g(y).

2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограниченна сверху. При этом у двойственной задачи будет пустое допустимое множество.

3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4.Обе из рассматриваемых задач имеют пустые допустимые множества.

Экономический смысл первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при из­вестных заранее ценах продукции равна затра­там на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y_i. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:

f(X) < g(Y}, т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Зна­чит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.

Из первой теоремы двойственности следует, что при оп­тимальной производственной программе и векторе оценок ресурсов производственные потери равны нулю.

Вторая теорема двойственности

(теорема о дополняющей нежесткости)

Пусть X=(x₁, x₂,...x_n) - допустимое решение прямой задачи, а Y= (y₁, y₂,...y_m) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

*

**

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

Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X₁, X₂,..., X_n) и оптимальный вектор оценок Y=(Y₁, Y₂,..., Y_m):

(4)

(5)

Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет вы­пускаться.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках.

Значения переменных Y_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.

Пример. Сформулируем экономико-математическую модель двойственной задачи к задаче о коврах.

Прямая задача:

f(x) = 3Х₁ +4Х₂ +3Х₃ +1Х₄

Ограничения по ресурсам

7Х₁ +2Х₂ +2Х₃ +6Х₄ 80

5Х₁ +8Х₂ +4Х₃ +3Х₄ 480

2Х₁ +4Х₂ +Х₃ +8Х₄ 130

Х₁, Х₂, Х₃, Х₄ 0

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

Y₁ – двойственная оценка ресурса труд, или «цена» труда;

Y₂ – двойственная оценка ресурса сырье, или «цена» сырья;

Y₃ – двойственная оценка ресурса оборудование, или «цена» оборудования.

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

g = 80 ´ Y₁ + 480´ Y₂ + 130´ Y₃ ® min

Необходимо найти такие “цены” на ресурсы (Y_i), чтобы общая стоимость используемых ресурсов была минимальной.

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

7 ´ Y₁ + 5´ Y₂ + 2´ Y₃ ³ 3

2 ´ Y₁ + 8´ Y₂ + 4´ Y₃ ³ 4

2 ´ Y₁ + 4´ Y₂ + 1´ Y₃ ³ 3

6 ´ Y₁ + 3´ Y₂ + 8´ Y₃ ³ 1

Y₁ , Y₂ , Y₃ ³ 0

Задача о размещении производственных заказов

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

Необходимо найти такой вариант распределения объемов производства продукции и ка­питальных вложений по филиалам, при котором суммарная стоимость изделий будет минимальной.

Таблица

В результате решения получен план распределения объемов производства по филиалам предприятия

Требуется:

1) Сформулировать экономико-математическую модель прямой и двойственной задачи.

2) Найти оптимальный план двойственной задачи, используя теоремы двойственности.