"Симплексный метод в экономических задачах" (стр. 4 )

bi i=1,2	(N)	Базис (B)	XiB	aBi1= аNi 1* В-1	min XiB / aBi1
XN1 aNi1	XN3 aNi3	XBj / XBj	(XB2) ai2	(XB4) ai4
400	5	1	(XB2)	0,05	0	20	0,25	80
450	10	0	(XB4)	-0,75	1	150	6,25	24
cTN	45	0	cTB  →	80	0	P= XiB * cIB =1600
dj	-25	4	рj  →	4	0

Пояснения к формированию симплекс-таблицы 2С

1 шаг - вначале производят замену номеров вводимой в базис переменнпй (XB2) и выводимой  из него в небазисную матрицу переменной (XN3)

2 шаг – введение в  строку (сj)  базисного коэффициента целевой функции (cTB =80) переменной (XB2): 

3 шаг -  пересчет элементов  направляющей сгроки производят делением элементов направляющей  сгроки симплекс-таблицы 1С на  направляющий  элемент (20):

  a11= 5

  a13= 1/20 =  0.05

aB12=20/20  =1

aB14=0/20  =0

  X1B =400/20=20

4 шаг -  пересчет  элементов  ненаправляющей  сгроки производят вычитанием из элементов  этой  сгроки  симплекс-таблицы 1С  произведения соответствующего  элемента направляющей строки симплекс-таблицы 2С на элемент столбца (aB2) исходной  симплекс-таблицы  1С.

  a21|= 10

  a23 =0 -0,05 * 15 = -0,75

aB22 =15 -1 * 15 =0

aB24 =1 -0 * 15 = 1

  X2B = 450 - 20 * 15 = 150.

5 шаг - вычисление целевой функции (Р):

Р = cjB * XiB = 1600

6 шаг - вычисление симплексного мультипликатора (ПJ):

рJ = cjB * В-1

7 шаг - вычисление симплексного критерия (dj):

dj = рJ т*aNj - cNj

d1 = рJ *aN1 - cN1

d3 = рJ *aN3 - cN3

