3. Сызықтық программалау есебін шешудің графикалық әдісі

 

Келесі сызықтық программалау есебі [7-11]

(1.5)

және тек екі белгісізі бар сызықтық алгебралық теңдеулер жүйесі

(1.6)

берілсін. (1.6) жүйенің әрбір теңсіздігі (х1, х2) координат жазықтығында қандайда бір жарты жазықтықты анықтайды. Сондықтан (1.5)-(1.6) есебінің шешімдерінің мүмкін болатын W жиыны, ақырлы жарты жазықтықтардың қиылысуы болып табылады, яғни (х1, х2) жартыжазықтығындағы қандайда бір көпбұрышты облыс. Беріліген есепті графикалық әдіспен шешу үшін, ең алдымен көпбұрышты W облысын салу қажет, содан кейін C=(с1, с2) нормаль векторына перпендикулар F мақсаттық функцияның тіреулік түзуін координаттар басы арқылы өтетіндей етіп жүргізу керек. F түзуі өзіне-өзі паралелль, С векторының бағытымен W облысымен қиылысуы аяқталғанша орын ауыстыра береді (минимумға шешілетін есеп үшін F түзуі қарсы бағытта орын ауыструы қажет). Егер осындай орын ауыстыру кезінде F түзуі барлық уақытта W облысын қиып өтетін болса, онда мақсаттық функция алынған жиында жоғарыдан шенелмеген және (1.5)-(1.6) есептің тиімді шешімі болмайды.

Басқа жағдайда W облысының тіреулік F түзуімен қилысуы нүктесінде одан кейінгі орын ауыстыруларда W облысымен бос қиылысу болатын болса, онда бұл нүктені (1.5)-(1.6) есебінің тиімді шешімдер жиыны болып табылады.

Сонымен (1.5)-(1.6) сызықтық программалау есебін, оның геометриялық интерпретациясына (түсіндіру) сүйене отырып шешу келесі қадамдардан тұрады [10]:

1. (1.6) шектеулер жүйесіндегі теңсіздіктер таңбасын теңдіктер таңбасына ауыстру нәтижесінде пайда болған теңдеулердің түзулерін саламыз.

2. Есептің әрбір шектеулері арқылы анықталатын жарты жазықтықты табамыз.

3. Шешімдер көпбұрышын анықтаймыз және C=(с1, с2) нормаль векторын саламыз.

4. Координатаның бас нүктесі арқылы өтетін F=с1х1 +c2x2 түзуін саламыз және F түзуін C=(с1, с2) векторының бағытымен жылжытамыз. Осының нәтижесінде, мақсаттық функция максимал мәнге ие болатын нүктені немесе мүмкін болатын жоспарлар жиынында мақсаттық функция жоғарыдан шенелмегенің анықтаймыз.

Әрі қарай әрбір кезең бойынша төменде берілген есепті толығырақ қарастырайық [7].

I кезең. Есептің экономикалық қойылымы. Айталық екі типтегі (К1 және К2 типтері) бояу шығаратын химиялық профильдің өндірістік фирмасы бар болсын. Өткізілетін базарда К1 типті бояудың бір килограмы 2 ш.б., ал К2 типті бояудың бір килограмы 3 ш.б. тұратын болсын. Бұл бояуларды өндіру үшін екі түрлі (A және B) шикізат қолданылады. Бір килограмм К1 типті бояу алу үшін А түріндегі шикізаттан екі килограмм және B түріндегі шикізаттан бір килограмм қажет, ал бір килограмм К2 типті бояу алу үшін A түріндегі шикізаттан бір килограмм және B түріндегі шикізаттан екі килограмм қажет. Қойманың қуаты мынадай: A шикізатының тәуліктік қоры 35 килограммнан аспайды, ал В шикізатының тәуліктік қоры 40 килограммнан аспайды. Бұл мәліметтерді келесі кесте түрінде көрсетуге болады:

Кесте 1.3

бояу

шикізат

К1

К2

Қойма

A

2

1

35

B

1

2

40

Бояулардың тәуліктік өндірісі және өтімділік көлемі фирмаға максимальды кіріс әкелетіндей К1 және К2 типті бояулардың тәуліктік өндіріс жоспарын ұйымдастыру қажет.

II кезең. Математикалық моделді құру. Фирма алдына қойылған міндетті ескере отырып, оны келесі модель түрінде тұжырымдауға болады: і0 және і0 айнымалыларын тәуліктік бояу өндірісінің параметрі ретінде енгізіп және кестені ескерсек, онда келесі математикалық модельді жазуға болады:

III кезең. Шешу әдісі. Берілген есепті оның геометриялық интерпретациясын қолдана отырып шешеміз.

1. Шектеулер жүйесіндегі теңсіздіктер таңбасын теңдіктер таңбасына ауыстыру нәтижесінде алынған теңдеулер бойынша түзулерді саламыз:

х1Ох2 жазықтығында I түзуі жүйенің бірінші теңдеуіне, II түзуі -екінші, III түзуі -үшінші, IV түзуі –төртінші теңдеуге сәйкес болатындай етіп түзулерді саламыз. Нәтижесінде 1- суретті аламыз.

2. Алынған жарты жазықтықтардың қилысуы берілген есептің шешімінің көпбұрышын анықтайды. 1-суреттен көрініп тұрғандай, шешімнің көпбұрышы ОАВС төртбұрышы болып табылады.

1-сурет. Графиктік әдістің көрнісі

 

Осы төртбұрышқа кіретін кез келген нүктенің координатасы айнымалының оң болу шартын және берілген жүйедегі теңсіздіктерді қанағаттандырады. Егер біз OABC төртбұрышына кіретін және F функциясына максимум мән беретін нүктені тапсақ қана, есептің шешімі бар болады. Осы нүктені табу үшін С(2;3) векторын және 2x1 +3х2 = h түзуін саламыз. Мұндағы h – 2x1 + 3х2 = h түзуі мен көпбұрыш шешімінің ортақ нүктесі бар болатын қандай да бір тұрақты. Сондықтан h=60 деп алып, 2x1 + 3х2 = 60 түзуін саламыз (1-сурет).

Салынған 2x1 + 3х2 = 60 түзуін С векторының бағытымен жылжыта отырып, оның есептің шешімдер көпбұрышымен соңғы ортақ нүктесі В екенің көру қиын емес. Осы нүктенің координаталары К1 және К2 типті бояуларды өндіруде ең көп пайда әкелетін бояуларды өндіру жоспарын анықтайды.

В нүктесінің координаттарын I және II түзулердің қилысуы нүктесі ретінде анықтаймыз. Демек, оның координаттары осы түзулердің теңдеулерін қанағаттандырады:

Бұл теңдеулер жүйесін шешіп, x1=10, х2=15 мәндерін табамыз, ал мақсаттық функция мәні F = 2∙10 + 3∙15= 65 болады.

Жауабы: max F=65; Xопт=(10, 15).

IV кезең. Алынған тиімді шешімнің экономикалық анализі. Егер фирма К1 типті бояудан 10 килограмм және К2 типті бояудан 15 килограмм өндірсе, онда оларды сату нәтижесінде максимальды пайда, яғни 65 ш.б. табады. Есеп толығымен шешілді.