MAVZU: CHIZIQLI DASTURLASH

Vazifa 2.A. Chiziqli dasturlash masalasini yechish grafik usul

Diqqat!

Bu 2073-sonli ishning SINOV VERSIYASI, asl nusxaning narxi 200 rubl. yilda ishlab chiqilgan Microsoft dasturi So'z.

To'lov. Kontaktlar.

Variant 7. Maksimal va minimal qiymatlarni topingchiziqli funksiya F = 2x 1 - 2 x 2cheklovlar bilan: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Yechim:

Tengsizlik belgilarini shartli ravishda tenglik belgilari bilan almashtirib, x1 + x2 = 4 tenglamalar tizimini olamiz;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Bu tenglamalar yordamida to‘g‘ri chiziqlar quramiz, keyin tengsizlik belgilariga muvofiq, yarim tekisliklarni tanlaymiz va ularning umumiy qismini – ODR ning ruxsat etilgan yechimlari viloyati – to‘rtburchak MNPQ ni olamiz.

Minimal funktsiya qiymati

tions - M(2; 2) nuqtada

F min = 2·2 - 2·2 = 0.

Maksimal qiymatga N nuqtada erishiladi (10; 0),

F max = 2·10 - 2·0 = 20.

Variant 8. Maksimal va minimal qiymatlarni toping

chiziqli funksiya F = x 1 + x 2

cheklovlar bilan: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Yechim:

Tengsizlik belgilarini shartli ravishda tenglik belgilari bilan almashtirib, biz x1 - 4 x2 = 4 tenglamalar tizimini olamiz;

3 x1 - x2 = 0;

Keling, bu tenglamalardan foydalanib to'g'ri chiziqlar quramiz, keyin tengsizliklar belgilariga muvofiq, biz yarim tekisliklarni tanlaymiz va ularning umumiy qismini - ODR ning ruxsat etilgan yechimlari mintaqasini - cheksiz ko'pburchak MNPQ ni olamiz.

Minimal funktsiya qiymati

tions - masalan, to'g'ridan-to'g'ri NP bo'yicha

nuqtada P(4; 0)

F min = 4 + 0 = 4.

ODR yuqoridan cheklanmagan, shuning uchun F max = + ∞.

Variant 10. Maksimal va minimal qiymatlarni toping

chiziqli funksiya F = 2 x 1 - 3 x 2

cheklovlar bilan: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

Tengsizlik belgilarini shartli ravishda tenglik belgilari bilan almashtirib, tenglamalar tizimini olamiz

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Bu tenglamalardan foydalanib to‘g‘ri chiziqlar quramiz, so‘ngra tengsizlik belgilariga muvofiq yarim tekisliklarni tanlaymiz va ularning umumiy qismini – ODR ning ruxsat etilgan yechimlar viloyatini – MNPQRS ko‘pburchagini olamiz.

G(2; -3) vektorini tuzamiz va koordinatalarning boshini chizamiz daraja chizig'i- Streyt.

Biz daraja chizig'ini yo'nalishda siljitamiz, F qiymati ortadi. S(7; 0) nuqtada maqsad funksiyasi maksimal F max =2·7–3·0= = 14 ga etadi. Darajali chiziqni yo'nalishda harakatlantiramiz, F qiymati kamayadi. Funktsiyaning minimal qiymati N(0; 5) nuqtada.

F min = 2·0 – 3·5 = –15.

Vazifa 2.B. Chiziqli dasturlash masalasini yechish

analitik simpleks usuli

Variant 7. Maqsad funksiyasini minimallashtiring F = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

cheklovlar bilan: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Yechim:

Noma’lumlar soni n=6, tenglamalar soni m=3. Demak, r = n-m = 3 ta noma’lumni erkin deb olish mumkin. Keling, x 1, x 3 va x 6 ni tanlaymiz.

Biz x 2, x 4 va x 5 asosiy o'zgaruvchilarni bo'sh bo'lganlar bilan ifodalaymiz va tizimni birlik asosiga qisqartiramiz.

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

Maqsad funktsiyasi quyidagicha ko'rinadi:

F = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Keling, x 1 = x 3 = x 6 = 0 ni qo'yamiz va asosiy o'zgaruvchilar x 2 = 2 qiymatlarini oladi; x 4 = 9; x 5 = 6, ya'ni birinchi mumkin bo'lgan yechim (0; 2; 0; 9; 6; 0), maqsad funktsiyasi F 1 = 13.

X 3 va x 6 o'zgaruvchilari manfiy koeffitsientlar bilan maqsad funktsiyasiga kiritilgan, shuning uchun ularning qiymatlari ortishi bilan F qiymati kamayadi. Masalan, x 6 ni olaylik. Tizimning 1- tenglamasidan (*) x 6 qiymatini x 6 = 1 ga oshirish mumkinligi aniq (x 2 ³ 0 bo'lganda). Bunday holda, x 1 va x 3 nolga teng bo'lib qoladi. Endi biz asosiy o'zgaruvchilar sifatida x 4, x 5, x 6 ni, erkin o'zgaruvchilar sifatida esa x 1, x 2, x 3 ni olamiz. Keling, yangi asosiy o'zgaruvchilarni yangi erkinlar bilan ifodalaylik. olamiz

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

F = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Erkin o'zgaruvchilarga nol qiymatlarni belgilaymiz, ya'ni x 1 = x 2 = x 3 = 0, x 6 = 1, x 4 = 3, x 5 = 4, ya'ni uchinchi mumkin bo'lgan yechim (0) ; 0; 0; 3; 4; 1). Bu holda F 3 = 6.

X 3 o'zgaruvchisi manfiy koeffitsientli maqsad funksiyasiga kiritilgan, shuning uchun x 3 ning nol qiymatiga nisbatan ortishi F ning kamayishiga olib keladi. 2-tenglamadan x 3 ning 1/4 gacha ko'tarilishi mumkinligi aniq. , 3-tenglamadan - 2/3 gacha. Ikkinchi tenglama muhimroqdir. X 3 o'zgaruvchisini asosiylar soniga, x 4 ni esa bo'shlar soniga aylantiramiz.

Endi biz yangi erkin o'zgaruvchilar sifatida x 1, x 2 va x 4 ni olamiz. Keling, ular orqali x 3, x 5, x 6 yangi asosiy o'zgaruvchilarni ifodalaylik. Keling, tizimni olamiz

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Maqsad funksiyasi shaklni oladi

F = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

X 1 va x 2 o'zgaruvchilari manfiy koeffitsientli maqsad funktsiyasiga kiritilgan, shuning uchun ularning qiymatlari oshgani sayin F qiymati kamayadi. Masalan, x 2 ni olaylik. Tizimning 2-tenglamasidan x 2 qiymatini x 2 = 5 gacha (x 5 ³ 0 bo'lganda) oshirish mumkinligi aniq. Bunday holda, x 1 va x 4 nol bo'lib qoladi, boshqa o'zgaruvchilarning qiymatlari x 3 = 3/2 ga teng; x 5 = 0, x 6 = 3/2, ya'ni to'rtinchi mumkin bo'lgan yechim (0; 5; 3/2; 0; 0; 3/2). Bu holda F 4 = 5/4.

Endi biz yangi erkin o'zgaruvchilar sifatida x 1, x 4 va x 5 ni olamiz. Ular orqali x 2, x 3, x 6 yangi asosiy o'zgaruvchilarni ifodalaylik. Keling, tizimni olamiz

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Maqsad funksiyasi shaklni oladi

F = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

F ifodasidagi ikkala o'zgaruvchining koeffitsientlari ijobiydir, shuning uchun F qiymatini yanada pasaytirish mumkin emas.

Ya'ni, F min ning minimal qiymati = - 5, oxirgi mumkin bo'lgan yechim (0; 5; 3/2; 0; 0; 3/2) optimaldir.

Variant 8. Maqsad funksiyasini maksimallashtirish F = 4 x 5 + 2 x 6

cheklovlar bilan: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Yechim:

Tenglamalar soni 4 ta, noma'lumlar soni 6. Shuning uchun r = n – m = 6 – 4 = 2 o'zgaruvchini erkin o'zgaruvchi sifatida, 4 ta o'zgaruvchini asosiy sifatida tanlash mumkin. Biz x 5 va x 6 ni bepul, x 1 , x 2 , x 3 , x 4 ni asosiy sifatida tanlaymiz. Keling, asosiy o'zgaruvchilarni erkinlar bilan ifodalaymiz va tenglamalar tizimini birlik asosiga keltiramiz

x 1 = 12 - x 5 - x 6;

x 2 = 30 - 5 x 5 + x 6;

x 3 = 6 - x 5 + 2 x 6;

x 4 = 9 - 3/2 x 5 + x 6;

Maqsad funksiyasini F = 4 x 5 + 2 x 6 ko'rinishda yozamiz. Erkin o'zgaruvchilarga x 5 = x 6 = 0 nol qiymatlarni belgilaymiz. Bu holda, asosiy o'zgaruvchilar x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 qiymatlarini oladi. , ya'ni birinchi mumkin bo'lgan yechimni (12, 30 , 6, 9, 0,) va F 1 = 0 ni olamiz.

Ikkala erkin o'zgaruvchi ham musbat koeffitsientlar bilan maqsad funksiyasiga kiradi, ya'ni F ni yanada oshirish mumkin.Masalan, x 6 ni asosiylar soniga aylantiramiz. (1) tenglamadan x 5 = 12 da x 1 = 0, (2) ÷ (4) x 6 da ijobiy koeffitsientlar bilan kiritilganligi aniq. Keling, yangi asosga o'tamiz: asosiy o'zgaruvchilar - x 6, x 2, x 3, x 4, bepul - x 1, x 5. Yangi asosiy o'zgaruvchilarni yangi erkin ko'rinishda ifodalaymiz.

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5;

x 4 = 21 - x 1 - 5/2 x 5;

Maqsad funksiyasi F = 24 - 2 x 1 + 2 x 5 ko'rinishda bo'ladi;

Erkin o'zgaruvchilarga x 1 = x 5 = 0 nol qiymatlarni belgilaymiz. Bu holda, asosiy o'zgaruvchilar x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 qiymatlarini oladi. , ya'ni ikkinchi mumkin bo'lgan yechimni (0, 42 , 30, 21, 0, 12) va F 2 = 24 ni olamiz.

Maqsadli funktsiya x 5 musbat koeffitsient bilan kiritilgan, ya'ni F ni yanada oshirish mumkin. Yangi asosga o'tamiz: asosiy o'zgaruvchilar - x 6, x 5, x 3, x 4, bepul - x 1 , x 2. Yangi asosiy o'zgaruvchilarni yangi erkin orqali ifodalaymiz

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2;

x 3 = 9 - 3/2 x 1 + 1/2 x 2;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5;

Maqsad funksiyasi F = 38 – 7/2 x 1 – 1/3 x 2 ko'rinishda bo'ladi;

Erkin o'zgaruvchilarga x 1 = x 2 = 0 nol qiymatlarni belgilaymiz. Bu holda, asosiy o'zgaruvchilar x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 qiymatlarini oladi. /2, ya'ni uchinchi mumkin bo'lgan yechim X 3 = (0, 0, 9, 7/2, 7, 5) va F 3 = 38 ni olamiz.

Ikkala o'zgaruvchi ham maqsad funktsiyasiga manfiy koeffitsientlar bilan kiradi, ya'ni F ning yanada oshishi mumkin emas.

Shuning uchun oxirgi mumkin bo'lgan yechim optimal, ya'ni X opt = (0, 0, 9, 7/2, 7, 5) va F max = 38.

Variant 10. Maqsad funksiyasini F = x 2 + x 3 maksimal darajaga keltiring

cheklovlar bilan: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Yechim:

Tenglamalar-cheklovlar tizimi mos keladi, chunki tenglamalar tizimi va kengaytirilgan matritsaning darajalari bir xil va 2 ga teng. Demak, ikkita o'zgaruvchini erkin, qolgan ikkita o'zgaruvchini - asosiy - bo'lishi mumkin. ikkita erkin orqali chiziqli ifodalanadi.

Erkin o'zgaruvchilar sifatida x 2 va x 3 ni olaylik.Unda asosiy o'zgaruvchilar x 1 va x 2 bo'ladi, ularni erkin ko'rinishda ifodalaymiz.

x 1 = 1 + x 2 - x 3; (*)

x 4 = 2 - x 2 + 2 x 3;

Maqsad funksiyasi allaqachon x 2 va x 3 ko'rinishida ifodalangan, ya'ni F = x 2 + x 3.

x 2 =0 va x 3 =0 uchun asosiy o'zgaruvchilar x 1 = 1, x 4 = 2 ga teng bo'ladi.

Bizda F 1 = 0 bo'lgan X 1 = (1, 0, 0, 2) birinchi mumkin bo'lgan yechim mavjud.

F ni oshirish, masalan, ijobiy koeffitsientli F ifodasiga kiritilgan x 3 qiymatini oshirish orqali mumkin (x 2 nolga teng bo'lib qoladi). Tizimning birinchi tenglamasi (*) shuni ko'rsatadiki, x 3 ni 1 ga oshirish mumkin (x 1 ³0 shartidan), ya'ni bu tenglama x 3 qiymatining oshishiga cheklov qo'yadi. Tizimning birinchi tenglamasi (*) hal qilinmoqda. Ushbu tenglamaga asoslanib, biz x 1 va x 3 ni almashtirib, yangi asosga o'tamiz. Endi asosiy o'zgaruvchilar x 3 va x 4, erkin o'zgaruvchilar esa x 1 va x 2 bo'ladi. Endi x 3 va x 4 ni x 1 va x 2 hisobida ifodalaymiz.

Biz olamiz: x 3 = 1 - x 1 + x 2; (**)

x 4 = 4 - 2 x 1 + x 2;

F = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Erkin o'zgaruvchilarni nolga tenglashtirib, biz ikkinchi ruxsat etilgan asosiy yechimni olamiz X 2 = (0; 0; 1; 4), buning uchun F 2 = 1.

F ning ortishi x2 ning ortishi bilan mumkin. Oxirgi tenglamalar tizimi (**) bo'yicha x 2 ning o'sishi cheklanmagan. Binobarin, F tobora kattaroq ijobiy qiymatlarni oladi, ya'ni F max = + ¥.

Demak, F maqsad funksiyasi yuqoridan cheklanmagan, shuning uchun optimal yechim yo'q.

Vazifa 2.D. Berilgan masalaga ikkilangan masala tuzing

asl vazifa.

Variant 7. Maqsad funksiyasini F = 2 maksimallashtirish× x 1 - x 4

cheklovlar bilan: x 1 + x 2 = 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Yechim:

2 va 3 tenglamalarga qo'shimcha o'zgaruvchilar kiritish orqali cheklovlar tizimini yagona, masalan, kanonik shaklga keltiramiz.

x 1 + x 2 = 20,

x 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Biz 2-turdagi assimetrik muammoni oldik. Ikki tomonlama muammo quyidagicha ko'rinadi:

Maqsad funksiyasini F = 20 minimallashtiring × y 1 + 5 × y2+8 × y 3

y 1 - y 3 da ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Variant 8. Maqsad funksiyasini maksimallashtirish F = x 2 - x 4 - 3× x 5

cheklovlar bilan: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Yechim:

Bizda tenglamalar ko'rinishidagi cheklovlar tizimi bilan boshlang'ich maksimallashtirish muammosi bor, ya'ni ikki tomonlama muammolar assimetrik tip 2 turiga ega, uning matematik modeli matritsa shaklida quyidagi shaklga ega:

Asl muammo: Ikki tomonlama muammo:

F = C × X max F = B T × Ymin

da A × A T da X = B × Y ≥ C T

Dastlabki masalada maqsad funksiyadagi o‘zgaruvchilar uchun koeffitsientlar qatori matritsasi C = (0; 1; 0; -1; -3; 0) ko‘rinishga ega bo‘ladi.

erkin shartlar ustuni matritsasi va cheklovlar tizimidagi o'zgaruvchilar uchun koeffitsientlar matritsasi shaklga ega.

B = 2, A = 0 - 4 1 2 -1 0

Koeffitsientlarning ko‘chirilgan matritsasi, maqsad funksiyadagi o‘zgaruvchilar uchun qator koeffitsientlar matritsasi va erkin hadlarning ustun matritsasi topilsin.

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

Ikkilamchi masala quyidagi shaklda yoziladi:

F = y 1 + 2 maqsad funksiyasining minimal qiymatini toping × y2+5 × y 3

y 1 ≥ 0 cheklovlar ostida,

2× y 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Variant 10. F = x 1 + x 2 + x 3 funksiyani minimallashtiring

cheklovlar bilan: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Yechim:

Bizda tengsizliklar ko'rinishidagi cheklovlar tizimi bilan birlamchi minimallashtirish muammosi bor, ya'ni ikki tomonlama masalalar 3-turdagi simmetrik shaklga ega, uning matematik modeli matritsa shaklida quyidagi shaklga ega:

Asl muammo Ikki tomonlama muammo

F = C × X min F = B T × Y maks

da A × X ≥ B va A T × Y ≤ S T

X ≥ 0 Y ≥ 0

Dastlabki masalada maqsad funksiyadagi o‘zgaruvchilar uchun koeffitsientlar qatori matritsa, erkin hadlar ustuni va cheklovlar tizimidagi o‘zgaruvchilar uchun koeffitsientlar matritsasi shaklga ega.

C = (1; 1; 1), B = 3, A = 6 4 5

Ikkilamchi masala matritsalarini topamiz

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Ikkilamchi muammo quyidagicha tuzilgan:

F = 2y 1 + 3y 2 + 4y 3 maqsad funktsiyasini maksimal darajaga ko'taring

cheklovlar ostida 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

Vazifa 2.C. Simpleks jadvallar yordamida chiziqli dasturlash masalasini yechish.

Variant 7. Maqsad funksiyasini maksimallashtirish F = 2 x 1 - x 2 + 3 x 3 + 2 x 4

cheklovlar bilan: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Yechim:

Keling, cheklovlar tizimini kanonik shaklga keltiraylik

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Bizda 7 ta noma'lumli 3 ta tenglamalar tizimi mavjud. 3 ta oʻzgaruvchini x 1 , z 1 , z 3 ni asosiy, x 2 , x 3 , x 4 , z 2 erkin oʻzgaruvchilar sifatida tanlaymiz va ular orqali asosiy oʻzgaruvchilarni ifodalaymiz.

(2) dan bizda x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6 bor

(1) va (3) ga almashtiring, biz olamiz

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

F - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Simpleks jadvalini tuzamiz

I takrorlash 1-jadval

Asosiy AC	Ozodlik. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) F 1 = 2.

II takrorlash 2-jadval

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) F 2 = 4.

III takrorlash 3-jadval

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV takrorlash 4-jadval

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

Indeks qatorida oxirgi jadval yo'q manfiy raqamlar, ya'ni maqsad funksiya ifodasida hamma G i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Javob: F m ax = 149/14,

optimal yechim (0; 0; 25/14; 37/14; 1/2; 0; 0)

Variant 8. Maqsad funksiyasini F = 5 x 1 - x 3 minimallashtiring

cheklovlar ostida: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Yechim:

O'zgaruvchilar soni 4, matritsaning darajasi 2, shuning uchun erkin o'zgaruvchilar soni r = 4 - 2 = 2, asosiy o'zgaruvchilar soni ham 2. Keling, x 3, x 4 ni olamiz. erkin o'zgaruvchilar, x 1, x 2 asosiy o'zgaruvchilarni erkin ko'rinishida ifodalang va tizimni birlik asosiga keltiraylik:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

F = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Tenglamalar sistemasi va maqsad funksiyasini simpleks jadvali uchun qulay shaklda yozamiz, ya'ni x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

Keling, stol tuzaylik

I takrorlash 1-jadval

Asosiy AC	Ozodlik. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) F 1 = 10.

II takrorlash 2-jadval

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) F 2 = -1.

III takrorlash 3-jadval

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

Oxirgi jadvalning indeks satrida musbat sonlar yo'q, ya'ni maqsad funksiya ifodasida hammasi G i > 0. Bizda I holat mavjud, shuning uchun oxirgi asosiy yechim optimal hisoblanadi.

Javob: F min = -7/4, optimal yechim (0; 0; 7/4; 1/2)

********************

Variant 10. Maqsad funksiyasini F = x 1 + x 2 minimallashtirish,

cheklovlar ostida: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Yechim:

O'zgaruvchilar soni 5, matritsaning darajasi 3, shuning uchun erkin o'zgaruvchilar soni r = 6-3 = 2. Erkin o'zgaruvchilar sifatida x 3 va x 4 ni va x 1 , x 2 ni olaylik. x 5 asosiy sifatida. Tizimning barcha tenglamalari allaqachon birlik asosiga qisqartirilgan (asosiy o'zgaruvchilar erkin bo'lganlar bilan ifodalanadi), lekin simpleks jadvallarini ishlatish uchun qulay bo'lmagan shaklda yozilgan. Tenglamalar sistemasini shaklda yozamiz

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4. = 5

Maqsad funksiyasini erkin o'zgaruvchilar bilan ifodalaymiz va uni F - 3 x 3 +3 x 4 = 3 ko'rinishda yozamiz.

Keling, stol tuzaylik

I takrorlash 1-jadval

Asosiy AC	Ozodlik. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

jadval 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

Oxirgi jadvalning indeks qatorida musbat sonlar yo'q, ya'ni maqsad funksiya ifodasida hammasi Gi > 0. Bizda 1-holat bor, shuning uchun oxirgi asosiy yechim optimal hisoblanadi.

Javob: F min = 3/2, optimal yechim (3/2; 0; 0; 1/2; 11/2).

Federal ta'lim agentligi

Davlat byudjeti ta'lim muassasasi

yuqoriroq kasb-hunar ta'limi

"Omsk davlat texnika universiteti"

HISOBI VA GRAFIK ISH

intizom bo'yicha "OPTIMAL BOSHQARISH NAZARIYASI »

mavzusida"OPTIMALlashtirish USULLARI VA AMALIYATLARNI TADQIQOT »

variant 7

Bajarildi:

sirtqi talaba

4-kurs ZA-419 guruhi

To'liq ismi: Kuzhelev S. A.

Tekshirildi:

Devyaterikova M.V.

Omsk - 2012 yil
^

Topshiriq 1. Chiziqli dasturlash masalalarini echishning grafik usuli.

7) 7x 1 + 6x 2 → maksimal 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

1-qadam: Mumkin hududni qurish

O'zgaruvchilar va kvadratlarning manfiy bo'lmasligi shartlari ularning ruxsat etilgan qiymatlari oralig'ini birinchi kvadrantgacha cheklaydi. Modelning qolgan to'rtta tengsizlik cheklovlarining har biri ma'lum bir yarim tekislikka to'g'ri keladi. Ushbu yarim tekisliklarning birinchi kvadrant bilan kesishishi muammoning mumkin bo'lgan echimlari to'plamini tashkil qiladi.

Modelning birinchi cheklovi shaklga ega . Undagi ≤ belgisini = belgisi bilan almashtirib, tenglamani olamiz . Shaklda. 1.1 tekislikni ikkita yarim tekislikka ajratuvchi to'g'ri chiziqni (1) belgilaydi Ushbu holatda chiziq ustida va pastda. Qaysi biri tengsizlikni qanoatlantirishini tanlash , unga berilgan chiziqda yotmagan har qanday nuqtaning koordinatalarini almashtiring (masalan, bosh X 1 = 0, X 2 = 0). To'g'ri ifodani olganimiz uchun (20 0 + 6 0 = 0 ≤15), u holda koordinatalarning kelib chiqishini o'z ichiga olgan yarim tekislik (o'q bilan belgilangan) tengsizlikni qondiradi. Aks holda, yana bir yarim tekislik.

Muammoning qolgan cheklovlari bilan ham xuddi shunday davom etamiz. Barcha qurilgan yarim tekisliklarning birinchi kvadrant shakllari bilan kesishishi A B C D(1-rasmga qarang). Bu muammoning mumkin bo'lgan sohasi.

Qadam 2. Darajali chiziqni chizish Darajali chiziq Maqsad funksiyasi - bu maqsad funktsiyasi doimiy qiymat oladigan tekislikdagi nuqtalar to'plami. Bunday to'plam tenglama bilan berilgan f ( x) = const. Keling, masalan, const = 0 va sathda chiziq chizing f ( x) = 0, ya'ni. bizning holatlarimizda to'g'ri chiziq 7 x 1 + 6x 2 = 0.

Bu chiziq koordinata boshidan o'tadi va vektorga perpendikulyar. Bu vektor (0,0) nuqtadagi maqsad funksiyasining gradientidir. Funktsiyaning gradienti - bu ko'rib chiqilayotgan nuqtada berilgan funktsiyaning qisman hosilalari qiymatlari vektori. LP muammosi bo'lsa, maqsad funktsiyasining qisman hosilalari koeffitsientlarga teng Cmen, j = 1 , ..., n.

Gradient funksiyaning eng tez o'sish yo'nalishini ko'rsatadi. Maqsad funktsiyasi darajasi chizig'ini ko'chirish f ( x) = const. gradient yo'nalishiga perpendikulyar bo'lsa, biz mintaqa bilan kesishgan oxirgi nuqtani topamiz. Bizning holatda, bu D nuqtasi bo'lib, u maqsad funktsiyasining maksimal nuqtasi bo'ladi (2-rasmga qarang).

U (2) va (3) chiziqlarning kesishmasida yotadi (1-rasmga qarang) va optimal echimni belgilaydi.

^ E'tibor bering, agar siz maqsad funktsiyasining minimal qiymatini topmoqchi bo'lsangiz, daraja chizig'i gradient yo'nalishiga qarama-qarshi yo'nalishda harakatlanadi.

^ 3-qadam. Maqsad funksiyasining maksimal (minimal) nuqtasi va optimal qiymatining koordinatalarini aniqlash

C nuqtaning koordinatalarini topish uchun to'g'ri chiziqlarga mos keladigan tenglamalardan tashkil topgan tizimni yechish kerak (bu holda 2 va 3 tenglamalar):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Biz optimal yechimni olamiz = 1,33.

^ Optimal qiymat maqsad funktsiyasi f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

NAZORAT ISHLARINI INTIPINOZ:

“OPTIMAL YECHIMA USULLARI”

Variant № 8

1. Chiziqli dasturlash masalasini grafik usulda yechish. Berilgan cheklovlar bilan funktsiyaning maksimal va minimumini toping:

,

.

Yechim

