1-лаборатория: Чизиқли дастурлаш масалалари

1-лаборатория: Чизиқли дастурлаш масалалари

Оптималлаш масалалари ечими қуйидаги шартларда берилади:

самарадорлик кўрсаткичи Е х₁, х₂, … ларда чизиқли функцияда ифодаланади;

мумкин бўлган ечимлар чегаралари чизиқли тенглама ёки тенгсизликлар кўринишига эга бўлиб, чизиқли дастурлаш масалалари деб аталади.

Шунга ўхшаш масалалардан баъзиларини кўриб чиқамиз.

1) озиқ‑овқат захираси масаласи:

Бунда

П₁, П₂, П₃, П₄ – тўрт хил кўринишдаги озуқа махсулоти;

С₁, С₂, С₃, С₄ – махсулотларнинг бирлик нархи.

Бу озуқа махсулотларидан озиқ‑овқат захирасини тузиш керак, яъни қуйидаги шартлар бўлиши керак:

• 
  оқсиллар в₁ бирликдан кам бўлмасин;
  
• 
  углеводлар в₂ бирликдан кам бўлмасин; (1.1)
  
• 
  ёғлар в₃ бирликдан кам бўлмасин.
  

Ҳар бир бирлик махсулот елементлари таркиби:

Жадвал 1.1.

		Элемент
		Оқсил	Углевод	Ёғ
Махсулот	П1	а11	а12	а13
	П2	а21	а22	а23
	П3	а31	а32	а33
	П4	а41	а42	а43

Минимал ҳаражатлар эвазига 1.1 шартни таъминловчи озиқ‑овқат захирасини тузиш талаб этилади.

х₁, х₂, х_3, х₄ – озиқ‑овқат захирасига кирувчи П₁, П₂, П₃, П₄ тураи махсулотларнинг миқдори.

Шубхасиз,

Е= С₁х₁+ С₂х₂+ С₃х₃+ С₄х₄ – озиқ‑овқат захираси нархи

Ёки (1.2)

Шартнинг (1.1) математик ёзилиши қуйидагича

чегаралар: (1.3)

Масаланинг қўйилиши қуйидагича бўлади:

Шундай х₁, х₂, х_3, х₄, ларни танлаш керакки (1.3) шартни қаноатлантирган холда (1.2) ифода минимумга эришсин.

2) станоклар таъминлаш масаласи:

Фабрикада 1‑турдаи станокдан – N1 та.

Фабрикада 2‑турдаи станокдан – N2 та.

Станоклар тўрт хил кўринишдаги матоларни чиқаради:

Т₁, Т₂, Т₃, Т₄.

Ишлаб чиқариш самарадорлиги қуидагича

	Мато тури
	Т1	Т2	Т3	Т4
1	а11	а12	а13	а14
2	а21	а22	а23	а24

1-турдаги матодан бир ойлик фойда қуйидагича:

Фабриканинг ойлик режаси қуйидагича:

Масала қуйидагича қўйилади: станокларга 4 хил матони шундай юклаш керакки, натижада режа бажарилсин ва фода максимал бўлсин.

Масаланинг математик қўйилиши қуйидагича:

–1‑турдаги станок ва Т₁ мато чиқариш билан банд;

-1‑турдаги станок ва Т₂ мато чиқариш билан банд;

…………………………..

-2‑турдаги станок ва Т₄мато чиқариш билан банд;

Умуман олганда - i турдаги станоклар сони ва T_j (i=1,2; j=1,2,3,4) мато чиқариш билан бандлари.

Шундай қилиб 8 та ечим элементи хосил бўлади:

, (1.4)

Уларни шундай танлаш керакки фойда максимал бўлсин:

(1.5)

Чегаралашлар:

Станоклар сонига қараб:

(1.6)

Ассортиментга қараб:

(1.7)

Масала қуйидагича қўйилади:

