Курсовая работа по «Теории принятия решения»

Признаком отсутствия целочисленного решения служит появление в симплекс-таблице  хотя бы 1 строки с дробным свободным  членом и с остальными целыми коэффициентами, т.к. в этом случае соответствующее  уравнение не имеет решения в целых числах.

 

3.1.1. Процесс  формирования правильного отсечения.

После каждой итерации система ограничений  имеет вид:

X_i=b_i - ∑a_ijx_j, x_iϵ{Бп} (5),

где Сп – множество свободных  переменных;

Бп – множество базисных переменных.

Если выполняется условие оптимальности задачи, то находим оптимальное решение, а если все компоненты оптимального плана целочисленные, то задача решена. Предположим, что некоторые b₀ – не целые. Пусть компонента i₀ не целая. Рассмотрим i₀ равенство системы 5, для которой выполняется условие оптимальности, т.е. x_io=b_io∑a_iox_j (6). Наибольшая целая часть числа а, его не превосходящая, обозначается [а], а дробная положительная {а}.

а=[a]+{a}, 0≤{a}<1 (7)

Перейдем к дальнейшему изучению уравнения 6. Найдем целую и дробную части его коэффициентов b_io и a_io. Согласно равенству 7 имеем:

b_io=[b_io]+{b_io}

a_ioj=[a_ioj]+{a_ioj}, x_jϵ{Сп}   (8)

Так как по предположению b_io е целое, то {b_io}>0, а {a_ioj}≥0. Подставив выражение 8 в равенство 6, получим:

х_io=([b_io]-∑[a_ioj]x_j)+({b_io}-∑[a_ioj]x_j) (9)

Так как первое слагаемое равенства 9 есть целое число, то для того, чтобы x_io был целой необходимо, чтобы второе слагаемое также было целым, т.е. величина L_io={b_io}-∑[a_ioj]x_j должна быть целым числом, т.к. x_i0 это координата допустимого целочисленного решения задачи 1-4, то L_io всегда целое число. Покажем, что L_io≤0. В самом деле, величина ∑[a_ioj]x_j не может быть отрицательной. Из условия 7 следует, что 0≤{b_io}<1. Так как L_io целое, то из предположения, что L_io>0 должно следовать {b_io}>1, что противоречит определению дробной части числа.

Доказано, что любое допустимое решение задачи 1-4 должно удовлетворять  неравенству {b_io}-∑[a_ioj]x_j≤0 (10).

 

3.2. Блок-схема решения  задачи.

 
3.3. Физическая интерпретация задачи.

Требуется определить максимальную по стоимости смесь сырья для изготовления пищевых концентратов, которые должны содержать питательные вещества (П). Эти вещества содержаться в сырье (М) в различных сочетаниях. Содержание питательных веществ в сырье и готовом продукте, а также цена на каждый вид сырья показаны в таблице (табл.28).

Табл.28

Виды сырья    Питательные  вещества	M1	М2	Max содержание(единиц) питательных веществ в готовом продукте
П1	2	4	17
П2	10	3	15
Цена за единицу сырья, руб.	1	4

 

 

3.4. Аналитическое решение задачи.

max   z = x₁ + 4x₂

2x₁ + 4x₂ ≤ 17

10x₁ + 3x₂  ≤ 15

x₁, x ₂ ≥ 0      x₁, x ₂ – целые

 

Решение:

Сведем задачу к каноническому  виду:

max z = x₁ + 4x₂+ 0x₃+ 0x₄

2x₁ + 4x₂ + x₃ = 17

10x₁ + 3x₂ + x₄ = 15

x_j ≥ 0 ( )

Решаем задачу симплекс методом  без учета целочисленности (табл.29):

Табл.29

Бп	Сб	А0	х1	х2	х3	х4
			1	4	0	0
х3	0	17	2	4	1	0
х4	0	15	10	3	0	1
Zj - Ci		0	-1	-4	0	0

Полученная итерация содержит отрицательные  оценки, поэтому перейдем к новому плану (табл.30).

Табл.30

Бп	Сб	А0	х1	х2	х3	х4
			1	4	0	0
х2	4	17/4	1/2	1	1/4	0
х4	0	9/4	17/2	0	-3/4	1
Zj - Ci		17	1	0	1	0

 

b2=15-(17*3)/4=9/4

a21=10-(2*3)/4=17/2

a23=0-(1*3)/4=-3/4

a24=1-(0*3)/4=1

Δ0=0-(17*(-4))/4=17

Δ1=-1-(2*(-4))/4=1

Δ3=0-(1*(-4))/4=1

