Algoritmlarni loyihalash fanidan mustaqil ishi

4.Chiziqli dasturlash masalasini yechishning simpleks usuli.
Simpleks usuli - optimallashtirish muammosining optimal yechimini topish vositasi sifatida bo'sh o'zgaruvchilar, jadvallar va pivot o'zgaruvchilardan foydalangan holda chiziqli dasturlash modellarini qo'lda yechishga yondashuv. Chiziqli dastur - chiziqli cheklovlar bilan maksimal yoki minimal tenglama berilgan holda eng yaxshi natijaga erishish usuli. Ko'pgina chiziqli dasturlarni MatLab kabi onlayn hal qiluvchi yordamida yechish mumkin, ammo Simpleks usuli chiziqli dasturlarni qo'lda yechish usulidir. Simpleks usuli yordamida chiziqli dasturlash modelini yechish uchun quyidagi bosqichlarni bajarish kerak:
●Standart shakl
●Slack o'zgaruvchilarni kiritish
● Jadvalni yaratish
●Pivot o‘zgaruvchilari
●Yangi jadval yaratish
●Optimallikni tekshirish
●Optimal qiymatlarni aniqlang
Ushbu hujjat Simpleks usulini yuqoridagi bosqichlarga ajratadi va optimal yechimni topish uchun butun hujjat davomida quyida ko'rsatilgan chiziqli dasturlash modeliga amal qiladi.

1-qadam: Standart shakl
Standart shakl optimal yechimni yechishdan oldin barcha chiziqli dasturlar uchun asosiy formatdir va uchta talabga ega: (1) maksimallashtirish muammosi bo'lishi kerak, (2) barcha chiziqli cheklovlar tengsizlikdan kichik yoki teng bo'lishi kerak. , (3) barcha o'zgaruvchilar salbiy emas. Ushbu talablarni har doim asosiy algebra va almashtirish yordamida har qanday chiziqli dasturni o'zgartirish orqali qondirish mumkin. Standart shakl zarur, chunki u Simpleks usulini va optimallashtirish muammolarini hal qilishning boshqa usullarini iloji boricha samarali hal qilish uchun ideal boshlang'ich nuqtani yaratadi.
Minimallashtirish chiziqli dastur modelini maksimallashtirish chiziqli dastur modeliga aylantirish uchun maqsad funktsiyasining chap va o'ng tomonlarini -1 ga ko'paytirish kifoya.

Chiziqli cheklovlarni katta yoki teng tengsizlikdan kichik yoki teng tengsizlikka o'tkazish, xuddi maqsad funktsiyasiga nisbatan qilingan kabi amalga oshirilishi mumkin. Ikkala tomonda -1 ga ko'paytirilsa, tengsizlikni kamroq yoki tengga o'zgartirish mumkin.

Model standart shaklda bo'lgandan so'ng, Simplex usulining 2-bosqichida ko'rsatilganidek, bo'sh o'zgaruvchilar qo'shilishi mumkin.
2-qadam: Slack o'zgaruvchilarni aniqlang
Bo'sh o'zgaruvchilar qo'shimcha o'zgaruvchilar bo'lib, ularni tengsizlik cheklovlaridan tenglik cheklovlariga aylantirish uchun chiziqli dasturning chiziqli cheklovlariga kiritiladi. Agar model standart shaklda bo'lsa, bo'sh o'zgaruvchilar har doim +1 koeffitsientiga ega bo'ladi. Cheklovlarda ularni bitta aniq javob bilan echiladigan tengliklarga aylantirish uchun bo'sh o'zgaruvchilar kerak bo'ladi.

Bo'sh o'zgaruvchilar kiritilgandan so'ng, jadval 3-bosqichda tavsiflanganidek, optimallikni tekshirish uchun o'rnatilishi mumkin.
3-qadam: Jadvalni o'rnatish
Simplex jadvali chiziqli dasturlash modelida qator operatsiyalarini bajarish, shuningdek, yechimning optimalligini tekshirish uchun ishlatiladi. Jadval chiziqli cheklovchi o'zgaruvchilarga mos keladigan koeffitsientdan va maqsad funktsiyasi koeffitsientlaridan iborat. Quyidagi jadvalda jadvalning qalin chizilgan yuqori qatori har bir ustun nimani anglatishini bildiradi. Quyidagi ikki qator chiziqli dasturlash modelidan chiziqli cheklash o‘zgaruvchan koeffitsientlarini, oxirgi qator esa maqsad funksiyasi o‘zgaruvchan koeffitsientlarini ifodalaydi.