Шундай мусбат , i=1,2; j=1,2,3,4, ларни танлаш керакки натижада (1.5) функция максимумга эришсин.

3) ресурсларни тақсимоти масаласи.

Бизга берилган

R₁, R₂,…, R_m – ресурслар (хомашё, техника, ишчи кучи).

b₁, b₂,…, b_m – ресурслар сони (бирликда).

T₁, T₂,…, T_n – товар турлари,юқоридаги ресурслардан ишлаб чиқариш мумкин бўлган.

1 бирлик T_j махсулотни чиқариш учун a_ij бирлик R_i (i=1,2,…,m) ресурс лозим . Ҳар бир бирлик R_i ресурснинг нархи d_i (i=1,2,…,m) туради. Ҳар бир бирлик T_j махсулот эса c_j() нархда сотилиши мумкин.

Ҳар бир T_j махсулот турининг сони қуидагича чегараланади:

.

Масала: қайси махсулотдан қанча чиқарилса фойда максимал бўлади?

Математик моделини тузамиз:

Олайлик х₁, х₂, …, х_n –T₁, T₂,…, T_n, махсулот турларининг сони бўлсин.

Чегаралашлар:

Ишлаб чиқариш бўича:

(1.8)

Ресурслар бўича:

(1.9)

Ёки кисқача:

(1.9)

х₁, х₂, …, х_n лар орқали Е фойданинг мақсад функциясини аниқлаймиз.

T_j бирлик махсулотнинг таннархи S_j қуйидагига тенг:

(1.10)

Қисқача

(1.10’)

(1.10) бўича хисоблаб барча тан нархларни топамиз

S₁, S₂, …, S_n

T_j бирлик махсулотдан ҳақиқи фойда

(j=1,2,…,n) (1.11)

(1.11) ифодадан қуйидагига эга бўламиз

q₁, q₂, …, q_n

Умумий соф фойда Е қуйидагича :

(1.12)

Қуйидагича талаб қўйилди:

Шунда х₁, х₂,…, х_n,ларни танлаш керакки улар (1.8) ва (1.9) шартларни қаноатлантириб (1.12) Е мақсад функциясини максимумга эриштирсин.

4) Юк ташиш масалалари:

Бизда m та омбор мавжуд

- лар эса бирлик махсулотлар сони.

Бундан ташқари n пунктлар ва сўровлар мавжуд(бирлик махсулотда)

Эндиликда омбордан пунктга юк ташиш режасини тузиб чиқиш керак.

Сўровлар қуидаги шартлар асосида бажарилади.

Омборлар эса пунктлар билан маълум бир ўллар орқали боғланган. Бирлик махсулотни С_i дан П_j га ташишда таннарх га тушади.

Эндиликда биздан ҳаражатларни минималга олиб борадиган юк ташиш режасини тузиш талаб этилади.

Олалик - С_i дан П_j га олиб бориладиган махсулот сони бўлсин. Унда ечимлар элементи қуйидагича бўлади:

Ёки қисқача

Шундай ларни танлаш керакки қуйидаги шартлар бажарилсин:

1. 
   махсулот сони омбор ҳажмидан ва захирадан ортиб кетмаслиги лозим:
   

Ёки қисқача

(1.13)

2. 
   талаб қилувчи пункт сўровлари бажарилиши керак:
   

Ёки қисқача

(1.14)

Юк ташишларнинг умумий нархи

Ёки қисқача

(1.15)

Бу ерда Е мақсад функциясини минимумга етказиш керак. Бундай масалалар транспорт масаласи деб номланади.

Назорат саволлари

1. 
   Чизиқли дастурлаш масаласига қандай масалалар киради?
   
2. 
   Ўзгарувчининг аддитивлиги нима дегани?
   
3. 
   Ресурслар тақсимоти масаласининг математик моделини тузинг.
   
4. 
   Юк ташиш масаласининг математик моделини тузинг.