8 шаг - определение переменной, вводимой в базис.  В базисную матрицу должен быть введен столбец коэффициентов (аN3) переменной Х3, которая имеет наибольшую (по модулю, отрицательную величину симплексного критерия (d3=-25).  В геометрической интерпретации это  означает переход в другую, наиболее благоприятную, с точки зрения увеличения целевой функции, вершину многогранника.

9 шаг - пересчет вводимого в базис столбца коэффициентов (аB3). Эта операция выполняется последовательным умножением слева вектора (аN3) на обратную матрицу (В-1)

aB3 = аN3 * В-1

9 шаг – определение критерия вывода  переменной, из базиса, как:  min (XB/aB2)

Так как (XB/aB2=150/6,25=24) меньше, чем (XB/aB2=20/0,25=80), то  переменная (X3) подлежит выводу из базиса. 

10 шаг - определение направляющего элемента во вводимом столбце коэффициентов (необходимого для пересчета базиса). Он находится в строке,  соответствующей минимальному значению, (XB/aB2=24) модифицированного столбца и равен (aB2=6,25).

На этом вычислительные операции второго этапа, связанные с определением второго базиса и целенаправленным поиском новой вершины многогранника (нового базиса), завершены. Операции третьего этапа заключаются в формировании нового, третьего базиса и проверки его на оптимальность. Результаты этих вычислений приведены в симплексной таблице ЗС.

Симплексная таблица 3C

bi i=1,2	(N)	Базис (B)	XiB	aBi2= аNi 2* В-1	min XiB / aBi2
XN4 aNi4	XN3 aNi3	XBj / XBj	(XB2) ai2	(XB1) ai1
400	0	1	(XB2)	0,08	-0,04	14	-	-
450	1	0	(XB1)	-0,12	0,16	24	-	-
cTN	0	0	cTB  →	80	45	P= XiB * cTB =2200
dj(yj)	4	1	рj  →	1	4

1 шаг - вначале производят замену номеров вводимой в базис переменнпй (XB1) и выводимой  из него в небазисную матрицу переменной (XN4)

2 шаг – введение в  строку (сj)  базисного коэффициента целевой функции (cTB =45) переменной (XB2): 

3 шаг -  пересчет элементов  направляющей сгроки производят делением элементов направляющей  сгроки симплекс-таблицы 1С на  направляющий  элемент (6/25):

a24= 1/6,25 =  0.16

  a23= -0,75/6,25 = -0.12

aB22=0/6,25  =0

aB21=6,25/6,25  =1

  X2B =150/6,25=24

2 шаг -  пересчет  элементов  ненаправляющей  строки.

  a14|= 0 - 0.16 * 0,25 =-0.04

  a13 =0,05-(-0,12)*0,25 =0,08

aB12 =1 -0 * 0,25 =1

aB11 =0,25- 1*0,25 = 0

X1B = 20 - 24 *0,25= 14.

4 шаг - вычисление целевой функции (Р):

Р = cjB * XiB = 2200

5 шаг - вычисление симплексного мультипликатора (ПT):

рJ = сбт * В-1

6 шаг - вычисление симплексного критерия (dj):

dj = рJ *aNj - cNj

d1(4) = рJ *aN1 - cN1 

или

d2(3 = рJ *aN3 - cN3

или

Так как ни один из показателей (dj) не имеет отрицательных значений

dj = (4 – 1)

решение прямой задачи завершено.

.Заметим, что небазисная  матрица (N), на завершающем  этапе оптимального решения прямой залачи, представлена элементами  дополнительных переменных (ресурсов –XN3 и XN4). И, поэтому,  положительнве значения  симплексных  критериев (d1, d2), являющиеся индикатором  завершения  решения прямой задачи,  одновременно являются двойственными  оценками используемых ресурсов

(y1=d1=1; y2=d2=4).

Те же оценки  ресурсов (y1=1; y2=4) получены при решении  двойственной задачи  графическим методом.

4. ЗАКЛЮЧЕНИЕ

Оптимальное решение прямой задачи графическим и симплексным методами предполагает выпуск обоих видов продукции объемом 14 и 24  единиц.

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

5. Литература

1. , Линейное прораммирование, М, МИТХТ им. , 1989

2. Акулич 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9

3. ормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. —ISBN 5-8459-0857-4

4. ,   Линейное и целочисленное линейное программирование. — Нижний Новгород: Издательство Нижегородского госуниверситета им. , 2004. — С. 63-66 (раздел 2.8. Замечания о сложности решения ЗЛП).

5. Краткое описание симплекс-метода на сайте Института дистанционного обучения ИНТУИТ

6. “Исследование операций”, методичка УрГЭУ (Екатеринбург), 2002;

7. "Линейное программирование; руководство к решению задач", 2005, стр. 28 (пример 3.1 - графический метод), стр. 56 (пример 4.6 - симплекс-метод), стр. 66 (двойственность);

8. , "Математическое программирование", методичка УрГЭУ, 2003, стр. 10...18 (решение типовой задачи)

9. , "Mathcad 12", 2005, стр. 223 (задача 8.3); линейного программирования);

10. "Математическое программирование", 2006;

11. "Общий курс высшей математики для экономистов", 2007, стр. 571.

       

12. аха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8

  6. ВАРИАНТЫ ЗАДАНИЙ

Вариант “У1”
bi /Xj	X1	X2
b1=400	a11= 5	a12= 20
b2=450	a21= 10	a22 15
cj	45	80
560  Вариант 2”
bi /Xj	X1	X2
b1=700	a11= 10	a12= 6
b2=800	a21= 5	a22 12
cj	4	8

74        Вариант 3”
bi /Xj	X1	X2
b1=70	a11= 8	a12=4
b2=75	a21= 3	a22 9
cj	4	8

210        Вариант 4”
bi /Xj	X1	X2
b1=300	a11= 12	a12= 6
b2=400	a21= 4	a22 12
cj	3	6
410        Вариант 5”
bi /Xj	X1	X2
b1=600	a11= 18	a12= 12
b2=800	a21= 10	a22 20
cj	6	10

590        Вариант 6”
bi /Xj	X1	X2
b1=600	a11= 20	a12= 12
b2=800	a21= 10	a22 22
cj	8	16

3900        Вариант 7”
bi /Xj	X1	X2
b1=960	a11= 30	a12= 14
b2=780	a21= 8	a22 16
cj	40	80

400        Вариант 8
bi /Xj	X1	X2
b1=100	a11= 3	a12, 4
b2=120	a21= 8	a22 2
cj	12	16

97  Вариант 9
bi /Xj	X1	X2
b1=220	a11= 12	a12= 24
b2=160	a21= 24	a22 18
cj	3	5

1312 Вариант 10”
bi /Xj	X1	X2
b1=820	a11= 15	a12= 25
b2=660	a21= 30	a22 20
cj	24	40

1 Практическое использование находят преимузествено системы с n>m.

2 Симпексный критерий являются оценкой и  индикатором возможного улучшения целевой функции - превышение  заданного  (отрицательного) значеия прибыли единицы небазисной продукции (- cтN) над ее  базисным  значением (рТ*aNq)

3 По определению,  целевая функция прямой и двочтвенной задачи  имеют равные по модулю значения и один и тот же алгоритм решения:

       P = . сBт * В-1* b         (2.20)

для прямой задачи:         P = . сBт * XB=2200         (2.21)

       X В =В-1* b=         (2.22)

для двойственной задачи:        P = . yТ* b=2200         (2.22)

  yТ =. сBт * В-1  (2.24)

4 Введение в базис новой  переменной означает переход в новую вершину многогранника допустимых решений