танлов масаласининг қўйилиши. мак усули

DOC 141,5 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1352191414_29807.doc å = = n j ij x 1 1 å = = m i ij x 1 1 min 1 1 ¾ ® ¾ = å å = = ij n j ij m i x b f танлов масаласининг қўйилиши www.arxiv.uz танлов масаласининг қўйилиши. мак усули режа: 1. танлов масаласининг қўйилиши. 2. транспорт масаласининг амалий масала мисолида математик модели. 3. танлов масаласининг ўзига хос хусусиятлари. 4. мак усули моҳияти. 5. мак усулини амалий мисолни ечиш билан тушунтириш. танлов масаласи транспорт масаласи каби чизиқли программалаш масаласига киради, лекин у махсус кўринишга эга. хусусан, чекликлардаги коэффициентлар 0 ёки 1 коэффициентга эга, ҳар бир ўзгарувчи эса фақат иккита чекликда иштирок этади. мазкур мавзуда ўрганиладиган масала траспорт масаласининг танлов характерига эга бўлган хусусий кўринишидир. бу усулнинг моҳиятини қуйидаги масаланинг мазмунига боғлаб тушунтирамиз. r1, r2,..., r5 - рақамли 5 киши t1, t2,..., t5 рақамли топшириқларни бажара олади. касбий маҳоратига боғлиқ равишда бу топшириқларни …