Cheklovlar tizimida maqsad funktsiyasining minimal qiymatini va maksimalni topish kerak:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Keling, mumkin bo'lgan echimlar mintaqasini quraylik, ya'ni. Tengsizliklar sistemasini grafik usulda yechamiz. Buning uchun biz har bir to'g'ri chiziqni quramiz va tengsizliklar bilan aniqlangan yarim tekisliklarni aniqlaymiz (yarim tekisliklar tub bilan ko'rsatilgan).

Yarim tekisliklarning kesishishi nuqta koordinatalari masala cheklovlar tizimining tengsizliklarini qanoatlantiradigan mintaqa bo'ladi. Eritma ko'pburchak maydonining chegaralarini belgilaymiz.

F = 0 funktsiyaning qiymatiga mos keladigan to'g'ri chiziqni quramiz: F = 2x 1 +3x 2 = 0. Maqsad funksiyasining koeffitsientlaridan tuzilgan gradient vektor F(X) ning minimallashtirish yo'nalishini ko'rsatadi. Vektorning boshi nuqta (0; 0), oxiri nuqta (2; 3). Biz bu to'g'ri chiziqni parallel ravishda harakatlantiramiz. Biz minimal yechimga qiziqqanimiz uchun, shuning uchun biz to'g'ri chiziqni belgilangan maydonga birinchi tegguncha harakatlantiramiz. Grafikda bu to'g'ri chiziq nuqta chiziq bilan ko'rsatilgan.

Streyt
mintaqani C nuqtada kesib o'tadi. C nuqta (4) va (1) chiziqlarning kesishishi natijasida olinganligi sababli, uning koordinatalari ushbu chiziqlar tenglamalarini qanoatlantiradi:
.

Tenglamalar tizimini yechib, biz quyidagilarni olamiz: x 1 = 3,3333, x 2 = 0.

Maqsad funksiyasining minimal qiymatini qanday topish mumkin: .

Keling, masalaning ob'ektiv funktsiyasini ko'rib chiqaylik.

F = 0 funktsiyaning qiymatiga mos keladigan to'g'ri chiziqni quramiz: F = 2x 1 +3x 2 = 0. Maqsad funksiyasining koeffitsientlaridan tuzilgan gradient vektor F(X) ning maksimallashtirish yo'nalishini ko'rsatadi. Vektorning boshi nuqta (0; 0), oxiri nuqta (2; 3). Biz bu to'g'ri chiziqni parallel ravishda harakatlantiramiz. Biz maksimal yechimga qiziqqanimiz sababli, biz to'g'ri chiziqni belgilangan maydonning oxirgi tegishigacha siljitamiz. Grafikda bu to'g'ri chiziq nuqta chiziq bilan ko'rsatilgan.

Streyt
mintaqani B nuqtada kesib o'tadi. B nuqta (2) va (3) chiziqlarning kesishishi natijasida olinganligi sababli, uning koordinatalari ushbu chiziqlar tenglamalarini qanoatlantiradi:

.

Maqsad funksiyasining maksimal qiymatini qanday topish mumkin: .

Javob:
Va
.

2 . Simpleks usuli yordamida chiziqli dasturlash masalasini yeching:

.

Yechim

Simpleks jadvalidan foydalanib, to'g'ridan-to'g'ri chiziqli dasturlash masalasini simpleks usuli yordamida hal qilaylik.

Maqsad funksiyasining minimal qiymatini aniqlaymiz
quyidagi shartlar ostida - cheklovlar:
.

Birinchi mos yozuvlar rejasini tuzish uchun biz qo'shimcha o'zgaruvchilarni kiritish orqali tengsizliklar tizimini tenglamalar tizimiga keltiramiz.

1-ma'no tengsizligida (≥) biz asosiy o'zgaruvchini kiritamiz x 3 minus belgisi bilan. 2-ma'no tengsizligida (≤) biz asosiy o'zgaruvchini kiritamiz x 4 . 3-ma'no tengsizligida (≤) biz x 5 asosiy o'zgaruvchini kiritamiz.

Keling, sun'iy o'zgaruvchilarni kiritamiz : 1-tenglikda biz o'zgaruvchini kiritamiz x 6 ;

Muammoni minimal darajaga qo'yish uchun maqsad funksiyasini quyidagicha yozamiz: .

Maqsad funktsiyasiga kiritilgan sun'iy o'zgaruvchilardan foydalanish uchun M jazo deb ataladigan jazo qo'llaniladi, odatda ko'rsatilmagan juda katta ijobiy raqam.

Olingan bazis sun’iy, yechim usuli esa sun’iy bazis usuli deb ataladi.

Bundan tashqari, sun'iy o'zgaruvchilar muammoning mazmuni bilan bog'liq emas, lekin ular boshlang'ich nuqtasini yaratishga imkon beradi va optimallashtirish jarayoni bu o'zgaruvchilarni nol qiymatlarni olishga va optimal echimning maqbulligini ta'minlashga majbur qiladi.

Tenglamalardan sun'iy o'zgaruvchilarni ifodalaymiz: x 6 = 4-x 1 -x 2 + x 3, biz ularni maqsad funktsiyasiga almashtiramiz: yoki.

Koeffitsient matritsasi
bu tenglamalar tizimi quyidagi ko'rinishga ega:
.

Keling, asosiy o'zgaruvchilar uchun tenglamalar tizimini yechamiz: x 6 , x 4 , x 5.

Erkin o'zgaruvchilar 0 ga teng deb faraz qilsak, birinchisini olamiz mos yozuvlar rejasi:

X1 = (0,0,0,2,10,4)

Asosiy yechim, agar u salbiy bo'lmasa, ruxsat etilgan deb ataladi.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Joriy mos yozuvlar rejasi optimal emas, chunki indeks chizig'ida ijobiy koeffitsientlar mavjud. Etakchi ustun sifatida biz x 2 o'zgaruvchisiga mos keladigan ustunni tanlaymiz, chunki bu eng katta koeffitsientdir. Keling, qiymatlarni hisoblaylik D i va ulardan eng kichigini tanlaymiz: min(4: 1, 2: 2, 10: 2) = 1.

Shuning uchun 2-qator yetakchi hisoblanadi.

Yechish elementi (2) ga teng bo'lib, yetakchi ustun va yetakchi qatorning kesishmasida joylashgan.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Biz simpleks jadvalining keyingi qismini tashkil qilamiz. X 4 o'zgaruvchisi o'rniga 1-rejaga x 2 o'zgaruvchisi kiradi.

1-rejadagi x 2 o'zgaruvchisiga mos keladigan qator 0-rejaning x 4 qatorining barcha elementlarini RE = 2 hal qiluvchi elementga bo'lish yo'li bilan olinadi. Yechish elementi o'rniga biz 1 ni olamiz. X 2 ustunining qolgan kataklarida biz nollarni yozamiz.

Shunday qilib, yangi rejada 1, satr x 2 va ustun x 2 to'ldiriladi. 1-yangi rejaning boshqa barcha elementlari, shu jumladan indeks qatorining elementlari to'rtburchaklar qoidasi bilan belgilanadi.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

Joriy mos yozuvlar rejasi optimal emas, chunki indeks qatorida ijobiy koeffitsientlar mavjud. Etakchi ustun sifatida biz x 1 o'zgaruvchisiga mos keladigan ustunni tanlaymiz, chunki bu eng katta koeffitsientdir. Keling, qiymatlarni hisoblaylik D i bo'linish qismi sifatida qator bo'yicha: va ulardan eng kichigini tanlaymiz: min (3: 1 1/2, -, 8: 2) = 2.

Shuning uchun 1-qator yetakchi hisoblanadi.

Yechish elementi (1 1/2) ga teng va yetakchi ustun va yetakchi qatorning kesishmasida joylashgan.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Biz simpleks jadvalining keyingi qismini tashkil qilamiz. X 6 o'zgaruvchisi o'rniga 2-rejaga x 1 o'zgaruvchisi kiradi.

Biz yangi simpleks jadvalini olamiz:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Indeks qatori qiymatlari orasida ijobiy qiymatlar yo'q. Shuning uchun ushbu jadval muammoning optimal rejasini belgilaydi.

Simpleks jadvalining yakuniy versiyasi:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Optimal yechimda sun'iy o'zgaruvchilar yo'qligi sababli (ular nolga teng), bu yechim joizdir.

Optimal rejani quyidagicha yozish mumkin: x 1 = 2, x 2 = 2:.

Javob:
,
.

3. Three Fat Man kompaniyasi shaharning turli hududlarida joylashgan uchta ombordan uchta do‘konga go‘sht konservalarini yetkazib beradi. Omborlarda mavjud bo'lgan konserva zaxiralari, shuningdek, do'kon buyurtmalari hajmi va etkazib berish stavkalari (odatiy pul birliklarida) transport jadvalida keltirilgan.

Eng kam pul xarajatlarini ta'minlaydigan transport rejasini toping ("shimoli-g'arbiy burchak" usuli yordamida dastlabki tashish rejasini bajaring).

Yechim

Muammoni hal qilish uchun zarur va etarli shartni tekshiramiz:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Balans sharti bajarildi. Teng ehtiyojlarni ta'minlaydi. Shuning uchun transport muammosining modeli yopiq.

Dastlabki ma'lumotlarni tarqatish jadvaliga kiritamiz.

Ehtiyojlar

Shimoli-g'arbiy burchak usulidan foydalanib, biz transport muammosining birinchi mos yozuvlar rejasini tuzamiz.

Reja yuqori chap burchakdan to'ldirila boshlaydi.

Kerakli element 4. Bu element uchun inventarlar 300, talablar 250. Minimal 250 bo'lgani uchun uni ayiramiz: .

			300 - 250 = 50
250 - 250 = 0

Kerakli element 2 ga teng. Ushbu element uchun inventar 50, talablar 400. Minimal 50 bo'lgani uchun uni ayirib tashlaymiz: .

			50 - 50 = 0
	400 - 50 = 350

Kerakli element 5. Ushbu element uchun inventar 300, talablar 350. Minimal 300 bo'lgani uchun uni ayiramiz:

			300 - 300 = 0
	350 - 300 = 50

Kerakli element 3. Ushbu element uchun inventar 200, talablar 50. Minimal 50 bo'lgani uchun uni ayiramiz:

			200 - 50 = 150
	50 - 50 = 0

Kerakli element 6. Bu element uchun inventar 150, talablar 150. Minimal 150 bo'lgani uchun uni ayiramiz:

			150 - 150 = 0
		150 - 150 = 0

Ehtiyojlar

Kirish

Insoniyat taraqqiyotining hozirgi bosqichi energiya asri o'rnini informatika asri egallashi bilan ajralib turadi. Inson faoliyatining barcha sohalariga yangi texnologiyalar jadal joriy etilmoqda. Axborot jamiyatiga o'tishning haqiqiy muammosi mavjud bo'lib, uning uchun ta'limni rivojlantirish ustuvor vazifaga aylanishi kerak. Jamiyatda bilimlarning tuzilishi ham o‘zgarmoqda. uchun ahamiyati ortib bormoqda amaliy hayot shaxsning ijodiy rivojlanishiga hissa qo'shadigan fundamental bilimlarni egallash. Olingan bilimlarning konstruktivligi va uni maqsadga muvofiq tuza bilish ham muhim ahamiyatga ega. Bilimlar asosida yangilari shakllanadi axborot resurslari jamiyat. Yangi bilimlarni shakllantirish va o'zlashtirish tizimli yondashuvning qat'iy metodologiyasiga asoslanishi kerak, uning doirasida namunaviy yondashuv alohida o'rin tutadi. Model yondashuvining imkoniyatlari qo'llaniladigan rasmiy modellar nuqtai nazaridan ham, modellashtirish usullarini amalga oshirish usullarida ham juda xilma-xildir. Jismoniy modellashtirish juda oddiy tizimlar uchun ishonchli natijalarni olish imkonini beradi.

Hozirgi vaqtda modellashtirish usullari u yoki bu darajada qo'llanilmaydigan inson faoliyati sohasini nomlash mumkin emas. Bu, ayniqsa, menejment sohasida to'g'ri keladi turli tizimlar, bu erda asosiy jarayonlar olingan ma'lumotlar asosida qaror qabul qilishdir.

1. Muammoning bayoni

minimal maqsad funktsiyasi

Topshiriqning 16-variantiga muvofiq yechim ko‘pburchagi bilan ko‘rsatilgan cheklovlar sistemasi uchun maqsad funksiyasining minimalini topish masalasini yeching. Eritma ko‘pburchagi 1-rasmda ko‘rsatilgan:

1-rasm - masala yechimlari ko'pburchagi

Cheklovlar tizimi va muammoning maqsad funktsiyasi quyida keltirilgan:

Muammoni quyidagi usullardan foydalangan holda hal qilish kerak:

LP masalalarini echishning grafik usuli;

LP masalalarini echishning algebraik usuli;

LP masalalarini yechishning Simpleks usuli;

LP muammolarining maqbul echimini topish usuli;

Ikkilamchi LP muammosini hal qilish;

Butun sonli LP masalalarini echish uchun tarmoqli va bog'langan usul;

Butun sonli LP masalalarini yechish uchun Gomori usuli;

Boolean LP muammolarini echish uchun Balazs usuli.

Yechim natijalarini solishtiring turli usullar ishdan tegishli xulosalar chiqarish.

2. Chiziqli dasturlash masalasining grafik yechimi

Chiziqli dasturlash masalalarini echishning grafik usuli noma'lumlar soni uchtadan oshmagan hollarda qo'llaniladi. Eritmalarning xossalarini sifatli tadqiq qilish uchun qulay va boshqa usullar (algebraik, tarmoqli va chegaralangan va boshqalar) bilan birgalikda qo'llaniladi. Usul g'oyasi chiziqli tengsizliklar tizimining grafik echimiga asoslangan.

Guruch. 2 LP masalasining grafik yechimi

Minimal nuqta

A1 va A2 ikkita nuqtadan o'tuvchi chiziq tenglamasi:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

cheklovlar bilan:

Chiziqli dasturlash masalasini algebraik simpleks usuli yordamida yechish

Muammoni echish uchun algebraik usulni qo'llash LP muammosining tasvirini umumlashtirishni talab qiladi. Tengsizliklar ko'rinishida ko'rsatilgan dastlabki cheklovlar tizimi cheklashlar tenglik shaklida ko'rsatilganda standart belgiga aylantiriladi. Cheklash tizimining transformatsiyasi standart ko'rinish quyidagi bosqichlarni o'z ichiga oladi:

Tengsizliklarni shunday aylantiringki, chapda o'zgaruvchilar va erkin shartlar, o'ngda esa 0, ya'ni. uchun chap tomoni noldan katta yoki teng edi;

Qo'shimcha o'zgaruvchilarni kiritish, ularning soni cheklovlar tizimidagi tengsizliklar soniga teng;

Qo'shilgan o'zgaruvchilarning manfiy emasligiga qo'shimcha cheklovlar kiritish orqali tengsizlik belgilarini qat'iy tenglik belgilari bilan almashtiring.

LP masalasini algebraik usul yordamida yechishda shart qo‘shiladi: maqsad funksiyasi minimumga intilishi kerak. Agar bu holat qanoatlantirmasa, maqsad funksiyasini mos ravishda o'zgartirish (-1 ga ko'paytirish) va minimallashtirish masalasini hal qilish kerak. Yechim topilgandan so'ng, o'zgaruvchilarning qiymatlarini asl funktsiyaga almashtiring va uning qiymatini hisoblang.

