28486

Постановка транспортної задачі та її математична модель

Доклад

Математика и математический анализ

Постановка транспортної задачі та її математична модель. Побудуємо математичну модель закритої транспортної задачі Позначимо через xij кількість одиниць вантажу запланованого до перевезення від iго постачальника до jго споживачаz сумарну вартість запланованих перевезень Для зручності умову задачі запишемо у вигляді таблиці табл 1 яку надалі будемо називати транспортною сіткою При цьому постачальників скорочено позначимо літерою П а споживачів С Таблиця 1...

Украинкский

2013-08-20

31.64 KB

6 чел.

14.21. Постановка транспортної задачі та її математична модель.

Деякий однорідний вантаж, зосереджений у т постачальників А1, А2,… , Аm в кількостях a1 , а2,…,am одиниць відповідно, необхідно перевезти n cпоживачам В1, В2,…Вn  в кількостях b1, b2,…, bn одиниць Відомаоматриц  вартостей перевезення одиниці вантажу від постачальника Аi до споживача Вj. Необхідно скласти такий план перевезень вантажів, який дозволить вивезти всі вантажі, повністю задовільнити потреби споживачів і сумарна вартість перевезень за яким буде мінімальною.Зауваження. Така постановка вимагає виконання рівності

                                                                Тобто сумарні запаси дорівнюють сумарним потребам Транспортну задачу, для якої виконується рівність (1) будемо називати закритою (з правильним балансом) і відкритою (з неправильним балансом) у протилежному випадку. Побудуємо математичну модель закритої транспортної задачі Позначимо через xij кількість одиниць вантажу, запланованого до перевезення від i-го постачальника до j-го споживача,z — сумарну вартість запланованих перевезень Для зручності умову задачі запишемо у вигляді таблиці (табл 1), яку надалі будемо називати транспортною сіткою При цьому постачальників скорочено позначимо літерою П, а споживачів — С                                                                            Таблиця 1

Знайдемо сумарну вартість запланованих перевезень Зокрема, сij — вартість перевезення одиниці вантажу відА1 до В1, а таких одиниць планується перевезти х11. Тому с11· х11- вартість запланованих перевезень від А1до В1. Аналогічно знаходяться вартості перевезень для кожної з клітинок Сума їх дасть z:

                                                                                   Систему обмежень отримаємо із умов задачі: а)  всі вантажі повинні бути вивезені, зокрема, сума всіх змінних будь-якою рядка дорівнює відповідному запасу вантажів,б)  всі потреби повинні бути задоволеними, тобто сума всіх змінних кожної колонки дорівнює відповідній потребі споживача.За змістом невідомих повинні виконуватися нерівності xij 0 для всіх значень індексів.Остаточно система обмежень набуває такого вигляду:

                                                                          Побудована математична модель являє собою задачу лінійного програмування Для існування оптимального плану задачі лінійною програмування достатньо непорожності множини допустимих планів і обмеженості цільової функції на цій множині Легко перевірити, що сукупність є                              є допустимим планом задачі (2)- (3), тобто множина допустимих планів непорожня.3 врахуванням рівнянь системи (3) можна отримати подвійну нерівність С1М≤ZС2М, справедливу для всіх допустимих планів, де С1 та С2 відповідно найменший І а найбільший елемент матриці вартостей перевезення вантажів.Таким чином, будь-яка закрита транспортна задача мас оптимальний план. В принципі, цей план можна було б знаходити одним Із аналітичних методів, розглянутих вище Проте такий підхід зумовив би великі розміри симплексних таблиць, адже чисто змінних дорівнює mn. А з другого боку, систему рівнянь (3) можна записати у векторно-матричномулвиглядіАХ=Ь,                                                   Де  А — (m +n)х (mn) - матриця, особливістю якої є те, що кожен Із елементів п є нулем або одиницею, причому кожна колонка матриці має лише по дві одиниці, решта елементів - нульові, а кожен рядок - n  або m одиниць, а решта — нулі.


 

А также другие работы, которые могут Вас заинтересовать

80992. Поняття та сутність методики навчання історії 31.29 KB
  Метод спосіб досягнення мети розв\'язання конкретного завдання Ефективність і якість навчання історії залежить від того наскільки вчитель володіє методами навчання і застосовує їх на практиці. Початкові елементи методики навчання історії зародилися з введенням викладання предмета як відповідь на практичні питання про цілі викладання про відбір історичного матеріалу якому навчали учнів і прийоми його розкриття. Методика історії як наука пройшла складний шлях розвитку.
80993. Методика роботи з історичним документом 33.52 KB
  Як відомо, до історичних джерел належить все створене людиною, а також предмети матеріальної культури, звичаї, обряди, памятки писемності. У широкому сенсі памятки писемності в методиці називають документами.
80994. Загальна характеристика шкільної програми з історії. Принципи їх побудови 38.33 KB
  Типи навчальних програм: Навчальні програми можуть бути типовими робочі і авторськими. Типові державні навчальні програми з історії розробляються на основі державного освітнього стандарту. Тому виникає необхідність періодично оновлювати навчальні програми у відповідності з розвитком педагогічної науки і практики.
80995. Проблема інтерпретації навчальних текстів на уроках історії. Інтерпретація (лат. interpretatio) — розяснення, тлумачення — відносно історичних текстів та ін.. (наукових та літературних текстів) 34.86 KB
  Щоб запобігти некритичному сприйняттю учнями історичної інформації, недостатньо тільки навчити їх досліджувати джерела. Важливим є також розвиток вмінь аналізувати та критично оцінювати інтерпретацію минулого, що міститься в будь-якому джерелі
80997. Закономерности и особенности развития детей с психофизическими нарушениями 31.05 KB
  Вторичные возникающие опосредованно в процессе аномального социального развития. Первичный дефект может иметь характер недоразвития или повреждения. Выготского является основным объектом в психологическом изучении и коррекции аномального развития.
80998. Категории детей с нарушениями интеллектуального развития, их развитие и обучение 30.24 KB
  имбецильность умеренная выраженность интеллектуального недоразвития дети не дееспособны не обучаемы но способны к овладению простыми навыками; 3. Дети с умственной отсталостью запаздывают в психическом развитии уже с первых дней жизни. По уровню речевого развития умственно отсталые дети представляют неоднородную группу: от общего недоразвития речи до достаточно развернутой обиходной речи но с нарушениями фонетики семантики. Дети с простой неосложненной дебильностью.
80999. Категории детей с задержкой психического развития, их развитие и обучение 29.64 KB
  Причины выраженной задержки психического развития: минимальные слабовыраженные органические повреждения или функциональная недостаточность центральной нервной системы возникшие в результате воздействия патогенетических факторов во внутриутробном природовом или в раннем периоде жизни ребенка; длительные хронические соматические заболевания перенесенные в раннем детстве; длительная социальнокультурная депривация; влияние стрессовых психотравмирующих факторов. психогенный генезис связывается с неблагоприятными условиями воспитания...
81000. Категории детей с нарушениями слуха, их развитие и обучение 29.05 KB
  Среди глухих детей различают: глухих без речи ранооглохших когда поражение слуха возникает у ребенка в доречевой период или в самом начале формирования речи; глухих сохранивших в той или иной мере речь позднооглохших это дети с потерей слуха но относительно сохранной речью ввиду сравнительно позднего возникновения глухоты. Врожденная или ранняя потеря слуха приводит к отсутствию речи немота либо ее грубому недоразвитию. У глухих детей изза речевых нарушений задерживается общение обеспечивающее совместную со взрослыми...