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

Лабораторная работа №2.

Цель работы: построение математической модели и решение оптимизационной задачи линейного программирования.

 

Требуется:

1. В соответствии с исходными данными записать математическую модель.

2. В соответствии с ограничениями построить область допустимых решений в пространстве параметров X_e, Х_i.

3. В ОДР построить линии равных уровней целевой функции D и определить максимальное значение D, принадлежащее этой области.

4. Определить оптимальные значения суточных объемов производства X_e^* и Х_i^* изделий Е и I обеспечивающие максимум целевой функции.

5. Рассчитать значения целевой функции D в узлах ОДР и сравнить полученные значения целевой функции D и координат оптимального решения X_e^* и Х_i^* с решениями, полученными графически.

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

 

Исходные данные

Номер варианта	a11	a12	a21	a22	b1	b2	b3	b4	Ce	Ci
	1,2			1,2	5,9	7,9	0,8	2,1

 

Постановка задачи.

Нередко на практике возникают задачи оптимизации какого-либо процесса по выбранному критерию. В данной работе рассматривается задача построения математической модели и её оптимизация графическим методом линейного программирования.

Рис.1

Небольшое предприятие (рис.1) выпускает два вида изделий Е и I. Продукция обоих видов поступает в продажу. Для производства требуется два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов на складе предприятия составляют b₁и b₂ соответственно.

Расходы продуктов А и В на единицу соответствующего изделия приведены в табл.1.

Т а б л и ц а 1

 

 

Исходный продукт	Расход исходного продукта на единицу изделия	Максимально возможный запас
Е	I
А	а11	а12	b1
В	а21	а22	b2

Цена одной единицы изделия Е равна С_e и С_i для I.

Изучение рынка сбыта показало, что суточный спрос на изделие I никогда не превышает спроса на изделие Е более чем на b₃. Кроме того установлено, что спрос на изделие I никогда не превышает b₄.

Каков должен быть объем производства каждого вида изделия в сутки, чтобы доход от реализации был максимальным?

 

Метод решения

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

В соответствии с заданными ограничениями в пространстве переменных X_e и Х_i необходимо построить область допустимых решений(ОДР) поставленной задачи. Допустимая область переменных представляет некоторый выпуклый многоугольник.

Для нахождения оптимального решения, необходимо выяснить в каком направлении возрастает целевая функция D = C_eX_e + С_i Х_i. С этой целью, в ОДР наносят ряд параллельных линий равного уровня значений целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях D. Это позволяет определить наклон целевой функции и направление, в котором происходит её увеличение. Чтобы найти оптимальное решение, следует перемещать прямую равного дохода, в направлении возрастания целевой функции до тех пор, пока она не сместится в область недопустимых значений переменных. Точка перехода из ОДР в область недопустимых значений соответствует оптимальному решению.

 

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

1. Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.

2. Множество всех планов ЗЛП выпукло.

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

4. Каждый угловой точке многоугольника решений отвечает опорный план ЗЛП.

РЕШЕНИЕ

Переменные:

Х_е - суточный объем производства изделия Е.

X_i – суточный объем производства изделия I.

Целевая функция:

D=D_e+D_i=C_eX_e+C_iX_i – доход от производства и сбыта изделия E и I.

D= 4X_e+3X_i

D=>max.

 

Ограничения:

1.2X_e + 2X_i ≤ 5.9 ограничения по запасам

2X_e + 1.2X_i ≤7.9

X_i – X_e ≤ 0.8 ограничения по спросу

X_i ≤ 2.1

X_e ≥0

X_i≥0

 

Требуется максимизировать значение целевой функции D (т.е. доход).

 

В соответствии с ограничениями построим ОДР (ABCEFG) в пространстве параметров X_e и X_i.

1-ое ограничение:

1.2X_e + 2X_i =5.9

Х_е=0; X_i=2.95

Х_е=4.9; X_i=0

 

2-ое ограничение:

2X_e + 1.2X_i =7.9

Х_е=0; X_i=6.6

Х_е=3,95;X_i=0

 

3-е ограничение:

X_i – X_e ≤ 0.8

Х_е=0; X_i=0.8

Х_е=-0.8;X_i=0

 

4-е ограничение:

X_i = 2.1

 

 

Рис.2

 

 

В ОДР строим линии равных уровней целевой функции D. Получаем точку F – точка перехода из ОДР в область недопустимых значений, соответствующая оптимальному решению. При этом X_e^* = 3.4, X_i^* = 0.9, D=16,3.

 

Рассчитаем значения целевой функции D в узлах ОДР и сравним полученные значения целевой функции D и координат оптимального решения X_e^*, X_i^* с решениями, полученными графически.

Узлы ОДР	Xe	Xi	D
A
B		0.8	2.4
C	1.3	2.1	11.5
E	1.4	2.1	11.9
F	3.4	0.9	16.3
G	3.95		15.8
F1	2.7	2.1	17.1
F2	4.9		19.6

 

т. А: X_e = 0; X_i =0; D=4*0+3*0=0

 

т. В: X_e = 0; X_i =0.8; D=4*0+3*0.8=2.4

 

т.С: На точку С накладываются ограничения 3 и 4, поэтому

X_i – X_e ≤ 0.8

X_i ≤ 2.1

 

Х_е = 1,3

Следовательно, Х_е = 1,3; X_i = 2,1; D=4*1,3+3*2,1=11,5

 

т.Е: на точку Е накладываются ограничения 1 и 4

1,2X_e + 2X_i ≤5.9

X_i ≤ 2.1

 

X_e=1.4; X_i = 2.1; D=4*1.4+3*2.1=11.9

 

т. F: на точку F накладываются ограничения 1 и 2

 

1.2X_e + 2X_i ≤ 5.9

2X_e + 1.2X_i ≤7.9

 

X_e=3.4; X_i=0.9; D=4*3.4+3*0.9=16.3

 

т. G: X_e=3.95; X_i=0; D=4*3.95+3*0=15.8

 

После нахождения значений целевой функции D в узлах ОДР получили, что решения, полученные графическим путем равны решению, которое было проведено с помощью симплексного метода. Получили, что суточный объем производства изделия Е равно 3,4; суточный объем производства изделия I равно 0,9. Доход от производства и сбыта изделий E и I равно 16,3.

 

Выясним, какие ограничения мешают дальнейшему увеличению целевой функции.

1. Если снять ограничение (1), то точка F может перейти в точку F1, на которую действуют ограничения (2) и (4).

2X_e + 1.2X_i ≤7.9

X_i≤2.1

 

X_e = 2.7; X_i = 2.1; D=4*2.7+3*2.1=17.1

 

2. Если снять ограничение (2), то точка F может перейти в точку F2, на которую действует ограничение (1) и X_i=0.

1.2X_e + 2X_i = 5.9

X_i=0

 

X_e = 4.9; X_i=0; D=4*4.9+3*0=19.6

 

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

 

Вывод

Построил математическую модель предприятия, выпускающего изделия Е и I. С помощью Графического метода и Симплексного метода определил, что X_e – суточный объем производства изделия E должен быть равен 3.4, а X_i – суточный объем производства изделия I должен быть равен 0.9. При этом доход от производства и сбыта изделия E и I будет максимальным, и будет равен D=16,3.

Также мы ставили задачей выяснить, какие ограничения мешают дальнейшему увеличению целевой функции. Дальнейшему увеличению целевой функции мешают ограничения (1) и (2). После снятия ограничения (1) мы получаем доход 17,1. После снятия ограничения (2) мы получаем доход равный 19,6.

Следовательно, можно рекомендовать предприятию отказаться от производства товара I и переключиться на производство товара Е.