Jadval to'ldirilgandan so'ng, 4-bosqichda ko'rsatilganidek, modelni optimal yechim uchun tekshirish mumkin.
4-qadam: Optimallikni tekshiring
Maksimallashtirish chiziqli dasturlash modelining optimal yechimi eng katta zeta qiymatini berish uchun maqsad funktsiyasidagi o'zgaruvchilarga tayinlangan qiymatlardir. Optimal yechim butun model grafigining burchak nuqtalarida mavjud bo'ladi. Jadval yordamida optimallikni tekshirish uchun oxirgi qatordagi barcha qiymatlar noldan katta yoki teng qiymatlarni o'z ichiga olishi kerak. Agar qiymat noldan kichik bo'lsa, bu o'zgaruvchining optimal qiymatiga erishmaganligini anglatadi. Oldingi jadvalda ko'rinib turganidek, pastki qatorda uchta salbiy qiymat mavjud bo'lib, bu yechim maqbul emasligini ko'rsatadi. Agar jadval optimal bo'lmasa, keyingi qadam 5-bosqichda ta'riflanganidek, yangi jadvalga asoslanish uchun asosiy o'zgaruvchini aniqlashdir.
5-qadam: Pivot o'zgaruvchisini aniqlang
Pivot o'zgaruvchisi qator operatsiyalarida qaysi o'zgaruvchi birlik qiymatiga aylanishini aniqlash uchun ishlatiladi va birlik qiymatini konvertatsiya qilishda asosiy omil hisoblanadi. Pivot o'zgaruvchisini jadvalning pastki qatoriga va indikatorga qarab aniqlash mumkin. Yechim maqbul emas deb hisoblasak, pastki qatordagi eng kichik salbiy qiymatni tanlang. Ushbu qiymat ustunida joylashgan qiymatlardan biri pivot o'zgaruvchisi bo'ladi. Ko'rsatkichni topish uchun chiziqli cheklovlarning beta qiymatlarini mumkin bo'lgan pivot o'zgaruvchisini o'z ichiga olgan ustundan mos qiymatlarga bo'ling. Qatorning eng kichik manfiy bo'lmagan ko'rsatkichi va pastki qatordagi eng kichik salbiy qiymati bilan kesishishi pivot o'zgaruvchiga aylanadi.

Quyida ko'rsatilgan misolda -10 oxirgi qatordagi eng kichik salbiy hisoblanadi. Bu pivot o'zgaruvchini o'z ichiga olishi uchun x2 ustunini belgilaydi. Ko'rsatkichni yechish bizga birinchi cheklov uchun qiymatni va ikkinchi cheklov uchun qiymatni beradi. Eng kichik manfiy bo'lmagan ko'rsatkich bo'lganligi sababli, pivot qiymati ikkinchi qatorda bo'ladi va 5 qiymatiga ega bo'ladi.

Endi yangi pivot o'zgaruvchisi aniqlangandan so'ng, o'zgaruvchini optimallashtirish va yangi mumkin bo'lgan optimal yechimni topish uchun 6-bosqichda yangi jadval yaratilishi mumkin.
6-qadam: Yangi jadval yarating
Yangi jadval yangi mumkin bo'lgan optimal yechimni aniqlash uchun ishlatiladi. Endi pivot o'zgaruvchisi 5-bosqichda aniqlangandan so'ng, jadvalning qolgan qismini ekvivalentini saqlab qolgan holda pivot o'zgaruvchini optimallashtirish uchun qator operatsiyalarini bajarish mumkin.

1. 
   Pivot o'zgaruvchini optimallashtirish uchun uni birlik qiymatiga (1 qiymati) aylantirish kerak bo'ladi. Qiymatni o'zgartirish uchun pivot o'zgaruvchisi bo'lgan qatorni pivot qiymatining o'zaro nisbatiga ko'paytiring. Quyidagi misolda pivot o'zgaruvchisi dastlab 5 ga teng, shuning uchun butun qatorni ga ko'paytiring.
   

II.Birlik qiymati aniqlangandan so'ng, birlik qiymatini o'z ichiga olgan ustundagi boshqa qiymatlar nolga aylanadi. Buning sababi, ikkinchi cheklovdagi x2 optimallashtirilmoqda, bu boshqa tenglamalarda x2 nolga teng bo'lishini talab qiladi.

