Проникновение математики в экономическую науку

В примере план x₀ оптимальным не является. Это видно из 6-й строки таблицы, так как в ней имеется пять отрицательных числа: z₁- c₁ = -12,

z₂- c₂ = -14, z₃- c₃ = -17, z₄- c₄ = -28, z₅- c₅ = -7. Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, насколько увеличится эта сумма при введении в план единицы того или иного вида продукции.

 

 

 

Если в основной форме задачи линейного программирования нет m единичных векторов среди P_j, то составляется расширенная задача. С помощью обычных вычислений симплекс – метода исключают искусственные векторы из базиса. Полученный после исключения искусственных векторов план и является опорным планом исходной задачи.     

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО  ПЛАНА      

При решении задачи симплексным  методом оптимальный план задачи определяется в следующей последовательности:

1. Если первоначальный план не является оптимальным, то изучить возможность улучшения оптимального плана. Если такая возможность имеется, т.е. есть хотя бы одно отрицательное число Δ_j, то составить 2-ю симплекс – таблицу или установить неразрешимость задачи.
2. Найти направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом Δ_j, а направляющая строка – минимальным из отношений компонент столбца вектора P₀ к положительным компонентам направляющего столбца.
3. По формулам (7) – (10) определить положительные компоненты нового опорного плана, коэффициенты разложения векторов P_j по векторам нового базиса и числа F₀’, Δ_j. Все эти числа записать в новой симплекс – таблице.

b₀’=                                          (7)

                       a’_ij =                                           (8)

F₀’ = F₀ – (b_r / a_rk)*Δ_k                                                    (9)

      Δ’_j = Δ_j – (a_rj / a_rk)*Δ_k                                                   (10)

4. Проверить найденный опорный план на оптимальность. Если план не оптимален, то необходимо составить новую симплекс – таблицу и перейти к новому опорному плану, а в случае получения оптимального плана или установления неразрешимости задачи закончить процесс решения.
5. Привести найденный оптимальный план, если он существует, и величину функции стоимости.

Для примера найдем оптимальный  план. Как видно из таблицы план не      оптимальный.

                                                           

 

 

 

             Таблица 4

I	БАЗИС		Cб		P0		12		14		17		28		7		0		0		0		0		0
											P1		P2		P3		P4		P5		P6		P7		P8		P9		P10
1	P6		0        990			10	12		11		5		7		1		0		0		0		0
2	P7		0		620		6		8		2		3		4		0		1		0		0		0
3	P8		0		510		4		5		6		3		9		0		0		1		0		0
4	P9		0		390		1		2		5		4		3		0		0		0		1		0
5	P10		0		900		12		6		5		1		2		0		0		0		0		1
6					F0=0		-12		-14		-17		-28		-7		0		0		0		0		0

                                                           

Это видно из 6-й строки таблицы, так как в ней имеется  пять отрицательных числа: z₁- c₁ = -12, z₂- c₂ = -14, z₃- c₃ = -17, z₄- c₄ = -28, z₅- c₅ = -7. Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, насколько увеличится эта сумма при введении в план единицы того или иного вида продукции. Так, число –2 означает, что при включении в план производства одного Арт1”, то обеспечивается увеличение выпуска продукции на 2 руб. Если включить в план производства по одному изделию Арт2, Арт3, Арт4 и Арт5, то общая стоимость изготовляемой продукции возрастет соответственно на 5, 6, 3 и 5 руб.

Поэтому с экономической  точки зрения наиболее целесообразным является включение в план производства Арт3.  Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число Δ_j стоит в 6-й строке столбца вектора P₃. Определяем вектор, подлежащий исключению из базиса.

Для этого находим θ₀ = min (b_j / a_i5)       для a_i5 > 0, т.е.

θ₀ = min (990/5; 620/3; 510/3; 390/4; 900/1) =390/4

Найдя число 390/4 = 97,5, мы тем самым с экономической точки зрения определили, какое количество Арт3 предприятие может изготавливать с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 990, 620, 510, 390 и 900, а на одно изделие Арт3 требуется затратить сырья каждого вида соответственно 3, 4, 2, 4 и 0, то максимальное число Арт3, которое может быть изготовлено предприятием, равно min (990/5; 620/3; 510/3; 390/4; 900/1) =390/4 = 97.5, т.е. ограничивающим фактором для производства изделий Арт3 является имеющейся Пробкой. С учетом его наличия предприятие может изготовить 97.5 изделия Арт3. При этом Пробка будет полностью использована.

Следовательно, вектор P₉ подлежит исключению из базиса. Столбец вектора P₄ и 4-я строка являются направляющими. Составляем таблицу для     2-ой итерации.

 Таблица 5

I	БАЗИС	Cб	P0	12	14	17	28	7	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8	P9	P10
1	P6	0	502,5	8,75	9,5	4,75	0	3,25	1	0	0	-1,25	0
2	P7	0	327,5	5.25	6,5	1,75	0	1,75	0	1	0	-0,75	0
3	P8	0	217,5	3.25	3,5	2,25	0	2,25	0	0	1	-1/2	0
4	P4	28	97.5	1/4	1/2	5/4	1	3/4	0	0	0	1/4	0
5	P10	0	802,5	11,75	5,5	3,75	0	3,75	0	0	0	-0,25	1
6			2730	-5.5	0	18	0	14	0	0	0	7	0

  

