2-ma’ruza. Chiziqli programmalash-tirishning umumiy masalasi va uni geometrik talqini reja

Chiziqli programmalash masalasining geometrik talqini

Chiziqli programmalash masalarini yechishni sodda usullaridan biri geometrik (grafik) usuldir.

Quyidagi masalani qaraylik.
1-Masala. Ikki xil benzindan ikki xil A va V aralashmalar tayyorlanadi. A aralashmaning tarkibi 60% 1 nav va 40% 2-nav; V aralashmaning tarkibi 80% 1-nav va 20% 2-nav benzindan iborat. A aralashmani sotish bahosi 10 sent, V aralashmaniki esa - 12 sent.
Agar 50 t 1-nav va 30 t 2-nav benzin mavjud bo‘lsa aralashmalarni hosil qilish rejasini shunday tuzish kerakki, natijada olingan foyda eng ko‘p bo‘lsin.
Yechish. Masala shartlarini tushunish qulay bo‘lishi uchun barcha ma’lumotlarni 1-jadvalga joylashtiramiz.
1-jadval

Mavjud benzin			aralashma turlari		Foizlar nisbati		1 kg narxi
1-nav	2-nav	1-nav			2-nav
50t	30t	A V		60% 80%		40% 20%	10 s 12 s

bilan A aralashma miqdorini belgilaymiz (tonna), bilan aralashma miqdorini belgilaymiz (tonna). va larning miqdorini shunday rejalashtiraylikki hosil bo‘lgan aralashmalarni sotishdan keladigan daromad eng ko‘p bo‘lsin.
A aralashmaning 1 tonnasi 100 $, u holda tonnaniki $ bo‘ladi. Xuddi shunday 1 tonna V aralashma 120 $ bo‘lsa, u holda tonnaniki bo‘ladi. Shunday qilib umumiy daromadni ifodalovchi

chiziqli formani maksimallashtirish kerak. Bunda va miqdorlar ixtiyoriy bo‘lmasdan ma’lum cheklanishlarga ega. Birinchidan va lar manfiy bo‘lmasligi kerak. Ikkinchidan A va V aralashmalarga ketadigan 1-navli benzinning miqdori 50 t dan oshmasligi kerak. Xuddi shunday 2-nav benzinning miqdori 30 t dan oshmasligi kerak.
A aralashmaning har bir tonnasiga 1-nav benzindan 0,6 t (60%) ketadi; tonnaga esa – 0,6 tonna 1-nav benzin ketadi. Xuddi shunday V aralashmaga 0,8 tonna 1-nav benzin ketadi. Shunday qilib

bo‘lishi kerak. Xudi shunday 2-nav benzin sarfi quyidagi tengsizlikni qanoatlantirishi kerak
.
Shunday qilib quyidagi masalaga kelamiz:
(1)
shartlarda
(2)
chiziqli formaning maksimal qiymati topilsin.
Masalani yechimini topish uchun (1) tengsizliklar sistemasini qanoatlantiruvchi qavariq ko‘pburchakni tuzamiz. Buning uchun tekislikda va to‘g‘ri chiziqlarni chizamiz. Bular koordinatalar o‘qlari bilan birga (1) sistemaning yechimi bo‘lgan qavariq to‘rtburchakni hosil qiladi (1-shakl).

1-shakl

Ko‘pburchakning ichida yoki tomonlarida yotgan har bir nuqta biror yechim bo‘lib hisoblanadi. Masalan, koordinatalari va bo‘lgan nuqta (1) sistemani qanoatlantiradi va 60 t A aralashmadan va 15 t V aralashmadan tayyorlanganligini bildiradi. Bunda foyda

ni tashkil etadi.
Bunday tuzilgan rejada aralashma tayyorlash uchun hamma benzin ishlatilmagan (2t 1-nav, 3t 2- nav benzin ishlatilmay qolgan).
Hamma benzin ishlatilganligi yoki optimal planni topish uchun quyidagicha ish ko‘ramiz:

tenglamaning to‘g‘ri chizig‘ini o‘tkazamiz. Tenglamaning chap tomoni aralashmani sotishdan tushgan pul. Shuning uchun

