Chiziqli dasturlash masalalarini yechishning simplek usuli

BO‘	1	-x1	-x2	. . .	-yr	. . .
-xn
y1	b’10	b’11	b’12	. . .	b’1s	. . .	b’1n
y2	b’20	b’21	b’22	. . .	b’2s	. . .	b’2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
xs	b’r0	b’r1	b’r2	. . .	b’rs	. . .	b’rn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	b'm0	b’m1	b’m2	. . .	b’ms	. . .	b’mn
Z	b’00	b’01	b’02	. . .	b’0s	. . .	b’0n

4.Yangi topilgan simpleks jadvalda tayanch plan mavjud bo‘lsa ikkinchi bosqichga, ya’ni optimal planni topishga o‘tiladi, aks holda yuqoridagi protsess yangi jadval uchun toki tayanch plan topilguncha qayta takrorlanadi.

4. Masalaning optimal planni topish

Agar 1 bosqichdan olingan tayanch planning simpleks jadvaldagi Z-satr elementlari (ozod hadi b´00 dan tashqari) hammasi musbat bo‘lsa, bu olingan boshlang‘ich tayanch plan yagona va u masalaning optimal plani (yechimi) bo‘ladi. Agar Z satrdagi hamma musbat elementlaridan kamida bittasi nulga tengi bo‘lsa, u holda masalaning cheksiz ko‘p optimal plani mavjud bo‘ladi. Agar Z satrdagi elementlardan hech bo‘lmaganda bittasi manfiy bo‘lsa, optimal plan quyidagi algoritim bo‘yicha topiladi:
1. Hal qiluvchi elementni topish.
1.1.Hal qiluvchi ustun topiladi. Z-qatordagi manfiy elementlarning modul bo‘yicha eng kattasi (bitta bo‘lsa o‘zi) tanlanadi. Shu element turgan ustun hal qiluvchi ustun bo‘ladi.
1.2.Hal qiluvchi satr topiladi. Ozod hadlar elementlari hal qiluvchi ustun elementlariga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi olinadi, ya’ni birinchi bosqichning 1.2 punktidagi kabi. Bu songa mos keluvchi ustundagi element hal qiluvchi element va shu element turgan satr esa hal qiluvchi satr bo‘ladi.
2.Hal qiluvchi satr va ustun o‘zgaruvchilari o‘z joylarini almashtiradi (agarda hali ular almashtirilmagan bo‘lsa).
3.Jadvalda simpleks almashtirish bajariladi. Simpleks almashtirish 1- bosqichdagi 3.1, 3.2, 3.3, 3.4 punktlar kabi bajariladi.
4.Yangi topilgan jadvalning Z satri qaraladi. Agar Z qatordagi hamma elementlar musbat bo‘lsa, olingan oxirgi plan masalaning optimal plani bo‘ladi. Aks holda yuqoridagi 1,2,3 punktlar yana takrorlanadi, toki optimal plan topilguncha.
Izoh: Chiziqli dasturlash masalasida, agar maqsad funksiyasining minumimi izlansa yuqoridagi 1-chi bosqich to‘lig‘icha o‘rinli bo‘lib, 2-bosqichda esa faqat Z qator elementlari manfiy holatga keltirilishi kerak, ya’ni teskari holat bo‘ladi