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 одиниць, а решта — нулі.


 

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

84611. Модернизация системы автоматического регулирования температуры в термокамере машины ТО-180 14.69 MB
  Стабилизацией называю. процесс придания камвольным тканям - тканям из смеси шерсти с синтетическими волокнами устойчивых фиксированных размеров и рисунков ткацкого переплетения, а также способности противостоять образованию необратимых деформаций в процессах последующей обработки и эксплуатации.
84612. Расчет и проектирование фундаментов зданий и сооружений 1.29 MB
  Проектирование фундаментов на естественном основании Предварительное назначение основных параметров и размеров фундаментов Определение расчетного сопротивления грунта Конструирование фундамента и уточнение действующих нагрузок Определение вертикального напряжения от собственного веса грунта на...
84613. АНАЛИЗ И СИНТЕЗ ТИПОВЫХ ЭЛЕКТРОННЫХ УСТРОЙСТВ 15.7 MB
  Построение логарифмической амплитудно-частотной характеристики (ЛАЧХ) преобразователя сигналов на операционном усилителе. Для заданной схемы преобразователя аналоговых сигналов на операционном усилителе (ОУ) рассчитать и построить его ЛАЧХ и определить основные параметры данного устройства.
84614. Основы организации и функционирования бюджетной системы Российской Федерации 327.7 KB
  Цель данной курсовой работы – определение места и значимости внебюджетных фондов социального назначения в социальной политике государства. Для достижения поставленной цели необходимо решить следующие задачи: Рассмотреть сущность и задачи социальной политики государства.
84615. Фирменные холодные блюда и закуски ресторанов г. Омска: ассортимент, технология приготовления и оформления 757.41 KB
  Цель курсовой работы: изучить ассортимент, технологию приготовления и оформления холодных блюд и закусок ресторанов г.Омска. Задачи курсовой работы: Провести сравнительный анализ ассортимента холодных блюд и закусок в предприятиях общественного питания г.Омска. Дать рекомендации по обновлению меню.
84616. Маркетинговые службы в системе управления предприятием ресторанно-гостиничного бизнеса, их функции и задачи 72.32 KB
  На Западе о маркетинге заговорили лишь начиная с середины девятнадцатого века. Первым, кто высказал предположение о том, что маркетинг должен быть центральным направлением деятельности предприятия, а работа с собственным кругом потребителя – задачей менеджера, был Сайрус Маккормик.
84617. Кодирование информации в защищенных компьютерных сетях 833.5 KB
  При цифровом кодировании дискретной информации применяют потенциальные и импульсные коды. В потенциальных кодах для представления логических единиц и нулей используются только значение потенциала сигнала, а его перепады, формирующие законченные импульсы, во внимание не принимаются.
84618. Технология приготовление длинных смешанных напитков: джулепы, коблеры, кулеры, сэнгер, флипы, слинги 1.27 MB
  Длинные смешанные напитки — это напитки объемом более 150 мл, разбавленные наполнителем. Наполнитель может быть газированным (вода из сифона, фруктово-ягодные напитки, минеральная вода, тонические воды) и негазированным (соки). Приготавливают длинные напитки путем смешивания компонентов в питьевом стакане.
84619. НАЦИОНАЛИЗМ КАК СУБЪЕКТИВНОЕ ОСНОВАНИЕ ДЛЯ РАЗЖИГАНИЯ ЭТНИЧЕСКИХ КОНФЛИКТОВ В РОССИИ 64.52 KB
  Предыстория осетино-ингушского конфликта. Динамика и последствия осетиноингушского конфликта. Причины осетино-ингушского конфликта. Возможные варианты урегулирования осетинО-ингушского конфликта.