Сызықтық бағдарламалау.

Сызықты бағдарламалау 2 д.ж.с кезінде дами бастады. Осы уақытта ұйымдар мен өңдірісті жоспарлауда қажеттіліктер тіды. Негізінде өңдірісті жоспары әскери техникалардың қажетілік түсіндіру үшін қажет. Сызықты бағдарламалаудың тапсырмасы функцияның экстремуммын табумен сипатталады.

F(x)=C1+X1+ C2+X2+……+ Cn+Xn->max(min)

Мұнда:

C1, C2... Cn – коэффиценттер

Х1, Х2... Хn – белгісіз мәндер

Белгісіз мәндер Хn теріс таңбалы болмау керек немесе Х1, Х2; Хn≥0 бұл мәндер жүйеде берілген шектеулерді қанағаттандыру керек.

A₁₁x₁+a₁₂x₂+…+A_1nx_n≥(=,≤)b₁

A₂₁x₁+a₂₂x₂+…+A_2nx_n≥(=,≤)b₂

A_n1x₁+a_n2x₂+…+A_nnx_n≥(=,≤)b₃

Шектеулер қатал немесе қатал емес болуы мүмкін. Шектеулер жүйесі барлық шешімдер мүмкін болатын шешімдер деп аталады. Егер нақты мүмкін болатын шешімдерде мақсатты функциягың мәні F(x) экстремумын тапса, онда мұндай шешім қолайлы шешім деп аталады.

Шешім барысында теңсіздіктер таңбасы теңдіктерге ауыстырылады. Бұл үшін шектеулер жүйесіне қосымша айнымалылар енгізіледі. Қосымша айнымалылардың индекстері қайталанбау керек. Егер шектеулерде ≥ танбасы тұрса онда қосымша айнымалылар – танбасымен енгізіледі.

Есепті шешу үшін базисті және базисті емес айнымалылардың саны, теңсіздіктердің санына тең болып қалады.

Мысалы:

2

=>

x₁+3x₂≥10 2x1+3x2-x3=10

-10x₁-x₂8 -10x1-x2+x4=8

F(x)=2x1-x2=>max

Базисті	Базисті емес
1)X1,x2	X3=X4=0
2)x1,x3	X2=X4=0
3)x1,x4	X2=X3=0
4)x2,x3	X1=X4=0
5)x2,x4	X1=X3=0
6)x3,x4	X1=X2=0

№	X1	X2	X3	X4	F(x)≠2x1-x2->max
1	-1,2	4,1	0	0	2*(-1,2)-4,1=-6,5
2	-0,8	0	-11,6	0	X1<0
3	2,22	0	0	6,4	F(x)=2*2.22=4.44
4	0	9	17	0	F(x)=0-9=-9
5	0	-0,5	0	11,3	F(x)=0-(-0.5)=0.5
6	0	0	0	0	F(x)=0

Табылған шешімдерді кестеге толтырамыз.

№	X1	X2	X3	X4	F(x)
1	300	200	0	0
2	800	0	-700	0
3	566,8	0	0	466,6
4	0	320	0	0
5	0	425		-525
6	0	0	1700	100

СБЕ әдісімен әр-түрлі ңақты есептер шешіледі.

1. Өңдірісті жоспарлау.

2. Персоналды тағайындау.

3. Тиімді орналастыру есебі.

4. Диета құру есебі.

5. Транспорттық есебі.

Өңдірісті жобалау есебінің міндетті тұжырымдамасы:

Тігін шеберханасы 2 түрлі бұйымдар дайындайды. Көйлек және костюм. Көйлек 30 ақшалық бірлік, ал костюм 60 ақшалық бірлік тұрады. Бұйымдарды тігу кезінде 2 түрлі шикізат қолданылады. Жүн және жібек. Қоймада 21 метр жүн және 24 метр жібек бар. 1 көйлек тігу үшін 1 метр жүн және 3 метр жібек керек, ал 1 костюм тігу үшін 3 метр жүн және 2 метр жібек керек. Табыс максималды болу үшін қанша мөлшерде көйлек және костюм тігу керек.X1=көйлек мөлшері.Х2=костюмдер мөлшеріүХ1,х2≥0

F(x)=30*4+60*5=420

F(x)=80*8+60*13=240

F(x)=30*21+60*0=630

F(x)=30*0+60*12=720

F(x)=30*0+60*7=420

Мысал:

	1	2	3	4	5	F(x)
1	-20	7	-155	0	0	–
2	-0	11	58	0	0	–
3	24	3	-66	0	0	1080
4	0	0	0	0	0	0
5	0	0	0	0	0	0
6	0	0	0	0	0	0
7	0	0	0	0	0	0
8	0	0	0	0	0	0
9	0	0	0	0	0	0
10	0	0	0	0	0	0

СБЕ-ні графикалық шешуі.

СБЕ-ны шешуге арналған матрицалық тәсіл өте көп уақыт алады. Өте көп есептеулерді қажет етеді. Сондықтан СБЕ-ны шешу үшін графиклық тәсіл қолданылады. СБЕ-ні графикалық әдіспен шешу үшін шектеулер жүйесін графикалық түрге келтіреміз. Ол үшін түзулердің графигін сызамыз.

l1≈x1+3x2=21

l 2≈3x1+2x1=24

X1	X2
0	7
21	0

X1	X2
0	12
8	0

Мүмкін болатын шешімдер аймағын табамыз. Ең тиімді шешім табу үшін Градиент вектор сызамыз. Бұл вектордың басы координат жүйесінің басында болады. Ал соңы мақсатты функцияның коэфиценттерінің нүктесінде болады. Мах мәнде табу үшін в-ға перпендикуляр түзу сызамыз. Перпендикуляр түзу түсіргенде ең жоғарғы нүктені тауып, оны максималды деп атаймыз. Осылайша таптық:

М = l1 ∩ l2

Табылған шешім шектеулер жүйесің қанағаттандыру керек және тексеру керек.