8-Тақырып. Сызықтық бағдарламалаудың тасымалдау есебі Дәріс жоспары (1 сағат)
Тасымалдау СБ есебін шешу дифференциалдық рента әдісі
жүктеу/скачать 1,09 Mb.
|
‹ҐЄжЁп 8. ЊЏЋђ Є §
- Бұл бет үшін навигация:
- Жөнелту пунктері
- Қажеттіліктер
- Есеп-3.
| 3. Тасымалдау СБ есебін шешу дифференциалдық рента әдісі.
10 «Солтүстік-батыс бұрыш» әдісі Транспорттық есептің тірек жоспарын солтүстік-батыс бұрышы әдісімен табу барысының әр қадамында қалған жүру пунктінін 1-нен және қалған белгілеу пунктінің 1-ін қарастырады. Шарттар кестесінің тор көздерін толтыру белгісіз 1 үшін сол жақ жоғарғы тор көзден басталады, яғни кестені диагоналы бойынша жүргізіліп отырылады. Есеп-2. A1, А2, А3 базаларына сан жағынан 140, 180 және 160 бірлікке тең біртекті жүк келіп түсті. Бір жүкті B1, В2, В3, В4, В5 белгілеу пунктеріне көлемі жағынан 60, 70, 120. 130 және 100 бірліктерін тасымалдау тарифтері әрбір жүру пунктерінен белгілеу пунктеріне сәйкестігі келесі кестеде көрсетілген: 1-кесте
Берілген көліктің тасымалдау жоспары солтүстік-батыс бұрыш әдісімен табу керек. Шешімі. Мұнда жөнелту пунктерінің саны m=3, ал белгілеу пунктерінің саны n=5. Демек, есептің тірек жоспары 5+3-1=7 толтырылған тор көздерде тұрған сандармен анықталады. Кестені толтыруды анықталмағаны х11 үшін тор көзінен бастаймыз, яғни бірінші белгілеу пунктінің қажеттілігін бірінші жөнелту пунктінің есебінен қанағаттандыруға тырысамыз. А1 пунктінің қорлары В1 пунктінің кажеттіліктерінен артық болатындардан, x11=60, бұл мәнді 2 кестедегі сәйкес тор көздерге жазамыз және А1 пунктінің қорларын 80-ге теңестіре отырып, В1 бағанасын қарастырудан уақытша алып тастаймыз. 2-кесте
A1 жүру пунктінен және В1 белгілеу пунктінен қалған алғашқыларын қарастырамыз. A1 пунктінің қорлары В2 пунктінің қажеттілігінен артық. x12=70 дейік, бұл мәнді 2 кестесіндегі сәйкес тор көзге жазамыз және В2 бағанын қарастырудан алып тастаймыз. А1 пунктіндегі қорларды 10 бірлікке тең деп есептейміз. Қайтадан A1 жөнелту пунктінен және В3 белгілеу пунктерінен қалған апғашқыларды қарастырамыз. В3 пунктерінің қажеттілігі A1 пунктінің қалған қорларынан артық. x3=10 дейік, және А1 жолын қарастырудан алып тастаймыз. x13=10 мәнін 2-кестесіндегі сәйкес тор көзге жазамыз және В3 пунктінін қажетгілігін 110 бірлікке тең деп есептейміз. Енді x23 және т.б. белгісіздер үшін тор көздерді толтыруға кірісеміз. 6-қадамнан соң А3 жүру пункті жалғыз өзі 100 бірлік жүк қорымен қалады және В5 белгілеу пунктінің біреуі 100 бірлік қажеттілігімен қалады. Осы жағдайға сәйкес біз толтыратын, яғни х35=100 (2-кестені) деп алынатын тор көзді толтырамыз. Нәтижесінде мынандай тірек жоспарын аламыз: Нақты тасымалдау жоспарына сәйкес, барлық жүктің тасымалдануын жалпы құны S=2*60 + 3*70 + 4*10 + 1*110 + 4*70 + 7*60 + 2*100=1380 құрып отыр. 2о «Кестенің ең кіші» элемент әдісі. Солтүстік-батыс бұрыш әдісінде әрбір қадамында бірінші қалған белгіленген қажеттіліктің пункттер бірінші қалған кету пункттерінің қорлары есебінен қанағаттандырылады. Көріп отырғандай, кету және белгіленген пункттерді таңдау тасымалдау тарифтеріне бағытталса, мақсатты түрде жүреді, оның ішінде: әрбір қадамда минималды тарифке жауап беретін, кез-келген тор көзді таңдау қажет (егер мұндай тор көздер бірнеше болса, онда олардың кез-келгенін таңдау керек), және таңдаған тор көзге сәйкес келетін жөнелту және белгіленген пункттерін қарастыру қажет. Минималды элемент әдісінің манызы, ол тор көздерді таңдауда минималды тарифтерді қоса есептегімен байқалады. Бұл әдісте мынаны ескеру қажет, яғни әдіс жоспар кезінде тасымалдаудың жалпы құнына қарағанда жүкті тасымалдаудың жалпы құны аз кезінде көліктік тапсырманың тірек жоспарын табуға мүмкіндік береді. Сондықтан көліктік тапсырманың тірек жоспары неғұрлым мақсатты түрде минималды элемент әдісімен шешіледі. Есеп-3. Көліктік тапсырманың алғашқы тірек жоспарын минималды элемент әдісімен табу керек. Шешімі. Алынған тапсырмаларды 3-кестесі түрінде жазамыз. 3-кесте
Минималды тариф 1-ге тең, айнымалы x13 тор көзінде берілген. х13=160 десек, бұл мәнді 3-кестесіндегі сәйкес тор көзге жазамыз және А1 жолынан қарастыруға уақытша алып тастаймыз. В3 белгіленген пунктің тұтынушылығы 30 бірлікке тең деп есептейміз. Кестенің қалған бөлігі, яғни А2 және А3 жолдары және төрт бағанасы В1, В2, В3 және В4 Сij аз мәндегі тарифті тор көз В2 бағанасы мен А3 жолының қиылысында көрінеді, яғни С32=2, х32=50 десек, және бұл мәнді 3-кестесіне сәйкес әкелеміз. В2 бағанасын уақытша қарастырудан алып тастаймыз және А3 пунктінің қоры 120 бірлікке тең деп есептейміз. Бұдан соң кестенің қалған бөліктерін, яғни 2-ші жолды, А2 мен А3 және үш бағананы – B1 В3 В4 қарастырамыз. Онда Сij минималды тарифы В3 бағанасы мен А3 жолының қиылысу тор көзінде тұр және 3-ке тең. Жоғарыда жазылған әдіспен бұл тор көзді толтырамыз және В4 бағанасы мен А2 жолы, В4 баганасы мен А3 жолы, В1 бағанасы мен А2 жолының қиылысында тұратын ұқсасты түрде (белгілі бірізділікпен) тор көзді толтырамыз. Нәтижесінде тіректі жоспарын аламыз: Тасымалдау жоспарындағы тасымалдаудың жалпы құны мынаны кұрайды: 30 «Фогель аппроксимациясы» әдісі. Фогель аппроксимациясы әдісімен көліктік жоспардың оптималды жоспарын анықтауда барлық бағаналар мен жолдар бойынша әрбір итерацияда минималды тарифтердің арасындагы әр түрлілігі байкалады. Бұл әр түрлілік тапсырма шарттары кестесінде бағана мен жолдар үшін арнайы жүргізілгенде жазылады. Көрсетілген әр түрліліктердің арасынан минималды элемент таңдалады. Берілген әртүрлілікке сәйкес келетін жолда (бағанада) минималды тариф анықтайды. Ол жазылған тор көз осы итерацияда толтырылады. Егер бұл бағаналардың (жолдарда) бірнеше тор көздері үшін минималды тариф бірдей болса, онда берілген жолда (бағанада) болатын екі минимадды тарифтер арасындағы шамалы әр түрлілікке сәйкес бағанада (жолда) орналастырылған тор көздерді толтыру үшін таңдайды. Есеп-4. Фогель аппроксимация әдісін пайдалана отырып, көлік тапсырысының тірек жоспарын табу керек, алынған мәліметтер 4-кестеде көрсетілген (бұл тапсырманың тірек жоспары минималды элемент әдісімен алдында шығарылган). Шешімі. Шарт кестесінде әрбір бағана мен жолдар үшін берілген бағана немесе жолда жазылган екі минимадды тарифтер арасындағы айырмашылықты бағанаға немесе қосымша жолдарға сыйдырамыз. 4-кесте
жүктеу/скачать 1,09 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||