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

1 - расм
Ечимлар соҳасига тегишли 12 та ўзгарувчилар координаталарининг шартли бутун сонли бўлиши расмдан кўриниб турибди. Берилган масалада оптималь ечимни аниқлайдиган нуқтани топиш учун, ОАВС кўпбурчакни, нуқталарининг координаталари бутун сонли бўлган OKEMRNF кўпбурчак билан алмаштирамиз (18.1 расм).
Нормал векторни қурамиз. Соҳалар чизиғини вектор йўналиши бўйича суриб, нуқтани аниқлаймиз. Бу нуқтада мақсад функция максимал қийматга эришади
ед.
Демак, ташкилот 1 –тур ускунадан бир комплект, 2 –тур ускунадан эса уч комплектини сотиб олса, ишлаб чиқариш майдонидан оптималь фойдаланиб, ишлаб чиқарилган маҳсулот максималлигини таъминлаган ҳолда, бир сменада 14 бирликка тенг маҳсулот ишлаб чиқаради.
Гомори усули. Бу усул, симплекс усулига ва кесувчи текисликлар усулига асосланган бўлиб, у Гомори томонидан тузилган алгоритм асосида аниқланади. Аввало симплекс усул билан бутун сонли чизиқли программалаштириш масаласининг оптимал ечими аниқланади. Агар ҳосил бўлган ечим бутун бўлса, масаланинг оптимал ечими аниқланган бўлади. Агар топилган ечимлардан ҳеч бўлмаганда биттаси бутун сонли бўлмаса, у ҳолда масала шартига қўшимча чекловлар киритилади. Бунга кўра, мумкин бўлган ечимлар соҳасидан, бутун бўлмаган ечим кесиб олинади ва бутун координатали бирорта ҳам нуқта ажратиб ташланмайди. Яна симплекс усул билан кенгайтирилган масаланинг таянч ва оптимал ечими аниқланади. Агар янги ечим бутун сонли бўлмаса, у ҳолда масала шартига яна битта қўшимча чеклов киритилади. Қўшимча чекловлар киритиш ва масала ечимини топишда симплекс усулни қўллаш жараёни, оптимал мусбат бутун сонли ечим топилгунча, ёки унинг мавжуд эмаслиги аниқлангунча давом эттирилади.
Мисол. Юқорида келтирилган масала, Гомори усули билан ечилсин. Масаланинг математик модели:

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

Ечиш. Масалани симплекс усул билан ечиш қуйидаги жадвалда келтирилган

БП	С	В	2	4	0	0
	0 0	19/3 10	2 1	1 (3)	1 0	0 1
		0	-2	-4	0	0
	0 4	3 10/3	(5/3) 1/3	0 1	1 0	-1/3 1/3
		40/3	-2/3	0	0	4/3
	2 4	9/5 41/15	1 0	0 1	3/5 -1/5	-1/5 2/5
		218/15	0	0	2/5	7/5

Симплекс жадвалдан кўринадики .

9/5 и 41/15 сонларнинг каср қисми аниқланади (3 қадамдаги 1- ва и 2- сатрлар):

3 қадамдаги 1- сатр учун қўшимча кесувчи тенглама тузамиз:
ёки .
Кейинги ҳисоблашлар қуйидаги жадвалда келтирилган

БП	С	В	2	4	0	0	0
	2 4	9/5 41/15	1 0	0 1	3/5 -1/5	-1/5 2/5	0 0
		218/15	0	0	2/5	7/5	0
	0	-4/5	0	0	(-3/5)	1/5	1
	2 4 0	1 3 4/3	1 0 0	0 1 0	0 0 1	0 1/3 -1/3	1 -1/3 -5/3
		14	0	0	0	4/3	2/3

Бу жадвалдан кўринадики .