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

Лекция № 5

1. Геометрическая интерпретация задачи и графический метод решения двухмерных задач линейного программирования

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

Если провести прямые, соответствующие условиям [(1)-(3)] задачи, получим область допустимых решений (ОДР).

Неравенства и целевую функцию задачи с двумя переменными можно изобразить в виде прямых линий в декартовой системе координат с осями x1, x2. Для этого заменим неравенства (1-3) уравнениями. Определим для каждого уравнения координаты двух точек, через которые проходит прямая. Для первого уравнения найдем две точки, через которые проведем прямую: .

Для второго уравнения определим координаты двух точек, через которые проведем прямую:

3. Для третьего уравнения определим координаты двух точек ; . через которые проведем прямую.

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

Получим область допустимых значений основных переменных (многоугольник), определяемую ограничениями 1, 2, 3 и условиями не отрицательности переменных.

 

Такой многоугольник называется симплексом. Все точки, расположенные внутри или на границе симплекса являются допустимыми, т. е. удовлетворяют системе ограничений 1-3.

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

при Z=10 при

.

при Z=60

 

n/t/

т. е. линия уровня совпадает с гранью симплекса (2).

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

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

Последний случай мог бы реализоваться, если бы, например, отношение коэффициентов целевой функции C1 и C2 при неизвестных X1 и X2 в уравнении целевой функции было таким же, как и у коэффициентов при неизвестных во втором ограничении.

, если С1=4, С2=2, тогда линия уравнения при максимальном значении целевой функции совпадала бы с гранью АВ симплекса, т. е. каждая точка отрезка АВ соответствовала бы оптимальному решению.

В общем случае оптимальному решению соответствует по крайней мере одна из вершин симплекса.

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

2. Приведение задач линейного программирования к каноническому представлению.

Алгоритм – точное описание последовательности действий при решении задачи. Для определения первого (опорного) решения необходимо перейти к каноническому представлению задачи, в котором все ограничения имеют форму уравнений (т. е. относятся к типу “=”).

Пример.

Исходные данные к задаче

Показатели	Ед.
	изм.	Зерновые	Кормовые.	Молочн. коровы	Привес свиней	Ресурсы хозяйства
Прод.
га	га	гол.	ц
х1	х2	х3	х4
1.Пл. пашни	га	1	1	-	-	1000*
5.Затраты труда	чел. дн.	5	5	50	100	40000*
6.Ден.-мат. затраты	Тыс. руб.	3	16	24	10	120000*
7.Урожайность	Ц. к. е/га	30	50	-	-	-
8.Продуктив- ность	ц/гол			2,0	50
9.Нормы кормл.:	ц к. е			50	10	-
Чистый доход	тыс. руб.	100		650	320

В соответствии с исходными данными сформулируем группу основных переменных:

x1 - площадь посева зерновых культур

x2 - площадь посева кормовых культур

x3 - поголовье коров

x4 - привес свиней

На все переменные накладывается условие неотрицательности.

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

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

1.  По площади пашни

2.  По трудовым ресурсам

3.  По денежным ресурсам

4.  По балансу кормов (20% зерна)

Целевая функция – максимум чистого дохода:

.

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

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

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

Помимо избыточных и остаточных переменных в левой части ограничений типа “” и “=” вводят со знаком “+” еще дополнительные неотрицательные переменные, называемыми искусственными. В правильном решении они должны быть равны «о», поэтому они вводятся таким образом в целевую функцию, чтоб алгоритм решения приводил автоматически к «обнулению» искусственных переменных.

В задачах на max искусственные переменные вводятся с большим коэффициентов со знаком «-», при решении на min – со знаком «+»; например:

 

.

В результате придем к канонической системе ограничений:

Дополнительные остаточные переменные:

x5 недоиспользованная площадь пашни

x6 недоиспользованные трудовые ресурсы

x7 недоиспользованные денежные ресурсы

x8 недоиспользованные корма

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

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

Первая симплекс-таблица (опорное решение).

№ огр.	Баз. пер.	Оценка цел. функции	Значение баз. пер. Аiо										Контроль	Частное от деления
Коэффициенты замещения
Основные перемен.	Дополнит. перемен.
1	Х5	0	1000	1	1	0	0	1	0			1003		-
2	Х6	0	40000	5	5	50	100	0	1			40161		800
3	Х7	0	120000	3	16	24	10	0		1		120054		5000
4	Х8	0	3000	-6	-50	50	10	0			1	3005		60min
zj – cj	0	100	0	650	320	0				-1070		-

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