Muammoni algebraik usul yordamida hal qilish, agar barcha asosiy o'zgaruvchilarning qiymatlari manfiy bo'lmasa va maqsad funktsiyasi tenglamasidagi erkin o'zgaruvchilarning koeffitsientlari ham manfiy bo'lmaganda optimal hisoblanadi. Agar bu shartlar bajarilmasa, yuqoridagi cheklovlarning bajarilishiga erishish uchun ba'zi o'zgaruvchilarni boshqalar bilan ifodalovchi (erkin va asosiy o'zgaruvchilarni o'zgartirish) tengsizliklar tizimini o'zgartirish kerak. Barcha erkin o'zgaruvchilarning qiymati nolga teng deb hisoblanadi.

Chiziqli dasturlash masalalarini yechishning algebraik usuli eng keng tarqalganlaridan biridir samarali usullar kichik hajmdagi muammolarni qo'lda hal qilishda, chunki ko'p sonli arifmetik hisob-kitoblarni talab qilmaydi. Ushbu usulni mashinada amalga oshirish, masalan, simpleks usuliga qaraganda ancha murakkab, chunki Algebraik usuldan foydalangan holda yechim algoritmi ma'lum darajada evristik bo'lib, yechimning samaradorligi ko'p jihatdan shaxsiy tajribaga bog'liq.

Erkin o'zgaruvchilar

Sent-lane - qo'shimcha to'plam

Salbiy bo'lmagan shartlar bajarildi, shuning uchun optimal echim topildi.

3. Simpleks jadval yordamida chiziqli dasturlash masalasini yechish

Yechish: Simpleks jadvali yordamida masalani yechish uchun standart shaklga keltiramiz.

Tizimning barcha tenglamalarini quyidagi shaklga keltiramiz:

Biz simpleks jadvalini tuzamiz:

Jadvalning har bir katagining yuqori burchagiga tenglamalar tizimidan koeffitsientlarni kiritamiz;

Biz F qatorida maksimal ijobiy elementni tanlaymiz, bundan tashqari bu umumiy ustun bo'ladi;

Umumiy elementni topish uchun biz barcha ijobiy tomonlar uchun munosabatlarni quramiz. 3/3; 9/1;- x3 qatoridagi minimal nisbat. Shuning uchun - umumiy satr va =3 - umumiy element.

Biz =1/=1/3 topamiz. Biz uni umumiy element joylashgan hujayraning pastki burchagiga keltiramiz;

Umumiy chiziqning barcha bo'sh pastki burchaklarida biz hujayraning yuqori burchagidagi qiymatning mahsulotini kiritamiz;

Umumiy chiziqning yuqori burchaklarini tanlang;

Umumiy ustunning barcha pastki burchaklarida yuqori burchakdagi qiymat mahsulotini - orqali kiritamiz va natijada olingan qiymatlarni tanlaymiz;

Jadvalning qolgan kataklari tegishli tanlangan elementlarning mahsuloti sifatida to'ldiriladi;

Keyin biz yangi jadval tuzamiz, unda umumiy ustun va satr elementlarining katakchalari belgilari almashtiriladi (x2 va x3);

Ilgari pastki burchakda bo'lgan qiymatlar oldingi umumiy satr va ustunning yuqori burchagiga yoziladi;

Oldingi jadvaldagi ushbu kataklarning yuqori va pastki burchaklari qiymatlarining yig'indisi qolgan kataklarning yuqori burchagida yozilgan.

4. Chiziqli dasturlash masalasini joiz yechim topib yechish

Chiziqli algebraik tenglamalar tizimi berilsin:

Biz hamma narsani shunday deb taxmin qilishimiz mumkin, aks holda biz mos keladigan tenglamani -1 ga ko'paytiramiz.

Biz yordamchi o'zgaruvchilarni kiritamiz:

Biz yordamchi funktsiyani ham kiritamiz

Biz cheklovlar (2) va shartlar ostida tizimni minimallashtiramiz.

RUXSAT BERILGAN YECHIMI TOPISH QOIDASI: (1) tizimga ruxsat berilgan yechimni topish uchun cheklovlar (2) ostida (3) shaklni minimallashtiramiz, erkin noma’lumlar sifatida xj va asos sifatida xj ni olamiz.

Simpleks usuli yordamida muammoni hal qilishda ikkita holat yuzaga kelishi mumkin:

min f=0, u holda barcha i nolga teng bo'lishi kerak. Va natijada xj qiymatlari tizim (1) uchun maqbul echim bo'ladi.

min f>0, ya'ni. asl tizimda mumkin bo'lgan yechim yo'q.

Manba tizimi:

Oldingi mavzudagi masala shartidan foydalaniladi.

Keling, qo'shimcha o'zgaruvchilarni kiritamiz:

Asl muammoning maqbul yechimi topildi: x1 = 3, x2 = 3, F = -12. Olingan amalga oshirish mumkin bo'lgan yechimga asoslanib, biz simpleks usuli yordamida dastlabki masalaning optimal echimini topamiz. Buning uchun yuqorida olingan jadvaldan yangi simpleks jadvalini tuzamiz, yordamchi masalaning maqsadli funksiyasi bilan qator va qatorni olib tashlaymiz:

Tuzilgan simpleks jadvalini tahlil qilib, biz dastlabki muammoning optimal yechimi allaqachon topilganligini ko'ramiz (maqsad funktsiyasiga mos keladigan qatordagi elementlar manfiy). Shunday qilib, yordamchi muammoni hal qilishda topilgan mumkin bo'lgan yechim asl muammoning optimal echimiga to'g'ri keladi:

6. Ikki chiziqli dasturlash masalasi

Asl cheklovlar tizimi va masalaning maqsad funktsiyasi quyidagi rasmda ko'rsatilgan.

cheklovlar bilan:

Yechim: Cheklovlar tizimini standart shaklga keltiramiz:

Bunga ikkilangan muammo quyidagi shaklga ega bo'ladi:

Ikkilamchi masalani yechish oddiy simpleks usuli yordamida bajariladi.

Maqsad funksiyasini shunday o'zgartiramizki, minimallashtirish masalasi hal qilinadi va cheklovlar tizimini simpleks usuli yordamida yechish uchun standart shaklda yozamiz.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

F = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Ikkilamchi LP muammosini hal qilish uchun boshlang'ich simpleks jadvalini tuzamiz.

Simpleks usulining ikkinchi bosqichi

Demak, simpleks usulining uchinchi bosqichida quyidagi natijalar bilan minimallashtirish masalasining optimal yechimi topildi: y2 = -7 /8, y1 = -11/8, F = 12. ning qiymatini topish uchun. Ikki tomonlama muammoning maqsad funktsiyasi, biz asosiy va erkin o'zgaruvchilarning topilgan qiymatlarini maksimallashtirish funktsiyasiga almashtiramiz:

Fmax = - Fmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

To'g'ridan-to'g'ri va ikki tomonlama masalalarning maqsad funktsiyasining qiymati mos kelganligi sababli, to'g'ridan-to'g'ri masalaning yechimi topiladi va 12 ga teng.

Fmin = Fmax = -12

7. Butun sonli chiziqli dasturlash masalasini tarmoq va chegara usuli yordamida yechish

Dastlabki masalani shunday o‘zgartiramizki, an’anaviy usullar yordamida yechilganda butun son sharti qanoatlanmaydi.

Butun sonli dasturlash masalasi yechimlarining boshlang‘ich ko‘pburchagi.

Eritmalarning o'zgartirilgan ko'pburchagi uchun biz tuzamiz yangi tizim cheklovlar.

Cheklashlar sistemasini algebraik usul yordamida yechish uchun tenglik shaklida yozamiz.

Yechish natijasida muammoning optimal rejasi topildi: x1 = 9/4, x2 = 5/2, F = -41/4. Bu yechim masalada belgilangan butun son shartiga javob bermaydi. Dastlabki yechim ko‘pburchagini undan 3-sonli maydonni hisobga olmaganda, ikkita sohaga ajratamiz

O'zgartirilgan muammo yechimi ko'pburchak

Eritma ko'pburchakning hosil bo'lgan sohalari uchun yangi cheklashlar tizimini yarataylik. Chap maydon to'rtburchak (trapezoid). Eritma ko'pburchagining chap mintaqasi uchun cheklovlar tizimi quyida keltirilgan.

Chap hudud uchun cheklash tizimi

To'g'ri maydon C nuqtasini ifodalaydi.

To'g'ri qaror mintaqasi uchun cheklovlar tizimi quyida keltirilgan.

Yangi cheklash tizimlari bir-biridan mustaqil ravishda hal qilinishi kerak bo'lgan ikkita yordamchi muammolarni ifodalaydi. Yechim ko‘pburchakning chap mintaqasi uchun butun sonli dasturlash masalasini yechamiz.

Yechish natijasida masalaning optimal rejasi topildi: x1 = 3, x2 = 3, F = -12. Bu reja masaladagi o‘zgaruvchilar butun son bo‘lishi shartini qanoatlantiradi va asl butun sonli chiziqli dasturlash masalasi uchun optimal mos yozuvlar rejasi sifatida qabul qilinishi mumkin. To'g'ri yechim mintaqasi uchun hal qilishning ma'nosi yo'q. Quyidagi rasmda daraxt ko‘rinishidagi butun sonli chiziqli dasturlash masalasini yechish jarayoni ko‘rsatilgan.

Gomori usuli yordamida butun sonli chiziqli dasturlash masalasini yechish jarayoni.

Ko'pgina amaliy dasturlarda chiziqli tengsizliklar tizimi va chiziqli shakl berilgan butun sonli dasturlash masalasi katta qiziqish uyg'otadi.

F maqsad funksiyasini minimallashtiruvchi (1) sistemaning butun sonli yechimini topish talab qilinadi va barcha koeffitsientlar butun sonlardir.

Butun sonli dasturlash masalasini yechish usullaridan biri Gomori tomonidan taklif qilingan. Usulning g'oyasi doimiy chiziqli dasturlash usullaridan, xususan, simpleks usulidan foydalanishdir.

1) Simpleks usuli yordamida (1), (2) masalalarning yechimi aniqlanadi, buning uchun butun son yechish talabi olib tashlanadi; agar yechim butun son bo'lib chiqsa, u holda butun sonli masalaning kerakli yechimi ham topiladi;

2) Aks holda, agar biron bir koordinata butun son bo'lmasa, masalaning natijaviy yechimi butun sonli yechimning mavjudligi (ruxsat etilgan ko'pburchakda butun son nuqtalarining mavjudligi) uchun tekshiriladi:

agar kasr bo'sh hadli har qanday qatorda boshqa barcha koeffitsientlar butun son bo'lib chiqsa, u holda ruxsat etilgan ko'pburchakda butun sonlar yoki nuqtalar mavjud emas va butun sonli dasturlash muammosining yechimi yo'q;

Aks holda, qo'shimcha chiziqli cheklov kiritiladi, bu butun sonli dasturlash muammosining yechimini topish uchun istiqbolsiz bo'lgan ruxsat etilgan ko'pburchakning bir qismini kesib tashlaydi;

3) Qo'shimcha chiziqli cheklovni qurish uchun kasr bo'sh hadli l-qatorni tanlang va qo'shimcha cheklovni yozing.

bu yerda va koeffitsientlarning mos ravishda kasr qismlari va bepul

a'zosi. (3) cheklovga yordamchi o‘zgaruvchini kiritamiz:

Keling, (4) cheklovga kiritilgan koeffitsientlarni aniqlaymiz:

qayerda va mos ravishda va uchun pastdan eng yaqin butun sonlar.

Gomori o'xshash bosqichlarning cheklangan soni chiziqli dasturlash muammosiga olib kelishini isbotladi, uning yechimi butun son va shuning uchun kerakli bo'ladi.

Yechish: Chiziqli cheklovlar tizimi va maqsad funksiyasini kanonik shaklga keltiramiz:

Butun son shartidan vaqtincha voz kechib, chiziqli cheklovlar sistemasining optimal yechimini aniqlaylik. Buning uchun biz simpleks usulidan foydalanamiz. Quyida, ketma-ket jadvallarda muammoning asl yechimi keltirilgan va muammoning optimal yechimini olish uchun asl jadvalning o'zgartirishlari keltirilgan:

Balazs usuli yordamida mantiqiy LP masalalarini yechish.

Quyidagi qoidalarni hisobga olgan holda mantiqiy o‘zgaruvchilar bilan butun sonli chiziqli dasturlash muammosi uchun o‘z versiyangizni yarating: masalada kamida 5 ta o‘zgaruvchi, kamida 4 ta cheklov qo‘llaniladi, cheklovlar koeffitsientlari va maqsad funksiyasi o‘zboshimchalik bilan tanlanadi, lekin bunday hollarda cheklovlar tizimining mos keladigan usuli. Vazifa Balazs algoritmidan foydalangan holda mantiqiy o'zgaruvchilar bilan LCLP ni hal qilish va to'liq qidiruv usuli yordamida muammoni hal qilish bilan bog'liq hisob-kitoblarning murakkabligini kamaytirishni aniqlashdir.