Δ4=0-(0*(-4)/4=0

 

В результате решения задачи без  учета целочисленности получен  оптимальный план:

Х_нц^*(1) = (0;17/4;0;9/4)

Z_нц^*(1) = 17

В полученном плане присутствуют нецелые  компоненты. Сформируем отсечение:

{17/4}-{1/2}x1-{1/4}x3≤0

1/2x1+1/4x3≥1/4   |*4

2x1 + x3 – x5 = 1

Табл.31

Бп	Сб	А0	х1	х2	х3	х4	х5
			1	4	0	0	0
х2	4	17/4	1/2	1	1/4	0	0
х4	0	9/4	17/2	0	-3/4	1	0
-	-	1	2	0	1	0	-1
Zj - Ci		17	1	0	1	0	0

Табл.32

Бп	Сб	А0	х1	х2	х3	х4	х5
			1	4	0	0	0
х2	4	4	0	1	0	0	1/4
х4	0	3	10	0	0	1	-3/4
x3	0	1	2	0	1	0	-1
Zj - Ci		16	-1	0	0	0	1

 

b1=17/4-(1*1/4)/1=4

b2=9/4-(1*(-3/4)/1=3

a11=1/2-(1/4*2)/1=0

a12=1-(0*1/4)/1=1

a14=0-(1/4*0)/1=0

a15=0-(1/4*(-1)/1=1/4

a21=17/2-(2*(-3/4))/1=10

a22=0-(0*(-3/4))/1=0

a24=1-(0*(-3/4))/1=1

a25=0-((-1)*(-3/4))/1=-3/4

Δ0=17-(1*1)/1=16

Δ1=1-(2*1)/1=-1

Δ2=0-(0*1)/1=0

Δ4=0-(0*1)/1=0

Δ5=0-(1*(-1))/1=1

 

 

Полученная итерация содержит отрицательные  оценки, поэтому перейдем к новому плану (табл.33).

Табл.33

Бп	Сб	А0	х1	х2	х3	х4	х5
			1	4	0	0	0
х2	4	4	0	1	0	0	1/4
х1	1	3/10	1	0	0	1/10	-3/40
x3	0	2/5	0	0	1	-1/5	-17/20
Zj - Ci		163/10	0	0	0	1/10	37/40

 

b1=4-(0*3)/10=4

b3=1-(2*3)/10=2/5

a12=1-(0*0)/10=1

a13=0-(0*0)/10=0

a14=0-(1*0)/10=0

a15=1/4-(0*(-3/4))/10=1/4

a32=0-(2*0)/10=0

a33=0-(0*2)/10=0

a34=0-(1*2)/10=-1/5

a35=-1-(2*(-3/4))/10=-17/20

Δ0=16-(3*(-1))/10=163/10

Δ2=0-(0*(-1))/10=0

Δ3=0-(0*(-1))/10=0

Δ4=0-(1*(-1))/10=1/10

Δ5=1-((-1)*(-3/4))/10=37/40

 

В результате решения задачи без  учета целочисленности получен  оптимальный план:

Х_нц^*(2) = (3/10;4;2/5;0)      Z_нц^*(2) = 163/10

В полученном плане присутствуют нецелые  компоненты. Сформируем отсечение:

{2/5}-{1-1/5}x4-{1-17/20}x5≤0

4/5x4+3/20x5≥2/5    |*20

16х4+3х5-х6=8

Табл.34

Бп	Сб	А0	х1	х2	х3	х4	х5	х6
			1	4	0	0	0	0
х2	4	4	0	1	0	0	1/4	0
х1	1	3/10	1	0	0	1/10	-3/40	0
x3	0	2/5	0	0	1	-1/5	-17/20	0
-	-	8	0	0	0	16	3	-1
Zj - Ci		163/10	0	0	0	1/10	37/40	0

Табл.35

Бп	Сб	А0	х1	х2	х3	х4	х5	х6
			1	4	0	0	0	0
х2	4	10/3	0	1	0	-4/3	0	1/12
х1	1	1/2	1	0	0	1/2	0	-1/40
x3	0	8/3	0	0	1	13/3	0	-17/60
х5	0	8/3	0	0	0	16/3	1	-1/3
Zj - Ci		83/6	0	0	0	-29/6	0	37/120

 

b1=4-(1/4*8)/3=10/3

b2=3/10-(8*(-3/40))/3=1/2

b3=2/5-(8*(-17/20))/3=8/3

a11=0-(0*1/4)/3=0

a12=1-(0*1/4)/3=1

a13=0-(0*1/4)/3=0

a14=0-(16*1/4)/3=-4/3

a16=0-((-1)*1/4)/3=1/12

a21=1-(0*(-3/40))/3=1

a22=0-(0*(-3/40))/3=0

a23=0-(0*(-3/40))/3=0

a24=1/10-(16*(-3/40))/3=1/2

a26=0-((-1)*(-3/40))/3=-1/40

a31=0-(0*(-17/20))/3=0

a32=0-(0*(-17/20))/3=0

a33=1-(0*(-17/20))/3=1

a34=-1/5-(16*(-17/20))/3=13/3

a36=0-((-1)*(-17/20))/3=-17/60

Δ0=163/10-(8*37/40)/3=83/6

Δ1=0-(0*37/40)/3=0

Δ2=0-(0*37/40)/3=0

Δ3=0-(0*37/40)/3=0

Δ4=1/10-(16*37/40)/3=-29/6

Δ6=0-((-1)*37/40)/3=37/120

 

Полученная итерация содержит отрицательные  оценки, поэтому перейдем к новому плану (табл.36).

Табл.36

Бп	Сб	А0	х1	х2	х3	х4	х5	х6
			1	4	0	0	0	0
х2	4	4	0	1	0	0	1/4	0
х1	1	1/4	1	0	0	0	-3/32	1/160
x3	0	1/2	0	0	1	0	-13/16	-1/80
х4	0	1/2	0	0	0	1	3/16	-1/16
Zj - Ci		195/12	0	0	0	0	29/32	1/160