Гомори алгоритмі

Гомори Алгоритмі екі қадамнан тұрады:

а) алдынғы

б) жалпы

Алдынғы қадам: СБ есебі бүтінсандылық шартысыз жай симплекс әдісімен шешіледі. Егер оптималды шешімдер бүтін санды болса, онда берілген алдынғы қадам есеп шешімі болып табылады. Егер сандар бүтін емес болса, онда жалпы қадамға өтеміз. Жалпы қадам екі бөлімнен тұрады:

1. Есептің бөлшек шешімдерін жоятын, есеп моделіне біз енгізетін қосымша шектеу құрастыру. Бұны геометриялық түрде көрсетейік: Кесіп тастау әдісін қолдансақ онда қосымша шектеулер (жиын артықшылықарын қиятын, яғни біздің алған шешімдер арасында тек бүтін сандар қалу керек)

2. Қосымша шектеуді ескере отырып, өзгермелі есепті шешу. Мұнда 1 және 2 қадамдар біз шешім тапқанша немесе есептің бүтін санды шешімі жоқ екендігіне көз жеткізгенімізше қайталана береді, яғни оптималды шешімін анықтау кезінде симплекс кестедегі бос мүшелер –бөлшек сандар бұл қатардағы коэффициенттер бөлшек емес

2 Жұмысты бекіту туралы есеп

1) n жұмыскер және m жұмыс берілген. Әрбір жүмыскерге 1 жұмысты тағайындап беруіміз керек j жұмысты i қызметкер істесе біз одан s_ij –түсім аламыз. Есебіміздің негізгі мақсаты әрбір жұмыскерге біб-бір жұмысты тағайындаудың арқасында мақсатты функцияны жоғарлату. Есебіміздің шешімінде оптимальды тағайындау анықтау керек (кімге нені береміз)

2) Белгілейік:

s_ij –түсім, егер j жұмысшы i қызметкер істесе.

xij –тағайындау жоспар, егер j жұмысын i қызметкер істесе.

3) Математикалық моделін құру үшін бұл есептің негізгі шарттарынанықтап алу қажет. айнымалы өзгерісті тағайындап аламыз.

1) бірінші шарт.

2) - екінші шарт.

/түсім көп болса- көбейтеміз/.

/шығын болса- азайтамыз/.

4) Бұл сызыкты есеп, соның ішінде бүтін санды есепке жатады.

1) егер n=m — жабық, ал n¹m болса, онда оған жалған жұмысшы немесе жалған жұмыс табамыз.

2) егер n>m болса, онда m+1 жұмыс қосамыз.

- азайтуға шығарсақ,

- көбейтуге шығарсақ.

3) егер n<m болса, онда n+1 жұмыскерді аламыз.

- азайту есебіне - көбейту есебіне.