Оңтайландыру есебінің айқын математикалық өрнегінің өңделіп, жетілдіруі

Тіке симплекс Қос мағыналы есеп

Тіке есепті қарастырсақ, мұнда z – мақсатты функция транспорт шығындарының минималдауын көрсетеді. (2)-шектеулер жабдықтаушы- заводтың (жіберу пункттерінің) өндіріс қуаттарының шектілігін ескереді. (3)-шектеулер тұтынушылардың (қабылдау пункттерінің) сұраныстарын толық қамтамасыз етуін көрсетеді.

Ашық транспорт есебін жабық транспорт есебіне келтіруге болады. Ашық транспорт есебін жабық транспорт есебіне келтіру үшін жалған пункттер енгізіледі. Жалған пункттердің тасымалдау құны нольге тең.

Егер , онда келесі жалған пункт енгізіледі:

, тасымалдау құны: С_і, n+1=0.

Келесі жағдайда тасымалдау құны: С_n+1, j=0,

жалған пункт енгізіледі.

Транспорт есебін потенциалдар әдісімен, венгр әдісімен, фогель әдісімен шығаруға болады..

Тіке есеп

Қос мағыналы есеп

Қос мағыналы есеп, тіке есептен келесі ережелермен табылады:

1. тіке есептің шектеу жүйесінің бос мүшелері қос мағыналы есептің мақсатты функциясының коэффиценттері болып саналады. Тіке есептің мақсатты функциясының коэффиценттері қос мағыналы есептің шектеулер жүйесінің бос мүшелері болып саналады.

2. тіке есептің әрбір шектеу теңсіздігіне қос мағыналы есептің қайшы белгімен алынған бос емес айнымалылар сәйкес келеді.

3. тіке есептің әрбір шектеу теңдіктерімен қос мағыналы есептің еркін айнымалылары сәйкес келеді.

4. тіке есептің әрбір еркін емес айнымалыларына қос мағыналы есептің шектеу теңсіздіктері сәйкес келеді(теңсіздік өз белгісі бойынша).

5. тіке есептің әрбір еркін айнымалыларына қос мағыналы есептің шектеу теңдіктері сәйкес келеді.

6. тіке есептің мақсатты функциясының максимальдануы қос мағыналы есептің мақсатты функциясының минимальдануы мен ауыстырылады.

7. тіке есептің шектеулерінің коэффиценттер матрицасын келтірген кезде пайда болатын матрицасы қос мағыналы есептің матрица коэффиценттері болып қызмет атқарады.

Қос мағыналықтың негізгі 1-теоремасы:

Қос мағыналы есептің жұбын қарастырайық. Егер олардың ішінде бір есептің оптималды шешімі болса, онда екінші есептің де оптималды шешімі болады. Және де, мақсаттық функциялардың экстрималды шешімдері тең болады.

басқа шешімдер үшін ). Егер осы есептердің біреуінің мақсатты функциясы шектелмесе, онда оған қос мағыналы есеп қарама-қайшы болады. Ең соңында, егер осы есептердің біреуі қарама-қайшы болса, онда оған қос мағыналы есептің мақсатты функциясы шексіз болады. Немесе олда қарама-қайшы болады.

Қос мағыналықтың екінші теоремасы:

Жұп қос мағыналы есептердің тіректі шешімдері

оптималды болу үшін бұл шешімдердің (қатаң еместікі толтыратын шарттар) деп аталатын шарттарды қанағаттандыратыны қажетті де жеткілікті:

Бойынша айтқанда, бір есептің кез-келген айнымалысын шешімнің (мағынасының) оған қос мағыналы есептің сәйкес шектеуінің оң жақ және сол жағынан айырмасына көбейтіндісі нөлге тең болу керек.