Методы оптимизации

ТАСЫМАЛ ЕСЕБІ  ПОТЕНЦИАЛДАР ӘДІСІ

Есептің қойылымы, негізгі анықтамалар •Тасымал есебінің мақсаты  ­ тауарларды тасымалдаудың  тиімді жолдары мен  тәсілдерін құру, аса ұзақ,  қарсы және қайталанатын  тасымалдарды жою

Есептің қойылымы, негізгі анықтамалар •Практикада тасымал есебінің негізгі 3  қойылымы кездеседі: 1.Тасымал шығынын минимумдауды   қамтамасыз ететін  тасымал құралдарының  тиімді құрылымын табу қажет. • Экономикалық және пайдаланушылық көрсеткіштері  тасымал құрамынан тәуелді болады.

Есептің қойылымы, негізгі анықтамалар Практикада тасымал есебінің негізгі 3  қойылымы кездеседі: 2. Шаруашылықтағы барлық  жүктерді  тасымалдау шығыны минималды болатындай  етіп транспорт түрлерінің  арасында жүктерді  үлестіріп орнату қажет  Біртекті жұмысты атқару үшін транспорттың  әр түрін қолдану тиімділігі барлық уақытта  бірей бола бермейді

Есептің қойылымы, негізгі анықтамалар Практикада тасымал есебінің негізгі 3  қойылымы кездеседі: 3. Тұтынушыларды жеткізушілерге бекіту  есебі Жүкті өндіруші пункттен қолданушы  пунктке дейінгі біртекті жүктерді экономды  тасымалдау жоспары

Тасымалдаудың ақшалай­ материалдық минималды шығыны  1 Тасымалдауды ң минималды  шығыны  4 Транспор т есебінің  тиімділік  критериі 2 3 Тасымалдауғ а кететін  минималды  уақыт  шығыны  Тасымалдау жұмыстарының  минималды көлемі

Өнімді шығарушы m  пункттен біртекті өнім  саны сәйкесінше  қолданушы n пунктке  жеткізу қажет  Өнім бірлігін і­ші  тасымалдаушы пункттен  j­ші қолданушы пунктке  тасымалдау бағасы cij –ге  тең және әрбір маршрут  үшін белгілі   Xij ­ і­ ші тасымалдау  пункттен  j­ ші  қолданушы пунктке  тасымалданатын  өнімнің саны Есептің  мазмұнды  қойылымы

Тасымалдау есебінің математикалық  қойылымы Белгілеулер: m – жеткізуші пункт саны; і – жеткізуші нөмірі; n – қолданушылар пунктінің саны; j – қолданушының нөмірі; ai – і­ ші тасымалдаушының біртекті жүк көлемі; bi ­ j­ші қолданушының біртекті жүк көлемі; cij ­  тасымалданатын жүк бірлігінің бағасы  xij, ­ жүк саны C – тасымалдауға кететін жалпы шығын

Потенциалдар әдісі – жүк тасымалының негізгі  жоспарын тиімділікке дейін тізбектей жақсарту процессі

Егер тасымалдау есебінің кейбір жоспары үшін тасымалдаушының потенциалы деп аталатын ui жүйеcін және қолданушының потенциалы деп аталатын vj      жүйеcін  m+n санынан жинақтауға  болатын болса, және ол төмендегі шартты қаңағаттандырса,  Теорема: vj ­ ui = cij, егер xij > 0  vj ­ ui ≤ cij, егер  xij = 0, онда тасымалдау жоспары тиімді жоспар болып табылады.

Өрнектің экономикалық мағынасы vj ­ ui = cij, егер xij > 0 Тасымалдау жоспарланған  тасымалдаушылар мен  қолданушылар үшін потенциалдар  айырымы жүк бірлігінің  тасымалдану шығынына сәйкес  келеді

Өрнектің экономикалық мағынасы vj ­ ui ≤ cij, егер  xij = 0  Тасымалдау жоспарланбаған  қолданушылар  мен  тасымалдаушылардың  өзге  жұптары үшін потенциалдар  айырымы тасымалдау шығынынан  аспайды

Егер тасымалдау жоспары  тиімді болса, онда тасымалдау  Потенциалдар дың  экономикалық  мағынасы пінкті мен қолданушы  пунктіндегі жүктерге  потенциалдарды  бекітуге  болады

Анықтамалар: 1. Жинақ – тасымалдау тізбегіндегі  клеткалардың кездейсоқ жиынтығы 2. Тізбек – бір қатарда орналасқан әрбір екі  көрші клеткалардың клеткалардың тізбекті  жиыны 3. Цикл – тұйық тізбек, бірінші клеткамен  қатар орналасқан соңғы клетка

1­қадам. Бастапқы тиімді жоспар табылғаннан соң ,  сәйкесінше vj потенциалы қойылады,  әрбір аі – тасымалдаушыға сәйкесінше ui  потенциалы қойылады, ал әрбір bj – қолданушыға  ui және vj сандары келесідей таңдалады : кез  келген клеткада жүктелген потенциалдар  қосындысы осы клеткадағы тасымал бағасына тең  болады  vj + ui = cij

U1=0 деп жорамалдайық

2­қадам. Жоспарды бағалау үшін жанама тарифтер анықталатын бос клеткаларды қарау  қажет.  c’ij = ui + vj

3­қадам. Әрбір бос клетка үшін баға есептеледі –  клетка тарифы мен оның жанама тарифының айырымы Әрбір бос клетка үшін осы бағалау теріс емес  болған жағдайда  жоспар тиімді болады

Алынған тасымалдау жоспары тиімді емес.

4­қадам. Егер кемінде бір теріс баға бар болса, онда  жоспарды жақсарту қажет, яғни жаңа жоспар  құрылады. Бағалауы теріс клетка жүктеледі. Егер  бірнеше теріс бағалау болса, абсолют  шамасы бойынша ең үлкен клетка жүктеледі.

Таңдалған клетка үшін тұйық цикл құрылады, яғни толтырылған клеткаларды  толтырылмаған клетка арқылы өтетіндей тұйық жол құрылады. Әрбір бос клетка үшін тек бір ғана цикл құрылады.

Тұйық цикл клеткаларына + және – тағңбалары қойылады. «­­» таңбасы ең кіші бағалауы бар клеткаға  қойылады, және «++ таңбасы тұрған клеткадағы бағалауға қосылып «­» тұрған бағалаудан алынады.  Нәтижесінде жаңа тасымалдау жоспары құрылады.

Жаңа жоспар құрылады Есептеу жұмысы 1­ қадамнан қайта  басталады.

U1=0 деп жорамалдайық

Алынған жоспар тиімді  емес, бағалаулар арасында  теріс бағалау бар.

Жоспарды жақсартып жаңа жоспар құру  қажет. Бағалауы теріс клеткалар жүктеледі

Жаңа жоспар құрылады

Алынған жоспар тиімді,  бағалаулар арасында теріс  бағалау жоқ.

Жауап: Жүкті тасысалдаудың тиімді жоспары: Жүк тасымалының минималды бағасы: