|
|
№ вар.
а11
а12
а13
а14
а21
а22
а23
а24
а31
а32
а33
а34
b1
b2
b3
с1
с2
с3
с4
1
1
0
2
1
0
1
3
2
4
2
0
4
180
210
800
9
6
4
7
Решение
1. Выберем элементы решения.
За элементы решения примем xi- количество i-го товара (элементов решений 4) i =
2. Составление системы ограничений
bj ,j = имеем 3 ограничения
3. Запишем целевую функцию.
L= max
4. Опираясь на условие задания и на перечисленные выше пункты, запишем математическую модель задачи.
L = 9*x1+6*x2+4*x3+7*x4 max
Приведем нашу математическую модель к виду ОЗЛП с помощью добавочных неотрицательных переменных, число которых равно числу неравенств. Так как имеем неравенство вида меньше/ равно, тодобавочные переменные вводим в левую часть со знаком “+”. Получаем следующее:
ОЗЛП
L = 9*x1+6*x2+4*x3+7*x4 max
Теперь определимся с существованием решения найденной ОЗЛП. Подсчитаем число уравнений(m) и число переменных(n), найдем их разность(k) и сделаем вывод. Итак, m=3, n=7, k=n-m=4. Так как число линейно независимых уравнений(m) меньше числа переменных(n),то система совместна и у нее существует бесчисленное множество решений. При этом (n-m) переменным мы можем придавать произвольные значения (свободные) и остальные m переменных (базисные) будем выражать через свободные.
Свободные: x1, x2, x3, x4
Базисные: x5, x6, x7
L = 9*x1+6*x2+4*x3+7*x4 max
опорное решение
Так как в L коэффициент при x1 больше 0 и больше всех остальных коэффициентов при переменных, то переменную x1 будем увеличивать. Определим границу увеличения x1 следующим образом: возьмем два уравнения из системы ограничений;
x5 = -x1-2x3-x4+180
x7=-4x1-2x2-4x4+800
Определим значения x1, при которых каждая из переменных x5 , x7 обратится в 0.
x5 =0
x7=0
Увеличивать x1 можно до наименьшего из найденных значений необходимо поменять местами переменные x1 и x5.
Новое решение будет следующим:
Свободные: x2, x3, x4, x5 =0
Базисные: x1, x6, x7
L=9*(180-2*x3-x4-x5)+6*x2+4*x3+7*x4=1620-18*x3-9*x4-9*x5+6*x2+4*x3+7*x4 =1620+6*x2-14*x3-2*x4-9*x5max
L = 1620+6*x2-14*x3-2*x4-9*x5max
Так как в L коэффициент при x2 больше 0, то переменную x2 будем увеличивать. Определим границу увеличения x2 по уже описанной выше схеме.
x6 = 210-x2-3x3-2x4
x7 = 80-2x2+8x3+4x5
x6 =0
x7=0
необходимо поменять местами переменные x2 и x7.
Новое решение будет следующим:
Свободные: x7, x3, x4, x5 =0
Базисные: x1, x6, x2
L = 1620+6*(40-0,5*x7+4*x3+2*x5)-14*x3-2*x4-9*x5= 1620+240-3*x7+24* x3+12*x5-14*x3-2*x4-9*x5= 1860+10* x3-2*x4+3* x5-3*x7
L = 1860+10* x3-2*x4+3* x5-3*x7
Так как в L коэффициент при x3 больше 0, то переменную x3 будем увеличивать. Определим границу увеличения x3 по уже описанной выше схеме.
x6=170-2x4-7x3-2x5+0.5x7
x2=40-0.5x7+4x3+2x5
x6 =0
x2=0
необходимо поменять местами переменные x3 и x2.
Новое решение будет следующим:
Свободные: x7, x2, x4, x5 =0
Базисные: x1, x6, x3
Видно, что получается отрицательная базисная переменная х3, поэтому очевидно, что x3 увеличивать нельзя. Поработаем с х5.
x1=180-2x3-x4-x5
x6=170-7x3-2x4-2x5+0.5x7
x2=40+4x3+2x5-0.5x7
x1 =0
x6=0
x2=0
Видим, что необходимо поменять местами х2 и х5
Новое решение будет следующим:
Свободные: x7, x3, x4, x2 =0
Базисные: x1, x6, x5
x6=170-7x3-2x4-2x5+0.5x7 x5= -40+x2-4x3+0.5x7
Видно, что получается отрицательная базисная переменная х5, поэтому очевидно, что x5 и х2 менять нельзя. Поменяем х5 с х6.
L=1860+10x3-2x4+3(85-3.5x3-x4-0.5x6+0.25x7)-3x7=2115-0.5x3-5x4-1.5x6-2.25x7
5. Симплекс-таблицы.
L = 9*x1+6*x2+4*x3+7*x4 L = 0 – (-9*x1-6*x2-4*x3-7*x4)
|
|
b |
||||
|
L |
|||||
При использовании материалов активная ссылка на источник обязательна.