Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va uning tahlili

Masalaning tayanch yechimini tuzish. Boshlang‘ich tayanch yechimni topish quyidagi algoritm bo‘yicha bajariladi:
1. Simpleks jadvaldan hal qiluvchi elementni topish:
1.1. Hal qiluvchi elementni topish oldin hal qiluvchi ustunni topishdan boshlanadi. Buning uchun ozod hadlar ustuniga qaraladi. Agar ozod hadlar ustunidagi elementlar hammasi musbat bo‘lsa, bu boshlang‘ich yechim tayanch yechim bo‘ladi va ikkinchi bosqichga o‘tiladi.
Agar manfiy element mavjud bo‘lsa ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa shu elementning o‘zi olinadi). Masalan, aytaylik bu element bo‘lsin. Shu element turgan satr qaraladi. Agar satr elementlaridan hammasi musbat bo‘lsa, masalaning yechimi mavjud bo‘lmaydi (bu holda hisoblashlar shu joyda to‘xtatiladi). Agar satrda manfiy element mavjud bo‘lsa, ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa o‘zi olinadi). Shu element turgan ustun hal qiluvchi ustun deyiladi. Misol uchun bu -chi ustun bo‘lsin.
1.2. Hal qiluvchi satr topiladi. Ozod hadlarni hal qiluvchi ustun elementlarga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi tanlanadi, ya’ni

Aytaylik, bu nisbatlar ichida musbatlarning eng kichigi bo‘lsin. U holda shu element turgan satr hal qiluvchi satr deyiladi, elementning o‘zi esa hal qiluvchi element bo‘ladi.
2. Hal qiluvchi ustun va satr o‘zgaruvchilari o‘rinlari almshtiriladi, (ya’ni va o‘rinlari almashtirilib, yangi jadval tuziladi).
3. Jadvalda simpleks almashtirish bajariladi.
3.1. Hal qiluvchi ustun elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya’ni
3.2. Hal qiluvchi satr elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya’ni
3.3. Hal qiluvchi element 1 ga tenglashtirilib o‘ziga bo‘linadi, ya’ni
3.4. Yangi simpleks jadvalning qolgan elementlari quyidagi formula orqali topiladi.

Yangi jadvalda -elementni hisoblashda eski jadvaldan , , , elementlarini topish quyidagicha bo‘ladi:
- elementning eski jadvaldagi unga mos element;
- element turgan satr bilan hal qiluvchi element ustuni kesishmasidagi element;
- element turgan ustun bilan hal qiluvchi element satri kesishmasidagi element;
- hal qiluvchi element.

Bazis o‘zgaruvchilar	1			...		...
				...		...
				...		...
...	...	...	...	...	...	...	...
				...		...
...	...	...	...	...	...	...	...
				...		...
				...		...

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