Чизиқли программалаштириш масаласи. Чизиқли программалаштириш масаласини ечиш усуллари. Чизиқли программалаштиришда иккиланма назария

Симплекс усул алгоритми
1. Масаланинг математик модели каноник кўринишда бўлиши керак. Агар у каноник шаклда бўлмаса, каноник шаклга келтириш зарур.
2. Симплекс жадвал тўлдирилади. Биринчи қадамда жадвалнинг оптималлик критерияси бўлган индекс сатрдан бошқа, барча сатрларини, чегаравий шартлардан ва мақсад функциядан фойдаланиб тўлдирамиз. Бошланғич таянч ечимни аниқлаймиз.
3. Топилган бошланғич таянч ечимни оптималлигини текширамиз. Индекс сатр номаълумлари формула билан топилиб, озод ҳадлар учун эса формула билан аниқланади.
Максимум масала ечилаётганда қуйидаги ҳоллар бўлади:
- барча оптималлик критериялари учун шарт бажарилади, у ҳолда топилган ечим оптимал бўлади;
- ҳеч бўлмаганда битта оптималлик критерияси учун шарт бажарилади, лекин бу ўзгарувчи учун бирорта ҳам мусбат коэффициент мавжуд эмас, у ҳолда масала ечиш тўхтатилади, чунки , яъни мақсад функция мумкин бўлган ечимлар соҳасида чегараланмаган;
- ҳеч бўлмаганда битта оптималлик критерияси манфий бўлиб, бунга мос ўзгарувчида ҳеч бўлмаганда битта мусбат коэффициент мавжуд бўлса, у ҳолда, мақсад функция қиймати катта бўлган бошқа таянч ечимга ўтилади;
- индекс сатрда манфий бўлган оптималлик критериялари бир нечта бўлса, у ҳолда базис номаълумга, манфий баҳоларнингорасидан, абсолют қиймати бўйича энг катта бўлган ўзгарувчи киритилади.
Айтайлик битта баҳо , ёки абсолют қиймати бўйича энг катта бўлган учун, k – сатрни танлаймиз. Бундан фойдаланиб, озод ҳадларни k – сатрнинг мусбат элементларига бўлгандан сўнг, энг кичик нисбатдан, аниқловчи элемент топилади.
4. Симплекс жадвалнинг иккинчи қадами аниқланади:
- аниқловчи турган сатр элементлари, аниқловчи элементга бўлиниб янги жадвалга ёзилади;
- базис номаълум тўлдирилади;
- жадвалнинг бошқа коэффициентлари ҳам шу каби топилади. Янги таянч ечим аниқланади.
5. Алгоритмнинг биринчи қадамига қайтилади.
Мисол. Чизиқли программалаштириш масаласини симплекс усул билан ечинг.


Ечиш. Берилган масалани каноник шаклга келтирамиз



чегаравий шартларда

Симплекс жадвални тузамиз.

БН	C	B	-1	3	2	0	0	0
	0 0 0	5 3 5	-1 (2) 2	-1 -3 -5	-2 1 6	1 0 0	0 1 0	0 0 1
		0	1	-3	-2	0	0	0
	0 -1 0	13/2 3/2 2	0 1 0	-5/2 -3/2 -2	-3/2 ½ 5	1 0 0	½ ½ -1	0 0 1
		-3/2	0	-3/2	-5/2	0	-1/2	0

.
Симплекс жадвалдан фойдаланиб масаланинг оптимал ечимини аниқлаймиз .