Сначала заполняем строку вектора, вновь введенного в базис, т.е. строку, номер которой совпадает  с номером направляющей строки. Здесь  направляющей является 4-я строка. Элементы этой строки таблицы 5 получаются из соответствующих  элементов таблицы 4 делением их на разрешающий элемент. При этом в столбце С_б записываем коэффициент С₄ = 28, стоящий в столбце вводимого в базис вектора P₄. Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноименных векторов проставляем единицы, а все остальные полагаем равными нулю.

P₀ = 390/4 = 97,5 ; P₁ = 1/4; P₂ = 1/2; P₃ = 5/4; P₄ = 1; P₅ = 3/4;

P₆ =0; P₇ =0; P₈ =0; P₉ = 1/4; P₁₀ = 0.

Для определения остальных  элементов таблицы 5 применяем правило  треугольника. Эти элементы могут быть вычислены и непосредственно по рекуррентным формулам.

Вычислим элементы таблицы 5, стоящие в столбце вектора P₀. Первый из них (P₆) находится в 1-й строке этого столбца. Для его вычисления находим три числа:

1. число, стоящее в таблице 4 на пересечении столбца вектора P₀ и 1-й строки (990);
2. число, стоящее в таблице 4 на пересечении столбца вектора P₄ и 1-й строки (5);
3. число, стоящее в таблице 5 на пересечении столбца вектора P₀ и 4-й строки (97,5).

Вычитая из первого числа  произведение двух других, находим искомый элемент:

990 – 5 * 97,5 = 502,5; записываем его в 1-й строке столбца вектора P₀ таблицы 5.

Четвёртый элемент столбца  вектора P₀ таблицы 5 был уже вычислен ранее (97,5). Для вычисления остальных элементов (P₇, P₈, P₁₀) столбца вектора P₀ также находим три числа и вычисляем их.

P₇ = 620 – 3 * 97,5 = 327,5;

P₈ = 510 – 3 * 97,5 = 217,5;

P₁₀ = 900 – 1 * 97,5 = 802,5.

Значение F₀ в 6-й строке столбца вектора P₀ можно найти двумя способами:

1. по формуле F₀ = (C, P₀), т.е.

    F₀ = 0 * 502,5 + 0 * 327,5 + 0 * 217,5 + 28 * 97,5 + 0 * 802,5 = 2730

2. по правилу треугольника; в данном случае треугольник образован числами 0, -6, 97,5. Этот способ приводит к тому же результату:

     0 – (-28) * 97,5 = 2730.

При определении по правилу  треугольника элементов столбца вектора P₀ третье число, стоящее в нижней вершине треугольника, все время оставалось неизменным, и менялись лишь первые два числа. Учтем это при нахождении элементов столбца вектора P₁ таблицы 5. Для вычисления указанных элементов первые два числа берем из столбцов векторов P₁ и P₄ таблицы 4, а третье число – из таблицы 5. Это число стоит на пересечении 5-й строки и столбца вектора P₁ последней таблицы. В результате получаем значения искомых элементов:

10 – 5 * 1/4 = 8,75;

6 – 3 * 1/4 = 5,25;

4 – 3 * 1/4 = 3,25;

12 – 1 * 1/4 = 11,75.

по правилу треугольника получим -12 – 1/4* (-28) = -5,

 Аналогично находим элементы столбцов векторов P₂, P₄, P₅ и P₉.

Элементы столбца вектора P₂:

12 - 5 * 1/2= 9,5;

8 - 3 * 1/2= 6,5;

5 – 3 * 1/2= 3,5;

6 - 1 * 1/2= 5,5;

F₂ = -14 – 1/2* (-28) = 0

   Элементы столбца вектора P₃:

11 - 5/4 * 5 = 4,75;

2 - 5/4* 3 = -1,75;

6 - 5/4 * 3 = -2,25;

5 – 5/4 * 1 =3,75;

F₃= -17 - 5/4 * (-28) = 18.

Элементы столбца вектора P₅:

7 - 5*3/4 = 3,25;

4 - 3*3/4 = 1,75;

9 - 3*3/4 = 6,75;

2 - 1*3/4 = 1,25;

F₅= -7-3/4*(-28) = 14.

Элементы столбца вектора P₉:

0 - 5*1/4 = 1,25;

0 - 3*1/4 = -0,75;

0 - 3*1/4 = -0,75;

0 - 1*1/4 = -0,25;

F₉= 0 – 1/4*(-28) = 7.

                                                   Таблица 6

I	БАЗИС		Cб		P0		12		14		17		28		7		0		0		0		0		0
											P1		P2		P3		P4		P5		P6		P7		P8		P9		P10
1	P6		0        502,5			8,75	9,5		4,75		0		3,25		1		0		0		-1,25		0
2	P7		0		327,5		5.25		6,5		1,75		0		1,75		0		1		0		-0,75		0
3	P8		0		217,5		3.25		3,5		2,25		0		2,25		0		0		1		-1/2		0
4	P4		28		97.5		1/4		1/2		5/4		1		3/4		0		0		0		1/4		0
5	P10		0		802,5		11,75		5,5		3,75		0		3,75		0		0		0		-0,25		1
6					2730		-5.5		0		18		0		14		0		0		0		7		0