Cheklovlarni amalga oshirish

F qiymati

Filtrlash cheklovi:

Hisoblash kuchini kamaytirishni aniqlash

To'liq qidirish usuli yordamida muammoning yechimi 6*25=192 hisoblangan ifodadir. Masalaning Balazs usuli yordamida yechimi 3*6+(25-3)=47 hisoblangan ifoda. To'liq qidiruv usuli yordamida muammoni hal qilish bilan bog'liq hisob-kitoblarning murakkabligining umumiy qisqarishi:

Xulosa

Yangi axborot texnologiyalarini joriy etuvchi axborot tizimlarini loyihalash jarayoni doimiy ravishda takomillashtirilmoqda. Tizim muhandislarining e'tibori tobora murakkab tizimlarga qaratilmoqda, bu fizik modellardan foydalanishni qiyinlashtiradi va tizimlarning matematik modellari va mashina simulyatsiyasining ahamiyatini oshiradi. Mashina simulyatsiyasi murakkab tizimlarni o'rganish va loyihalash uchun samarali vositaga aylandi. Matematik modellarning dolzarbligi ularning moslashuvchanligi, real jarayonlarga mosligi va zamonaviy shaxsiy kompyuterlar asosida amalga oshirishning arzonligi tufayli doimiy ravishda oshib bormoqda. Foydalanuvchiga, ya'ni kompyuter texnologiyalaridan foydalangan holda tizimlarni modellashtirish bo'yicha mutaxassisga tobora ko'proq imkoniyatlar taqdim etilmoqda. Modellashtirishdan foydalanish, ayniqsa, noto'g'ri qarorlar narxi eng katta bo'lgan avtomatlashtirilgan tizimlarni loyihalashning dastlabki bosqichlarida samarali bo'ladi.

Zamonaviy hisoblash vositalari tizimlarni o'rganishda qo'llaniladigan modellarning murakkabligini sezilarli darajada oshirishga imkon berdi, real tizimlarda yuzaga keladigan omillarning xilma-xilligini hisobga oladigan birlashtirilgan, analitik va simulyatsiya modellarini yaratish mumkin bo'ldi, ya'ni. , o'rganilayotgan hodisalarga ko'proq adekvat bo'lgan modellardan foydalanish.

Adabiyot:

1. Lyashchenko I.N. Chiziqli va chiziqli bo'lmagan dasturlash / I.N.Lyashchenko, E.A.Karagodova, N.V.Chernikova, N.Z.Shor. - K.: “Oliy maktab”, 1975, 372 b.

2. "Kompyuter tizimlari va tarmoqlari" ixtisosligining kunduzgi va sirtqi bo'limlari talabalari uchun "Amaliy matematika" fanidan kurs loyihasini bajarish bo'yicha ko'rsatmalar / Tuzuvchilar: I.A.Balakireva, A.V.Skatkov - Sevastopol: SevNATU Nashriyot uyi, 2003. - 15 p.

3. "Amaliy matematika" fanini o'rganish bo'yicha ko'rsatmalar, "Global qidiruv va bir o'lchovli minimallashtirish usullari" bo'limi / Comp. A.V.Skatkov, I.A.Balakireva, L.A.Litvinova - Sevastopol: SevGTU nashriyoti, 2000. - 31 p.

4. “Kompyuter tizimlari va tarmoqlari” ixtisosligi talabalari uchun “Amaliy matematika” fanini o‘rganish bo‘yicha uslubiy ko‘rsatmalar “To‘liq sonli chiziqli dasturlash masalalarini yechish” bo‘limi kunduzgi va sirtqi ta’lim uchun / Tuzuvchilar: I.A.Balakireva, A.V.Skatkov – Sevastopol. : SevNTU nashriyoti, 2000. - 13 p.

5. Akulich I.L. Misollar va masalalarda matematik dasturlash:

6. Darslik iqtisod talabalari uchun nafaqa. mutaxassis. universitetlar.-M.: Oliy. maktab, 1986.- 319 b., kasal.

7. Andronov S.A. Optimal dizayn usullari: Ma'ruzalar matni / SPbSUAP. Sankt-Peterburg, 2001. 169 b.: kasal.

Shunga o'xshash hujjatlar

Simpleks usuli yordamida chiziqli dasturlash masalalarini yechish algoritmi. Chiziqli dasturlash masalasining matematik modelini qurish. Excelda chiziqli dasturlash masalasini yechish. Foyda va optimal ishlab chiqarish rejasini topish.

kurs ishi, 2012-03-21 qo'shilgan


Grafik muammolarni hal qilish. Matematik modelni tuzish. Maqsad funksiyasining maksimal qiymatini aniqlash. Kanonik chiziqli dasturlash masalasining sun'iy asosi bilan simpleks usulida yechish. Yechimning optimalligini tekshirish.

test, 04/05/2016 qo'shilgan


Chiziqli dasturlashning nazariy asoslari. Chiziqli dasturlash masalalari, yechish usullari. Optimal yechimni tahlil qilish. Bir indeksli chiziqli dasturlash masalasini yechish. Muammoning bayoni va ma'lumotlarni kiritish. Modelni qurish va yechish bosqichlari.

kurs ishi, 2008-yil 12-09-da qo‘shilgan


Matematik modelni qurish. Simpleks jadvalidan foydalanib, to'g'ridan-to'g'ri chiziqli dasturlash masalasini simpleks usuli yordamida echish usulini tanlash, asoslash va tavsiflash. Ikkilamchi masalani shakllantirish va yechish. Modelning sezgirligini tahlil qilish.

kurs ishi, 31.10.2014 qo'shilgan


Korxona uchun maksimal foyda olish uchun matematik modelni qurish, masalani grafik hal qilish. SOLVER plaginidan foydalanib muammoni hal qilish. Resurs zahiralaridagi o'zgarishlarni tahlil qilish. Maqsad funksiyasi koeffitsientlarini o'zgartirish chegaralarini aniqlash.

kurs ishi, 12/17/2014 qo'shilgan


Matematik dasturlash. Chiziqli dasturlash. Chiziqli dasturlash masalalari. Chiziqli dasturlash masalalarini echishning grafik usuli. Chiziqli dasturlash masalasini iqtisodiy shakllantirish. Matematik modelni qurish.

kurs ishi, 2008 yil 13-10-da qo'shilgan


Chiziqli dasturlash masalasini grafik usulda yechish, uni MS Excelda tekshirish. Dasturdagi masalani yechishning ichki tuzilishini tahlil qilish. Ishlab chiqarish rejasini optimallashtirish. Simpleks usuli yordamida masalani yechish. Ko'p kanalli navbat tizimi.

test, 2012-05-02 qo'shilgan


Simpleks usuli yordamida chiziqli dasturlash masalasini yechish: masalani bayon qilish, iqtisodiy-matematik modelni qurish. Potensial usul yordamida transport masalasini hal qilish: dastlabki ma'lumot rejasini tuzish, uning optimal qiymatini aniqlash.

test, 04/11/2012 qo'shilgan


Nochiziqli dasturlash muammosining bayoni. Statsionar nuqtalarni va ularning turini aniqlash. Darajali chiziqlarni qurish, maqsad funksiyaning uch o'lchovli grafigi va cheklovlar. Masalaning grafik va analitik yechimi. Foydalanuvchi qo'llanmasi va algoritm diagrammasi.

kurs ishi, 12/17/2012 qo'shilgan


Chiziqli dasturlash masalasining yechimini tahlil qilish. Simpleks jadvallar yordamida Simpleks usuli. LP masalalarini kompyuterda modellashtirish va yechish. Muammoning optimal yechimining iqtisodiy talqini. Transport masalasini matematik shakllantirish.