2. 
   Jadval ekvivalentini saqlab qolish uchun pivot ustunida yoki pivot qatorida mavjud bo'lmagan boshqa o'zgaruvchilar yangi pivot qiymatlari yordamida hisoblanishi kerak. Har bir yangi qiymat uchun eski pivot ustunidagi qiymatning manfiyini hisoblanayotgan qiymatga mos keladigan yangi pivot qatoridagi qiymatga ko'paytiring. Keyin yangi jadval uchun yangi qiymat yaratish uchun buni eski jadvaldagi eski qiymatga qo'shing. Ushbu bosqichni keyingi sahifadagi tenglamaga qisqartirish mumkin:
   

Jadvalning yangi qiymati = (eski jadvalning umumiy ustunidagi manfiy qiymat) x (yangi jadval qatoridagi qiymat) + (Eski jadval qiymati)

Ushbu tushunchani biroz yaxshiroq tushuntirishga yordam beradigan raqamli misollar quyida keltirilgan.

7-qadam: Optimallikni tekshiring
4-bosqichda tushuntirilganidek, maksimallashtirish chiziqli dasturlash modelining optimal yechimi eng katta zeta qiymatini berish uchun maqsad funksiyasidagi o‘zgaruvchilarga berilgan qiymatlardir. Har bir yangi jadvaldan so'ng, yangi pivot o'zgaruvchini aniqlash kerakligini ko'rish uchun optimallikni tekshirish kerak bo'ladi. Pastki qatordagi barcha qiymatlar noldan katta yoki teng bo'lsa, yechim optimal hisoblanadi. Agar barcha qiymatlar noldan katta yoki teng bo'lsa, yechim optimal deb hisoblanadi va 8 dan 11 gacha bo'lgan bosqichlarni e'tiborsiz qoldirish mumkin. Agar salbiy qiymatlar mavjud bo'lsa, yechim hali ham optimal emas va 8-bosqichda ko'rsatilgan yangi aylanish nuqtasini aniqlash kerak bo'ladi.
8-qadam: Yangi Pivot o'zgaruvchisini aniqlang
Agar yechim optimal emas deb aniqlangan bo'lsa, yangi pivot o'zgaruvchisini aniqlash kerak bo'ladi. Pivot o'zgaruvchisi 5-bosqichda kiritilgan va qaysi o'zgaruvchi birlik qiymatiga aylanishini aniqlash uchun qator operatsiyalarida qo'llaniladi va birlik qiymatini konvertatsiya qilishda asosiy omil hisoblanadi. Pivot o'zgaruvchisi eng kichik manfiy bo'lmagan ko'rsatkich va pastki qatordagi eng kichik salbiy qiymat bilan qatorning kesishishi bilan aniqlanishi mumkin.

9-qadam: Yangi jadval yarating
Yangi pivot o'zgaruvchisi aniqlangandan so'ng, yangi jadval yaratish kerak bo'ladi. 6-bosqichda kiritilgan jadval jadvalning qolgan qismi ekvivalentini saqlab qolgan holda pivot o'zgaruvchisini optimallashtirish uchun ishlatiladi.

1. 
   O'zgaruvchi o'zgaruvchini o'z ichiga olgan qatorni aylanma qiymatining o'zaro nisbatiga ko'paytirish orqali 1-o'zgaruvchini hosil qiling. Quyidagi jadvalda pivot qiymati bo'lgan, shuning uchun hamma narsa 5 ga ko'paytiriladi.
   

2. 
   Keyin, pivot o'zgaruvchisi ustunidagi boshqa qiymatlarni nolga tenglashtiring. Bu pivot ustunidagi eski qiymatning manfiyini olish va uni pivot qatoridagi yangi qiymatga ko'paytirish orqali amalga oshiriladi. Keyin bu qiymat almashtirilayotgan eski qiymatga qo'shiladi.
   