Опорное решение предполагает, что остаточные переменные приравниваются ресурсам, а основные переменные равны нулю.

; - коэффициенты при неизвестных в уравнении для целевой функции;

- оценка целевой функции

- коэффициенты ограничений

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

Значение целевой функции при этом равно 0. .

Оценка решения на оптимальность.

Решение оптимально, когда все элементы индексной строки положительны в задачах на максимум; (отрицательны в задачах на минимум).

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

Увеличивая соответствующую небазисную переменную X3, вводя ее в базис, мы увеличиваем значение Z. Для определения выводимой из базиса переменной поочередно разделим значения элементов столбца свободных членов Aio на соответствующие положительные элементы ключевого столбца Aio/Aiкл.. Строка, в которой частное от деления оказалось минимальным, называют ключевой (главной) строкой.

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

Расчет всех элементов новой симплекс-таблицы.

Пересчет элементов начальной строки (ключевой):

А`кл. j=Aклj/Aкл. Все элементы ключевой строки делят на ключевой элемент.

1*60 = 1000,*(-1)=16+24=40, 0-(-650)*(-1)=-650,

*60=40000 – 3000=37000,

-*(-0,12)=-178

Таблица 22

Вторая симплекс-таблица

№ огр..	Баз. переменные	Оценка цел. функции	Значение баз. пер. Аiо	Коэффициенты замещения		Контроль	Частное от деления
Основные перемен.	Дополнит. перемен.
Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост)	Х8 (ост)
1	Х5(ост.)	0	1000	1	1	0	0	1	0	0	0	1003		1000
2	Х6(ост.)	0	37000	11	55	0	90	0	1	0	-1	37156		673
3	Х7(ост.)	0	118600	5,9	40	0	5,2	0	0	1	-0,5	118651		2960
4	Х3(осн.)	0	60	-0,12	-1	1	0,2	0	0	0	0,02	60,1		-
zj – cj	39000	-178	-650	0	-190	0	0	0	13	37995		-

Таблица 23

Третья симплекс-таблица

№ огр..	Баз. переменные	Оценка цел. функции	Значение баз. пер. Аiо	Коэффициенты замещения		Контроль	Частное от деления
Основные перемен.	Дополнит. перемен.
Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост	Х8 (ост)
1	Х5(ост.)	0	327,3	0,8	0	0	-1,64	1	-0,018	0	0,018	327,46		409
2	Х2(осн.)	0	672,7	0,2	1	0	1,64	0	0,018	0	-0,018	675,54		3360
3	Х7(ост.)	0	118600	-2,12	0	0	-60,3	0	-0,73	1	0,25	118538		-
4	Х3(осн.)	0	732,7	0,08	0	1	1,84	0	0,018	0	0,018	735,656		9160
zj – cj	476272	-48	0	0	874	0	1,18	0	1,18	477101

Таблица 24

Результаты решения симплексной задачи

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

№ огр..	Баз. переменные	Оценка цел. функции	Значен. базис. пер. Аiо	Коэффициенты замещения		Контроль
Основные перемен.	Дополнит. перемен.
Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост)	Х8 (ост)
1	Х1(осн)	0	409,1	1	0	0	-2,05	1,25	-0,023		0,023	409,3
2	Х2(осн.)	0	590,9	0	1	0	2,05	-0,25	0,023		-0,023	593,7
3	Х7(ост.)	0	92520	0	0	0	-64,6	2,65	-0,775		0,295	92457,57
4	Х3(осн.)	0	700	0	0	1	2	-0,1	0,02		0	702,92
zj – cj	495909	0	0	0	775	60	10,7		2,27	496757

Все без исключения коэффициенты новой таблицы рассчитываются на основе предыдущей через ключевой элемент. Любой элемент следующей таблицы равен соответствующему элементу предыдущей таблицы минус произведение соответствующего элемента ключевого (i) столбца на соответствующий (j) элемент начальной строки.

Контроль.

Находят сумму коэффициентов по строке, включая столбец свободных членов и записывают в столбец «контроль». А столбец «сумма» рассчитывается по общему правилу. Значения в этих столбцах должны быть равны между собой в пределах 5-ти значащих цифр.