ечимининг бештаси xij = 1 қолганлари 0 бўлади. бошқа томондан караганда эса 5(5 ўлчамдаги вақт матрицасида ҳар бир устун ва ҳар бир сатрдан биттадан шундай бешта элементни топиш керакки, натижада танланган элементлар йиғиндиси минимум бўлсин. xij - нинг 0 ёки 1 га тенг бўлиши, баъзи бир ҳолларда масала қўйилишига маъно бериш учун зарур. масалани n(n ўлчамдаги матрица учун умумлаштириш мумкин. ҳар бир бундай матрица учун масалада ҳар бир сатр ва ҳар бир устундан биттадан n та элементни танлаш керакки, уларнинг йиғиндиси энг кичик бўлсин. танланган элементларни x1i, x2j,..., xnt деб белгилаймиз. бу ерда i, j,..., t - 1, 2,..., n - элементларнинг баъзи бир ўрин алмаштиришидир. бундай ўрин алмаштиришлар n та бўлади, демак ҳатто энг кам миқдордаги n та ечимни топиш учун ҳам ҳамма ечимларни кўриб чиқиш, мумкин бўлмаган даражада чўзилиб кетади. шунинг учун бундай масалаларни, "транспорт" масаласининг хусусий ҳоли бўлса ҳам, "транспорт" усули билан ечиш мақсадга мувофиқ эмас. унга …

n(n ўлчамдаги масалани ечиш учун қўллаймиз. ҳар бир сатрдан минимал элементдан танлаймиз. ҳар бир минимал элемент остига чизамиз. агар ҳар бир устунда биттадан ости чизилган элемент бўлса, бу ости чизилган элементлар базис - оптимал танловни билдиради. масала алгоритми. бошлаш: устунлар тўпламини иккита а ва а' тўпламларга ажратамиз. а танланган тўплам, а' танланмаган тўплам. бошида (бошланишга кейинги қайтишларда ҳам) танланган устунлар йўқ, шунинг учун а тўплам бўш, а' тўплам эса ҳамма устунларга эга. қадам1:а' тўпламдан биттадан ортиқ остига чизилган элементларга эга бўлган устун танланади. бу устун а' тўпламдан а тўпламга ўтказилади. қадам 2 : i- сатрдаги а тўплам элементлари bi га, а' тўпламнинг i- сатридаги минимал элементи эса ai' га min (ai'-bi) = ar'-br бўлсин. қадам 3: а тўпламнинг ҳамма элементларини ar'-br га ошириш керак. қадам 4: ar'ни остки нуқталар билан белгилаймиз. энди ar' "нуқталар билан белгиланган" элемент. қадам 5: с - ar' га эга бўлган устун бўлсин. агар с да …

ри br ни ar' га ошириб, йўналишнинг қолган элементларини оширишини қадам 8 гача тўхтатиб турсак, ҳисоблашларни қисқартириш мумкин. бундай ҳолда устуннинг қолган элементлари остига чизилган элементлар қанчага оширилган бўлса, шунчага оширилиши керак. қуйида бу усулнинг тўла баёнини юқорида келтирилган мисолни ечиш учун келтирамиз. одамлар топшириқлар т1 т2 т3 т4 т5 м1 10 5 9 18 11 м2 13 19 6 12 14 м3 3 2 4 4 5 м4 18 9 12 17 15 м5 11 6 14 19 10 i босқич бошлаш қадам 1: 2 – устун а тўпламга ўтади. 10 5 9 18 11 қадам 2. 1-сатр: 5 нинг остига чизинг. а’=9 да минимум топилди, фарқ 4 га тенг 13 19 6 12 14 3-сатр: 2 нинг остига чизинг, минимум а’=3 нуқтада топилди, фарқ 1 га тенг. 3 2 4 4 5 4-сатр: 9 нинг остини чизинг, минимум а’=12 нуқтада топилди, фарқ 3 га тенг. 18 9 12 …

9 14 19 10 қадам 3: 2 ва 3 устунлардаги ҳамма элементларни 1 га оширамиз. 10 9 10 18 11 қадам 4: 5- сатр, 5-устундаги элементни нуқталар билан белгилаймиз. 13 23 7 12 14 қадам 5: с (5-устун) бошқа остига чизилган элемент-ларга эга эмас, шунинг учун кейинги қадамга ўтамиз. 3 6 5 4 5 қадам 6: 5-сатр, 5-устундаги 10 элементининг остини тўла чизамиз. 18 13 13 17 15 қадам 7: 5-сатр, 2-устундаги 10 элементи остидаги чизиқни бекор қиламиз 11 10 15 19 10 қадам 8: 0 (2- устун) бошқа остига чизилган элементларга эга, 4-устунда остига чизилган элементлар йўқ, шунинг учун бошланишига қайтамиз. бошланиш қадам 1: 2- устун а тўпламда бор 10 9 10 18 11 қадам 2: min(ar' - bi) 13 – 13 = 0 га тенг 13 23 7 12 14 қадам 3: ҳеч нарса ўзгармайди. 3 6 5 4 5 қадам 4: 4-сатр,3-устундаги 13 элементини нуқталар билан белгилаймиз. …

Хотите читать дальше?

Скачайте полный файл бесплатно через Telegram.

Скачать полный файл

О "танлов масаласининг қўйилиши. мак усули"

1352191414_29807.doc å = = n j ij x 1 1 å = = m i ij x 1 1 min 1 1 ¾ ® ¾ = å å = = ij n j ij m i x b f танлов масаласининг қўйилиши www.arxiv.uz танлов масаласининг қўйилиши. мак усули режа: 1. танлов масаласининг қўйилиши. 2. транспорт масаласининг амалий масала мисолида математик модели. 3. танлов масаласининг ўзига хос хусусиятлари. 4. мак усули моҳияти. 5. мак усулини амалий мисолни ечиш билан тушунтириш. танлов масаласи транспорт масаласи каби чизиқли программалаш масаласига киради, лекин у махсус кўринишга эга. хусусан, чекликлардаги коэффициентлар 0 ёки 1 коэффициентга эга, ҳар бир ўзгарувчи эса фақат иккита чекликда иштирок этади. мазкур мавзуда ўрганиладиган масала траспорт масаласининг танлов характерига эга бўлган …

Формат DOC, 141,5 КБ. Чтобы скачать "танлов масаласининг қўйилиши. мак усули", нажмите кнопку Telegram слева.

Теги: танлов масаласининг қўйилиши. м… DOC Бесплатная загрузка Telegram