10-qadam: Optimallikni tekshiring
Yangi jadvaldan foydalanib, optimallikni tekshiring. 4-bosqichda tushuntirilganidek, pastki qatordagi barcha qiymatlar noldan katta yoki teng bo'lganda optimal yechim paydo bo'ladi. Agar barcha qiymatlar noldan katta yoki teng bo'lsa, optimallikka erishilgani uchun 12-bosqichga o'ting. Agar salbiy qiymatlar hali ham mavjud bo'lsa, optimal yechim olinmaguncha 8 va 9-bosqichlarni takrorlang.
11-qadam: Optimal qiymatlarni aniqlang
Jadvalning optimalligi isbotlanganidan keyin optimal qiymatlarni aniqlash mumkin. Bularni asosiy va asosiy bo'lmagan o'zgaruvchilarni farqlash orqali topish mumkin. Asosiy o'zgaruvchini uning ustunida bitta 1 qiymatga ega bo'lish uchun tasniflash mumkin, qolganlari esa nolga teng. Agar o'zgaruvchi ushbu mezonlarga javob bermasa, u asosiy bo'lmagan hisoblanadi. Agar o'zgaruvchi asosiy bo'lmasa, bu o'zgaruvchining optimal yechimi nolga teng ekanligini bildiradi. Agar o'zgaruvchi asosiy bo'lsa, 1 qiymatini o'z ichiga olgan qator beta qiymatiga mos keladi. Beta qiymati berilgan o'zgaruvchi uchun optimal yechimni ifodalaydi.
Asosiy o'zgaruvchilar: x1, s1, z
Asosiy bo'lmagan o'zgaruvchilar: x2, x3, s2
x1 o'zgaruvchisi uchun 1 ikkinchi qatorda topiladi. Bu shuni ko'rsatadiki, optimal x1 qiymati beta qiymatlarning ikkinchi qatorida topilgan, bu 8 ga teng.
s1 o'zgaruvchisi birinchi qatorda 1 qiymatiga ega bo'lib, beta ustunidan optimal qiymat 2 bo'lishini ko'rsatadi. s1 bo'sh o'zgaruvchi bo'lganligi sababli, u aslida optimal yechimga kiritilmaydi, chunki o'zgaruvchi maqsad funktsiyasida mavjud emas.
Zeta o'zgaruvchisi oxirgi qatorda 1 ga ega. Bu maksimal maqsad qiymati beta ustunidan 64 bo'lishini ko'rsatadi.
Yakuniy yechim quyidagi qiymatlarga ega bo'lgan har bir o'zgaruvchini ko'rsatadi:
x1 = 8 s1 = 2
x2 = 0 s2 = 0
x3 = 0 z = 64
Maksimal optimal qiymat 64 ga teng va maqsad funktsiyasining (8, 0, 0) da topiladi.
#include
#include
#include
using namespace std;
#define ND 2
#define NS 2
#define N (ND+NS)
#define N1 (NS*(N+1))

void init(float x[],int n)

{
int i;

for(i=0;i
x[i]=0;
}

int main()

{
int i,j,k,ki,kj,bas[NS];
float a[NS][N+1],c[N],cb[NS],th[NS];
float x[ND],cj,z,t,b,min,max;

init(c,N);

init(cb,NS);
init(th,NS);
init(x,ND);

for(i=0;i
init(a[i],N+1);

for(i=0;i
a[i][i+ND]=1.0;

for(i=0;i
bas[i]=ND+i;

cout<<"Enter the constraints"<
for(i=0;i{
for(j=0;jcin>>a[i][j];
cin>>a[i][N];
}

cout<<"Enter the objective function"<
for(j=0;jcin>>c[j];
cout<while(1)
{

max=0;
kj=0;

for(j=0;j
{
z=0;
for(i=0;iz += cb[i]*a[i][j];
cj=c[j]-z;
if(cj>max)
{
max=cj;
kj=j;
}
}

if(max <= 0)

break;

max=0;

for(i=0;iif(a[i][kj] != 0)
{
th[i]=a[i][N]/a[i][kj];
if(th[i]>max)
max=th[i];
}

if(max <= 0)

{
cout<<"Unbonded solution";
return 1;
}

min=max;
ki=0;

for(i=0;iif((th[i] < min) && (th[i] != 0))
{
min=th[i];
ki=i;
}

t=a[ki][kj];

for(j=0;ja[ki][j] /= t;

for(i=0;i
if(i != ki)
{
b=a[i][kj];
for(k=0;ka[i][k] -= a[ki][k]*b;
}
cb[ki]=c[kj];
bas[ki]=kj;
}

for(i=0;i
if((bas[i] >= 0) && (bas[i]x[bas[i]]=a[i][N];

z=0;

for(i=0;iz += c[i]*x[i];

for(i=0;i
cout<<"x["<cout<cout<<"Optimal value="<cout<
return 0;
}