to‘g‘ri chiziq rejaning ishlamaganligini bildiradi. Xaqiqatdan ham to‘g‘ri chiziq tenglamasini qanoatlantiradi. Bu lar shuni bildiradiki, aralashma tayyorlanmagan va qayta ishlanmagan. Bu to‘g‘ri chiziqni vektor yo‘nalishi bo‘yicha perpendikulyar ravishda koordinatalar boshidan o‘tkazib, o‘ziga parrallel ravishda qavariq to‘plamga qarata siljitib boramiz. Bunda maqsad funksiya o‘zining maksimal qiymatiga ko‘pburchakning chetki nuqtasida erishadi. Shunday qilib nuqta chiziqli formaga maksimal qiymat beruvchi nuqtadir. Endi nuqtaning koordinatalarini, ya’ni to‘g‘ri chiziqlarning kesishish nuqtasini topamiz.

.

Shunday qilib agar aralashmadan 70 t va aralashmadan 10 t ishlab chiqilsa maksimal foyda olinar ekan. Bunday rejadagi aralashmalarni sotishdan tushgan mablag‘ quyidagicha bo‘ladi

.
2- masala. Mexanik sex uch xil o‘zaro almashinishi mumkin bo‘lgan detallarni ketma-ket uchta stanok orqali ishlab chiqaradi. Stanoklarning quvvati zahirasi (ishlash soati) mos holda 220, 400 va 100 soatni tashkil etadi. Vaqt sarfi detal uchun 1- stanokda 12 min.; 2-stanokda -15 min.; 3- stanokda -6 min; V detal uchun mos holda 10, 18 va 4 minut; S detal uchun esa - 9, 20 va 4 minutni tashkil etadi. Ishlab chiqarilgan detalning narxi 30 so‘m, detalniki 32 so‘m va S detalniki 29 so‘m . Stanoklarni ishlashini shunday tashkil etish kerakki natijada sexga keladigan foyda eng ko‘p bo‘lsin.

Yechish. Ma’lumotlarni 2-jadvalga joylashtiramiz.

2 – jadval

Stanoklar	Detallarning turlari va ularga ishlov berish vaqti, minut			Stanoklarni maksimal ishlatish vaqti, minut
	A	V	S
1	12	10	9	13200
2	15	18	20	24000
3	6	4	4	6000
Narxi, so‘m	30	32	29

Faraz qilaylik sex A detaldan ta, V detaldan ta, S detaldan ta ishlab chiqaradi. Birinchi stanok A detalga ishlov berish uchun 12 minut vaqt sarflasa, u xolda ta detal uchun minut vaqt sarflanadi; V detaldan tasiga 10 min, S detaldan tasiga 9 minut sarflanadi. 1- stanokning hamma detallar uchun ishlov berishiga ketgan vaqti minutdan ortiq bo‘lmasligi kerak. Shunday qilib quyidagi tengsizlikni hosil qilamiz.

Xuddi shunday 2- va 3- stanoklar uchun quyidagi tengsizliklarga ega bo‘lamiz

Bu tengsizliklarning ma’nosi shuki, stanoklar sarflagan vaqtlar zaxiradagi vaqtdan oshmasligi kerak.
Sexning umumiy daromadi ni tashkil etadi. Shunday qilib quyidagi masalaga keldik
(3)
chegaraviy shartlarda chiziqli formaning maksimal qiymati topilsin.
Yuqorida ta’kidlangan grafik usulni bu masalaga ham qo‘llash mumkin. Tekisliklarning kesishishidan hosil bo‘lgan figuraning qirralarida maqsad funksiya o‘zining eng katta qiymatiga erishadi. Buning uchun tekisliklarning kesishish nuqtasini, ya’ni (3) ga mos keluvchi tenglamalar sistemasining yechimlarini topamiz


Kramer formulasiga binoan quyidagiga ega bo‘lamiz:

Bu planda detallarni ishlab chiqarishdan keladigan sex daromadi quyidagini tashkil etadi
so‘m.
Yuqorida ta’kidlangan usul chiziqli programmalash masalalarini yechishning grafik usuli deyiladi. Bu usul ikki yoki uch o‘zgaruvchili tenglamalar sistemasini yechish imkonini beradi. Chiziqli programmalashning ko‘pchilik masalalari ko‘p o‘zgaruvchili bo‘lgan chiziqli tenglamalar yoki tengsizliklar sistemasini yechishga olib kelinadi. Bunday masalalarni yechish uchun boshqa usullar qo‘llaniladi. Bu usullar bilan kelgusida tanishamiz.