Моделирование и прогнозирование экономических процессов

 

 

Получаем новую симплекс-таблицу:

.........................

Итерация №2.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai4

и из них выберем наименьшее:

...........................

Следовательно, 1-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x2	2	0	1	-7/22	1/2	2/11	-1/22	4
x1	8	1	0	3/11	-1	3/11	2/11	-
F(X3)	52	0	0	91/11	-13	11/11+M	18/11+M	0

 

 

Получаем новую симплекс-таблицу:

.........................

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x4	4	0	2	-7/11	1	4/11	-1/11
x1	12	1	2	-4/11	0	7/11	1/11
F(X4)	104	0	26	9/11	0	59/11+M	6/11+M

 

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x4 = 4

x1 = 12

F(X) = 2•4 + 8•12 = 104

 

 

                                                           

Задача №9.

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

Определим максимальное значение целевой функции F(X) = x1 - x2 + x3 + x4 + x5 - x6 при следующих условиях-ограничений.

x1 + x4 + 6x6=9

3x1 + x2 - 4x3 + 2x6=2

x1 + 2x2 + x5 + 2x6=6

Введем искусственные переменные x: в 1-м равенстве вводим переменную x7; в 2-м равенстве вводим переменную x8; в 3-м равенстве вводим переменную x9;

1x1 + 0x2 + 0x3 + 1x4 + 0x5 + 6x6 + 1x7 + 0x8 + 0x9 = 9

3x1 + 1x2-4x3 + 0x4 + 0x5 + 2x6 + 0x7 + 1x8 + 0x9 = 2

1x1 + 2x2 + 0x3 + 0x4 + 1x5 + 2x6 + 0x7 + 0x8 + 1x9 = 6

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = x1-1x2+x3+x4+x5-1x6 - Mx7 - Mx8 - Mx9 → max

Из уравнений выражаем искусственные переменные:

x7 = 9-x1-x4-6x6

x8 = 2-3x1-x2+4x3-2x6

x9 = 6-x1-2x2-x5-2x6

которые подставим в целевую функцию:

F(X) = (1+5M)x1+(-1+3M)x2+(1-4M)x3+(1+M)x4+(1+M)x5+(-1+10M)x6+(-17M) → max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1	0	0	1	0	6	1	0	0
3	1	-4	0	0	2	0	1	0
1	2	0	0	1	2	0	0	1

 

Решим систему уравнений относительно базисных переменных:

x7, x8, x9,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,0,0,9,2,6)

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x7	9	1	0	0	1	0	6	1	0	0
x8	2	3	1	-4	0	0	2	0	1	0
x9	6	1	2	0	0	1	2	0	0	1
F(X0)	-17M	-1-5M	1-3M	-1+4M	-1-M	-1-M	1-10M	0	0	0

 

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai6

и из них выберем наименьшее:

...........................

Следовательно, 2-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x7	9	1	0	0	1	0	6	1	0	0	11/2
x8	2	3	1	-4	0	0	2	0	1	0	1
x9	6	1	2	0	0	1	2	0	0	1	3
F(X1)	-17M	-1-5M	1-3M	-1+4M	-1-M	-1-M	1-10M	0	0	0	0

 

 

Получаем новую симплекс-таблицу:

.........................

Итерация №1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai3

и из них выберем наименьшее:

...........................

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (12) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x7	3	-8	-3	12	1	0	0	1	-3	0	1/4
x6	1	11/2	1/2	-2	0	0	1	0	1/2	0	-
x9	4	-2	1	4	0	1	0	0	-1	1	1
F(X2)	-1-7M	-21/2+10M	1/2+2M	1-16M	-1-M	-1-M	0	0	-1/2+5M	0	0

 

 

Получаем новую симплекс-таблицу:

.........................

Итерация №2.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

...........................

Следовательно, 3-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x3	1/4	-2/3	-1/4	1	1/12	0	0	1/12	-1/4	0	-
x6	11/2	1/6	0	0	1/6	0	1	1/6	0	0	-
x9	3	2/3	2	0	-1/3	1	0	-1/3	0	1	11/2
F(X3)	-11/4-3M	-15/6-2/3M	3/4-2M	0	-11/12+M	-1-M	0	-1/12+11/3M	-1/4+M	0	0

 

 

Получаем новую симплекс-таблицу:

.........................

Итерация №3.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

...........................

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (1/3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x3	5/8	-7/12	0	1	1/24	1/8	0	1/24	-1/4	1/8	-
x6	11/2	1/6	0	0	1/6	0	1	1/6	0	0	9
x2	11/2	1/3	1	0	-1/6	1/2	0	-1/6	0	1/2	41/2
F(X4)	-23/8	-21/12	0	0	-23/24	-13/8	0	1/24+M	-1/4+M	-3/8+M	0

 

 

Получаем новую симплекс-таблицу:

.........................

Итерация №4.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai4

и из них выберем наименьшее:

...........................

Следовательно, 2-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x3	31/4	0	13/4	1	-1/4	1	0	-1/4	-1/4	1	-
x6	3/4	0	-1/2	0	1/4	-1/4	1	1/4	0	-1/4	3
x1	41/2	1	3	0	-1/2	11/2	0	-1/2	0	11/2	-
F(X5)	7	0	61/4	0	-2	13/4	0	-1+M	-1/4+M	23/4+M	0

 

 

Получаем новую симплекс-таблицу:

.........................

Итерация №5.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

Вычислим значения Di по строкам как частное от деления: bi / ai5

и из них выберем наименьшее:

...........................

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (3/4) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x3	4	0	11/4	1	0	3/4	1	0	-1/4	3/4	51/3
x4	3	0	-2	0	1	-1	4	1	0	-1	-
x1	6	1	2	0	0	1	2	0	0	1	6
F(X6)	13	0	21/4	0	0	-1/4	8	1+M	-1/4+M	3/4+M	0