Контрольная работа по "Высшей математики"

Обозначим через , , планируемые объемы производства соответствующих изделий, получим задачу максимизации:

F(X)=+++

при условиях:

++ + ≤ 150

++ + ≤ 170 

++ + ≤ 190 

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0 .

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.

5x1 + 10x2 + 15x3 + 20x4 + 1x5 + 0x6 + 0x7 = 150

20x1 + 15x2 + 10x3 + 5x4 + 0x5 + 1x6 + 0x7 = 170

15x1 + 9x2 + 4x3 + 17x4 + 0x5 + 0x6 + 1x7 = 190

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

5	10	15	20	1	0	0
20	15	10	5	0	1	0
15	9	4	17	0	0	1

 

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

Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

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

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,150,170,190) Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	150	5	10	15	20	1	0	0
x6	170	20	15	10	5	0	1	0
x7	190	15	9	4	17	0	0	1
F(X0)	0	-61/2	-8	-14	-10	0	0	0

 

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

Итерация №0.

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

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

3. Определение новой  свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее:

min (150 : 15 , 170 : 10 , 190 : 4 ) = 10 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (15) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x5	150	5	10	15	20	1	0	0	10
x6	170	20	15	10	5	0	1	0	17
x7	190	15	9	4	17	0	0	1	471/2
F(X1)	0	-6,5	-8	-14	-10	0	0	0	0

 

4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x3. Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=15 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x3 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (15), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5	x6	x7
150 : 15	5 : 15	10 : 15	15 : 15	20 : 15	1 : 15	0 : 15	0 : 15
170-(150 * 10):15	20-(5 * 10):15	15-(10 * 10):15	10-(15 * 10):15	5-(20 * 10):15	0-(1 * 10):15	1-(0 * 10):15	0-(0 * 10):15
190-(150 * 4):15	15-(5 * 4):15	9-(10 * 4):15	4-(15 * 4):15	17-(20 * 4):15	0-(1 * 4):15	0-(0 * 4):15	1-(0 * 4):15
0-(150 * -14):15	-61/2-(5 * -14):15	-8-(10 * -14):15	-14-(15 * -14):15	-10-(20 * -14):15	0-(1 * -14):15	0-(0 * -14):15	0-(0 * -14):15

 

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	10	1/3	2/3	1	11/3	1/15	0	0
x6	70	162/3	81/3	0	-81/3	-2/3	1	0
x7	150	132/3	61/3	0	112/3	-4/15	0	1
F(X1)	140	-15/6	11/3	0	82/3	14/15	0	0

 

Итерация №1.

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

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

3. Определение новой  свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

min (10 : 1/3 , 70 : 162/3 , 150 : 132/3) = 41/5

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x3	10	1/3	2/3	1	11/3	1/15	0	0	30
x6	70	162/3	81/3	0	-81/3	-2/3	1	0	41/5
x7	150	132/3	61/3	0	112/3	-4/15	0	1	1040/41
F(X2)	140	-15/6	11/3	0	82/3	14/15	0	0	0

 

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=162/3 На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x1 плана 2 записываем нули. Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5	x6	x7
10-(70 *1/3):162/3	1/3-(162/3 *1/3):162/3	2/3-(81/3 *1/3):162/3	1-(0 *1/3):162/3	11/3-(-81/3 *1/3):162/3	1/15-(-2/3 *1/3):162/3	0-(1 *1/3):162/3	0-(0 *1/3):162/3
70 : 162/3	162/3 : 162/3	81/3 : 162/3	0 : 162/3	-81/3 : 162/3	-2/3 : 162/3	1 : 162/3	0 : 162/3
150-(70 * 132/3):162/3	132/3-(162/3 * 132/3):162/3	61/3-(81/3 * 132/3):162/3	0-(0 * 132/3):162/3	112/3-(-81/3 * 132/3):162/3	-4/15-(-2/3 * 132/3):162/3	0-(1 * 132/3):162/3	1-(0 * 132/3):162/3
140-(70 * -15/6):162/3	-15/6-(162/3 * -15/6):162/3	11/3-(81/3 * -15/6):162/3	0-(0 * -15/6):162/3	82/3-(-81/3 * -15/6):162/3	14/15-(-2/3 * -15/6):162/3	0-(1 * -15/6):162/3	0-(0 * -15/6):162/3

 

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	83/5	0	1/2	1	11/2	2/25	-1/50	0
x1	41/5	1	1/2	0	-1/2	-1/25	3/50	0
x7	923/5	0	-1/2	0	181/2	7/25	-41/50	1
F(X2)	1477/10	0	21/4	0	73/4	43/50	11/100	0