Симплексный метод (стр. 1 из 3)

Задача 1.

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

Вариант 3.

Найти наибольшее значение функции f(X) = - x₁ - x₂ + 2x₃ при ограничениях

2x₁ + x₂ + x₃ £ 2

x₁ - x₂ + x₃ £ 1,

x_j³ 0, j = 1, 2, 3.

Решение.

Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x_4,5³ 0.

f(X) = - x₁ - x₂ + 2x₃® max

2x₁ + x₂ + x₃ + x₄ = 2

x₁ - x₂ + x₃ + x₅ = 1,

x_j³ 0, j = 1, 2, 3, 4, 5.

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

Очевидное начальное опорное решение (0; 0; 0; 2; 1).

Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах

Номер симплекс-таблицы	Базис	CjCi	B	-1	-1	2	0	0	Q
				A1	A2	A3	A4	A5
0	A4	0	2	2	1	1	1	0	2:1 = 1
	A5	0	1	1	-1	1	0	1	1:1 = 1
	j	-	0	1	1	-2	0	0
1	A4	0	1	1	2	0	1	-1	1:2 = 1/2
	A3	2	1	1	-1	1	0	1
	j	-	2	3	-1	0	0	2
2	A2	-1	1/2	1/2	1	0	1/2	-1/2
	A3	2	3/2	3/2	0	1	1/2	1/2
	j	-	5/2	7/2	0	0	1/2	3/2

Начальное опорное решение (0; 0; 0; 1; 1), соответствующее симплекс-таблице 0, неоптимальное, так как в D - строке есть отрицательные значения, наименьшее в столбце А₃. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А₅, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А₅ выводим из базиса, а А₃ - вводим в базис. После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 1; 1; 0) не оптимально, так как в D - строке есть отрицательные значения, в столбце А₂.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А₄. В качестве направляющей строки возьмем А₄. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А₄ выводим из базиса, а А₂ - вводим в базис. Опорное решение, соответствующее симплекс-таблице 2 (0; 1/2; 3/2; 0; 0) - оптимально, так как в D - строке нет отрицательных значений.

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

х₁ = 0, х₂ = 1/2 = 0,5; х₃ = 3/2 = 1,5; f_max = -1×0 - 1×0,5 + 2×1,5 = 2,5.

Задача 2.

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

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

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

Вариант 3.

Из 505 м² ткани нужно сшить не более 150 женских и не более 100 детских платьев. На пошив одного женского и детского платья требуется соответственно 3 м² и 1 м² ткани. При реализации каждого женского платья получают 10 ден. единиц прибыли, а детского – 5 ден. единиц. Сколько нужно сшить женских и детских платьев, чтобы получить наибольшую прибыль?

Решение.

Задание 1.

Обозначим x₁ и x₂ количество женских и детских платьев, соответственно (план пошива). Очевидно, x_1,2³ 0 и целые. Так как женских платьев должно быть не более 150, то x₁£ 150, аналогично, для детских платьев получаем x₂£ 100. Расход ткани на план пошива (x₁, x₂) составит 3x₁ + x₂ м², эта величина не должна превышать запаса ткани 505 м². Следовательно, должно выполняться неравенство 3x₁ + x₂£ 505.

Прибыль от продажи платьев составит f(X) = 10x₁ + 5x₂ ден. единиц, и она должна быть наибольшей

Получаем экономико-математическую модель задачи:

Найти максимум функции f(X) при заданных ограничениях

f(X) = 10x₁ + 5x₂® max

3x₁ + x₂£ 505

x₁£ 150

x₂£ 100

x_1,2³ 0, целые.

Задание 2.

Решаем задачу без условия целочисленности решения. Построим множество допустимых решений задачи.

Прямые ограничения x_1,2³ 0 выделяют первую четверть плоскости.

Проведем прямую 3x₁ + x₂ = 505 через точки (110; 175) и (175; -5). Подставим в первое неравенство координаты точки (0; 0): 3×0 +1×0 = 0 < 505, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую x1 = 150 и выберем левую полуплоскость.

Проведем прямую x2 = 100 и выберем нижнюю полуплоскость.

Множество допустимых решений – это многоугольник ABCDO.

Построим линию уровня целевой функции f(X) = 10x₁ + 5x₂ 10x₁ + 5x₂ = 0 через точки (0; 0 ) и (-10; 20). Вектор-градиент {10; 5} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение.

Из чертежа видно, что наибольшее значение целевой функции будет на линии уровня, проходящей через точку В.

Координаты этой точки найдем из системы

3x₁ + x₂ = 505,

x₂ = 100.

x₁ = 135,

x₂ = 100.

f_mах = 10 ×135 + 5 ×100 = 1850 ден. единиц.

Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане пошива следует сшить женских платьев 135 шт., детских – 100 шт. При этом прибыль составит 1850 ден. единиц и будет наибольшей.

Задание 3.

Двойственная задача.

Найти минимум функции g(Y) при ограничениях:

g(Y) = 505y₁ + 150y₂ + 100y₃® min

3y₁ + y₂³ 10

y₁ + y₃³ 5

y_1,2,3³ 0.

Оптимальное решение прямой задачи Х = (135; 100). Подставим его в ограничения этой задачи

3×135 + 1×100 = 505

135 < 150

100 = 100.

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

Так как для оптимального решения прямой задачи второе ограничение выполняется как неравенство, то в оптимальном решении двойственной задачи y₂ = 0.

Так как для оптимального решения прямой задачи х₁ > 0и х₂ > 0, то оба ограничения двойственной задачи выполняются как равенство. Для нахождения решения двойственной задачи получаем систему

y₂ = 0

3y₁ + y₂ = 10

y₁ + y₃ = 5.

Получаем решение: y₁ = 10/3, y₂ = 0, y₃ = 5/3.

Найдем значение целевой функции двойственной задачи:

g(Y) = 505×10/3 + 150×0 + 100×5/3 = 5550/3 = 1850.

Получили g_min = f_max = 1850 ден. единиц.

Так как значения прямой и двойственной функций равны, то Y = (10/3; 0; 5/3) является оптимальным решением двойственной задачи (по первой теореме двойственности).

Задача 3.

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

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

Задание 3. Найти оптимальный план перевозок, отметив при этом единственность или неединственность оптимального плана.

Вариант 3.

Картофель из четырех районов должен быть перевезен в три хранилища. Запасы картофеля в районах соответственно равны 400 т, 500 т, 800 т и 500 т. Возможности хранилищ соответственно равны 700 т, 800 т и 700 т. Затраты на перевозку одной тонны картофеля из первого района в каждое из хранилищ равны соответственно 1, 4 и 3 ден. единиц; аналогичные затраты на перевозку из второго района составляют 7, 1 и 5 ден. единиц, из третьего - 4, 8 и 3 ден. единиц, из четвертого - 6, 2 и 8 ден. единиц. Найти план перевозок картофеля из районов в хранилища, при котором транспортные расходы были бы минимальными.

Решение.

Задание 1.

Мощностипоставщиков	Мощности потребителей
	700	800	700
400	1	4	3
500	7	1	5
800	4	8	3
500	6	2	8

Сумма мощностей поставщиков (запасы картофеля в всех районах) 400+500+800+500 = 2200, сумма мощностей потребителей (возможности всех хранилищ) 700+800+700 = 2200. Суммы равны, данная задача является транспортной задачей закрытого типа.

Задание 2.

Обозначим x_ij объем поставок картофеля от i – го поставщика (района) j – му потребителю (хранилищу), i = 1, 2, 3, 4; j = 1, 2, 3. Очевидно, x_ij³ 0. В закрытой транспортной задаче все ограничения являются равенствами.

Так как потребности должны быть удовлетворены, то выполняются условия:

х₁₁ + х₂₁ + х₃₁ + х₄₁ = 700

х₁₂ + х₂₂ + х₃₂ + х₄₂ = 800 (1)

х₁₃ + х₂₃ + х₃₃ + х₄₃ = 700

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

х₁₁ + х₁₂ + х₁₃ = 400

х₂₁ + х₂₂ + х₂₃ = 500 (2)

х₃₁ + х₃₂ + х₃₃ = 800