1730
.pdf11
20-29. Решить задачу линейного программирования с известным опорным планом X0{x1, x2, x3, x4 ,0,0} симплексным методом.
20*. F(x)=(1/2)x5+x6 - max
x1 |
+2x5+3x6=6, |
|
x2 |
+3x5-2x6=4, |
|
x3 |
+ x5+4x6=2, |
|
x4 |
-2x5+x6=5. |
|
xi≥0 |
|
|
21. F(x)=4x5-x6 |
- max |
|
x1 |
- x5+4x6=2, |
|
x2 |
+2x5- x6=3, |
|
x3 |
+2x5-3x6=4, |
|
x4 |
-3x5+2x6=1. |
|
xi≥0 |
|
|
22. F(x)=-x5+2x6 |
- max |
|
x1 |
+x5-3x6=3, |
|
x2 |
-3x5+2x6=6, |
|
x3 |
+3x5+x6=2, |
|
x4 |
-2x5+3x6=4. |
|
xi≥0 |
|
|
23. F(x)=x5+2x6 |
- max |
|
x1 |
+x6=6, |
|
x2 |
+3x5+2x6=33, |
|
x3 |
+ x5- |
x6=6, |
x4 |
+2x5- 4x6=3. |
|
xi≥0 |
|
|
24. F(x)=x1-x4+x6 - max |
||
x1 |
-x5+x6=3, |
|
x2 |
-x5+x6=8, |
|
x3 |
-x5+4x6=12, |
|
x4 +x5-x6=4. |
||
xi≥0 |
|
|
25. F(x)=x1-3x4-x5+3x6 |
- max |
|
x1 |
-x5+x6=3, |
|
x2 |
-x5+4x6=21, |
|
x3 |
+4x5-x6=21, |
|
x4 |
+x5-x6 =3, |
|
xi≥0. |
|
|
12
26. . F(x)=2x5+x6 - max
x1 |
-2x5+x6=3, |
x2 |
+x5+4x6=30, |
x3 |
+3x5+2x6=30, |
x4 |
+3x5-4x6 =12, |
xi≥0. |
|
27. . F(x)=-2x3-x4 - max |
|
x1 |
-2x5-x6=2, |
x2 |
-x5-2x6=7, |
x3 |
+x5+2x6=16, |
x4 |
+x5+x6 =14, |
xi≥0. |
|
28. . F(x)=4x1+5x5 - max |
|
x1 |
-2x5+x6=2, |
x2 |
-x5+4x6=12, |
x3 |
+3x5-x6=16, |
x4 |
+x5-x6 =4, |
xi≥0. |
|
29. . F(x)= 3x4+2x5-3x6 - max |
|
x1 |
+x5+3x6=2, |
x2 |
+x5 - x6=1, |
x3 |
-x5 - x6=1, |
x4 |
-6x5+x6 =10, |
xi≥0. |
|
2*. . F(x)= x2-x3-4x5+5x6 - max
x1 |
-2x5+3x6=1, |
x2 |
-x5+3x6=13, |
x3 |
+4x5+x6=26, |
x4 |
+x5-3x6 =0, |
xi≥0. |
|
Указания по составлению симплексной таблицы
Симплексная таблица для задачи
F(x)=c1x1+c2x2+c3x3+…+c6x6 –max,
x1 |
+h15 x5+h16 x6=f1, |
x2 |
+ h25 x5+h26 x6=f2 |
x3 |
+ h35 x5+h36 x6=f3, |
x4 |
+ h45 x5+h46 x6=f4 |
xi≥0. |
|
13
Выглядит следующим образом:
ci |
|
B |
fi |
-c1 |
|
-c2 |
|
-c3 |
-c4 |
-c5 |
-c6 |
∑ |
fi/his |
|
|
|
|
x1 |
|
x2 |
|
x3 |
x4 |
x5 |
x6 |
|
|
c1 |
|
x1 |
f1 |
1 |
|
0 |
|
0 |
0 |
h15 |
h16 |
|
|
c2 |
|
x2 |
f2 |
0 |
1 |
|
0 |
0 |
h25 |
h26 |
|
|
|
c3 |
|
x3 |
f3 |
0 |
0 |
|
1 |
0 |
h35 |
h36 |
|
|
|
c4 |
|
x4 |
f4 |
0 |
0 |
|
0 |
1 |
h45 |
h46 |
|
|
|
|
4 |
|
|
0 |
0 |
|
0 |
0 |
|
|
|
|
|
F0= ∑ci fi |
|
|
|
|
|
|
|
5 |
6 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
i =1 |
|
|
|
|
|
|
|
|
|
|
|
Первый столбик содержит коэффициенты при базисных неизвестных в целевой функции. Во втором столбике выписаны базисные неизвестные, в третьемправые части уравнений системы ограничений. Дальше записана матрица из коэффициентов системы ограничений. В предпоследний столбик ∑ записывают суммы элементов строк таблицы. В дальнейшем с этими числами производятся те же преобразования, что и с другими элементами таблицы, при этом полученные значения должны каждый раз совпадать с суммой элементов соответствующих строк. Этот столбец нужен для контроля за вычислениями. В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции с противоположными знаками.
В последней строке записываются значения целевой функции F0(X0) при данном опорном плане X0{f1, f2, f3, f4, 0,0}, которые вычисляются по формуле
F0= ∑4 сi fi
i=1
И далее оценки свободных неизвестных, найденные по формуле
i = ∑4 |
ci hij −c j , j=1,2,3,4,5,6. |
i=1 |
|
Если среди оценок |
j есть отрицательные, то опорный план X0 не |
является оптимальным и значение функции F0 можно улучшить. Для этого нужно пересчитать симплексную таблицу, выбрав соответствующим образом ключевой элемент, стоящий на пересечении ключевой строки и ключевого столбца. За ключевой столбец берут тот, в котором находится отрицательная оценка. (Если отрицательных оценок больше одной, то рекомендуется выбирается столбик с наибольшей по абсолютной величине оценкой).
Для нахождения ключевой строки составляем отношения правых частей fi к положительным элементам ключевого столбца. Полученные значения записываются в последний столбец симплексной таблицы. Из них выбираем наименьшее, которое и указывает нам ключевую строку.
14
Решение задачи 2*:
Составим симплексную таблицу.
ci |
|
B |
|
fi |
|
0 |
|
-12 |
|
|
1 |
0 |
|
4 |
|
-5 |
∑ |
|
fi/his |
|
|
|
|
|
|
x1 |
|
x2 |
|
|
x3 |
x4 |
|
x5 |
|
x6 |
|
|
|
0 |
|
x1 |
|
1 |
|
1 |
|
0 |
|
|
0 |
0 |
|
-2 |
|
3 |
3 |
|
|
1 |
|
x2 |
|
13 |
|
0 |
1 |
|
|
0 |
0 |
|
-1 |
|
3 |
16 |
|
||
-1 |
|
x3 |
|
26 |
|
0 |
0 |
|
|
1 |
0 |
|
4 |
|
1 |
32 |
|
||
0 |
|
x4 |
|
0 |
|
0 |
0 |
|
|
0 |
1 |
|
1 |
|
-3 |
-1 |
|
||
F0=-13 |
|
|
|
|
0 |
0 |
|
|
0 |
0 |
|
-1 |
|
-3 |
-17 |
|
|||
|
Поскольку в |
последней |
строке |
есть |
отрицательные оценки свободных |
||||||||||||||
неизвестных |
5 =-1, |
|
6 =-3, то опорный план Х0={1;13;26;0;0;0} не является |
||||||||||||||||
оптимальным. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Для пересчета таблицы за ключевой столбец выберем столбец х6 с |
||||||||||||||||||
оценкой 6 =-3. Для |
определения |
ключевой |
строки |
составим |
отношения |
элементов столбика fi к положительным элементам соответствующих строк столбика х6. Из полученных соотношений 1/3, 13/3, 26 выбираем наименьшее min{1/3, 13/3, 26}=1/3. Поэтому ключевой строкой будет первая, а ключевым элементом – элемент 3, отмеченный в таблице кружком (см. следующую таблицу).
Пересчет таблицы с помощью ключевого элемента 3 будем производить по следующему правилу. Элементы ключевой строки разделим на ключевой элемент. Элементы ключевого столбца, кроме ключевого элемента, заменим нулями. Все остальные элементы пересчитываем по правилу прямоугольника: при пересчете каждого элемента в таблице выделяется прямоугольник, диагональ которого соединяет пересчитываемый элемент с ключевым. Из произведения этих элементов вычитаем произведение элементов, стоящих на концах другой диагонали этого прямоугольника. Полученная разность делится на ключевой элемент.
ci |
B |
fi |
0 |
|
-12 |
|
1 |
0 |
4 |
-5 |
∑ |
fi/his |
|
|
|
x1 |
|
x2 |
|
x3 |
x4 |
x5 |
x6 |
|
|
0 |
x1 |
1 |
1 |
|
0 |
|
0 |
0 |
-2 |
3 |
3 |
1/3 |
1 |
x2 |
13 |
0 |
1 |
|
0 |
0 |
-1 |
3 |
16 |
13/3 |
|
-1 |
x3 |
26 |
0 |
0 |
|
1 |
0 |
4 |
1 |
32 |
26 |
|
0 |
x4 |
0 |
0 |
0 |
|
0 |
1 |
1 |
-3 |
-1 |
|
|
F0=-13 |
|
|
0 |
0 |
|
0 |
0 |
-1 |
-3 |
-17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ci |
B |
fi |
0 |
|
-12 |
|
1 |
0 |
4 |
-5 |
∑ |
fi/his |
|
|
|
x1 |
|
x2 |
|
X3 |
x4 |
x5 |
x6 |
|
|
5 |
x6 |
1/3 |
1/3 |
|
0 |
|
0 |
0 |
-2/3 |
1 |
1 |
|
1 |
x2 |
12 |
-1 |
1 |
|
0 |
0 |
1 |
0 |
13 |
12 |
|
-1 |
x3 |
77/3 |
-1/3 |
0 |
|
1 |
0 |
14/3 |
0 |
31 |
77/14 |
|
0 |
x4 |
1 |
1 |
0 |
|
0 |
1 |
-1 |
0 |
2 |
|
|
F0=-12 |
|
|
1 |
0 |
|
0 |
0 |
-3 |
0 |
-14 |
|
15
ci |
B |
fi |
0 |
|
-12 |
|
1 |
0 |
4 |
-5 |
∑ |
fi/his |
|
|
|
x1 |
|
x2 |
|
X3 |
x4 |
x5 |
x6 |
|
|
5 |
x6 |
4 |
2/7 |
|
0 |
|
1/7 |
0 |
0 |
1 |
38/7 |
|
1 |
x2 |
13/2 |
-13/14 |
1 |
|
-3/14 |
0 |
0 |
0 |
89/14 |
|
|
-4 |
x5 |
11/2 |
-1/14 |
0 |
|
3/14 |
0 |
1 |
0 |
93/14 |
|
|
0 |
x4 |
13/2 |
13/14 |
0 |
|
3/14 |
1 |
0 |
0 |
121/14 |
|
|
F0=9/2 |
|
|
11/14 |
0 |
|
0 |
0 |
0 |
0 |
83/14 |
|
После первого пересчета мы получим вторую таблицу, из которой видно, что опорный план X1={0; 12; 77/3; 1; 0; 1/3} не является оптимальным, т.к. в
последней строке имеется отрицательная оценка 5 =-3. Поэтому, выбрав по
указанному выше правилу ключевой элемент 14/3, пересчитаем таблицу и придем к третьей таблице, в которой нет отрицательных оценок.
Это говорит о том, что мы получили оптимальный план
Xопт.={0; 13/2; 0; 13/2; 11/2; 4} При этом Fmax=F2=9/2.
Библиографический список Основная литература
1.Общий курс высшей математики для экономистов [Текст] : учебник / под ред. В. И. Ермакова – М. :ИНФРА-М, 2003. - 656 с.
2.Чернышов, К. И. Линейное программирование [Текст] : тексты лекций / К. И. Чернышов, Г. Д. Чернышова ; ВГЛТА. – Воронеж, 2006. – 48 с.
Дополнительная литература 1.Крейн, С. Г. Математическое программирование [Текст] / С. Г. Крейн. – Воронеж : Изд-во ВГУ, 1983. – 160 с.
16
Кругляк Владимир Викторович Перелыгина Екатерина Николаевна
ЛАНДШАФТНАЯ АРХИТЕКТУРА
Методические указания
квыполнению самостоятельной работы для студентов специальности 260500 (250203) – Садово-парковое и ландшафтное строительство
Подписано в печать 18.07.2008. Формат 60x84 1/16. Объём 1,0 п.л. Усл. печ.л. 0,93. Уч.-изд. л. 1,15. Тираж 70 экз. Заказ
ГОУ ВПО «Воронежская государственная лесотехническая академия» РИО ГОУ ВПО «ВГЛТА». 394613, Воронеж, ул. Тимирязева, 8 Отпечатано в УОП ГОУ ВПО «ВГЛТА». 394613, Воронеж, ул. Докучаева, 10