Транспортная задача и ее решение методом потенциалов, Постановка задачи и ее математическая модель - Транспортная задача и ее решение методом потенциалов
Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее рационального прикрепления пунктов отправления грузов (поставщиков) к пунктам их назначения (потребителям), чтобы общая стоимость транспортировки грузов была минимальной. Первая строгая постановка задачи была дана Хичкоком, а точный универсальный метод ее решения разработан советскими учеными Л. В. Конторовичем и М. К. Гавуриным.
Постановка задачи и ее математическая модель
Пусть в пунктах A1, A2, ..., Am производят некоторый однородный продукт в количествах a1, a2, ..., am соответственно. Этот продукт следует перевезти в пункты B1, B2, ..., Bn, потребляющие его соответственно в количествах b1, b2, ..., bn..
Пункты Ai () называются пунктами отправления или поставщиками, а пункты Bj () - пунктами назначения или потребителями. Рассмотрим сначала случай, когда суммарный объем производства равен суммарному объему потребления, т. е.
Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки по перевозке из пункта Ai в пункт Bj единицы продукции равны cij (,). Значения cij будем называть тарифами. Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Переменные xij будем называть перевозками.
Задача состоит в определении такого плана перевозок, при котором весь продукт из пунктов производства вывозится, запросы всех потребителей полностью удовлетворяются и суммарные транспортные издержки минимальны.
Условия T. З. удобно записывать в таблице следующего вида:
Таблица 1.1
Потребители |
B1 |
B2 |
... |
Bj |
... |
Bn | |
Постав- Щики |
Bj Ai |
B1 |
B2 |
... |
Bj |
... |
Bn |
A1 |
A1 |
C11 X11 |
C12 X12 |
... |
C1j X1j |
... |
C1n X1n |
A2 |
A2 |
C21 X21 |
C22 X22 |
... |
C2j X2j |
... |
C2n X2n |
... |
... |
... |
... |
... |
... |
... |
... |
Ai |
Ai |
Ci1 Xi1 |
Ci2 Xi2 |
... |
Cij Xij |
... |
Cin Xin |
... |
... |
... |
... |
... |
... |
... | |
Am |
Am |
Cm1 Xm1 |
Cm2 Xm2 |
... |
Cmj Xmj |
... |
Cmn Xmn |
В таблице 1.1 каждая клетка (i, j), соответствующая паре i-й поставщик - j-й потребитель, условно делится диагональю пополам и в правом верхнем углу записывается значение тарифа cij, а в левом нижнем - значение перевозки xij.
Математическая модель задачи имеет вид:
Xij ? 0, ;
Z = c11x11 + c12x12 + ... + c1nx1n + c21x21 + c22x22 + ... + c2nx2n + ... + cm1xm1 + cm2xm2 + ... + cmnxmn > min.
С помощью индексов суммирования эта модель запишется так:
Xij ? 0, ; (1.1)
(1.2)
> min. (1.3)
Условия (1.1) - условия неотрицательности перевозок (обратная транспортировка груза от потребителя к поставщикам запрещена).
Условия (1.2а) характеризируют полный вывоз продукта от поставщиков, а условия (1.2б) - полное удовлетворение запросов потребителей.
Суммарная стоимость Z транспортировки продукта согласно условию (1.3) должна быть минимальной.
Совокупность переменных xij, удовлетворяющих условиям (1.1) и (1.2), будем называть планом перевозок T. З. и записывать его в виде матрицы:
.
Совокупность тарифов сij будем записывать в виде матрицы, которую назовем матрицей тарифов:
.
Запишем систему ограничений T. З. в векторной форме. Обозначим столбец коэффициентов при xij через, а столбец сводных членов - через, тогда:
У вектора i-я и (m + j)-я компоненты равны единице, остальные компоненты равны нулю.
Система ограничений (1.2) T. З. в векторной форме будет иметь вид:
(1.4)
Похожие статьи
-
Ранг системы ограничений T. З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или...
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Вариант №1 1. Выбрать и обосновать наиболее эффективный метод решения задачи. 2. Разработать алгоритм и программу для решения задачи в общем виде. 3....
-
Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть...
-
Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...
-
Анализ предметной области Описание ПО решаемой задачи Предметной областью задачи № 2 также является процесс оплаты денежных средств по кредиту. Решается...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Анализ предметной области Предметной областью задачи является процесс определения суммы налога на дарение. Известны сумма подарков в МРОТ (минимальный...
-
Формирование области многокритериального выбора вариантов Стоит задача о выборе марки автомобиля с их известными особенностями и характеристиками....
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Для проверки соответствия требованиям ТЗ, была поставлена задача разработки 3-D модели корпуса Kyocera KD-PB1D79 при помощи системы AutoCAD. В этой части...
-
Построение модели предметной области с помощью описания структур данных и программного кода является классическим подходом в разработке ИС. Зачастую...
-
Методы Рунге-- Кутты-- важное семейство численных алгоритмов решения обыкновенных дифференциальных уравнений и их систем. Данные итеративные методы...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Постановка задачи: Фирма приобрела технологическую линию за начальную стоимость Sn. Срок службы технологической линии составляет K лет. Остаточная...
-
Метод конечных элементов (МКЭ) жесткости возник в аэрокосмической отрасли. Исследователи рассматривали различные подходы к анализу сложных частей...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Необходимо исследовать зависимость влияния различных факторов на параметр, характеризующий производство. В качестве такого параметра было выбрано...
-
Постановка задачи Основной целью дипломной работы является создание комплексной системы информационной безопасности предприятия на примере информационной...
-
Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ - Анализ потерь рабочего времени сорудников предприятия
Постановка задачи Имеется смета на выполнение проекта монтажа охранной сигнализации, в которой расписаны этапы выполнения работ, подбор специалистов на...
-
Построение модели сердца, Постановка задачи, Создание нового проекта - Построение модели сердца
Постановка задачи Мы рассмотрим простейшую математическую модель, описывающую процессы, похожие на биение сердца. Эта модель описана двумя...
-
Постановка задачи нечеткого управления Была рассмотрена задача по прогнозированию износа (в микрометрах) тормозных дисков автомобилей. Входные данные:...
-
Библиотека MSHTML MSHTML (так же известен как Trident) - браузерный движок для Microsoft Internet Explorer. Впервые Trident был реализован в четвертой...
-
На рисунке 1 представлен фрагмент электронной таблицы, в которой содержаться исходные данные для решения задачи. Рисунок 1 - Фрагмент электронной...
-
Постановка задачи - Расчет трудоемкости средствами Ms Excel
Необходимо рассчитать нормативную трудоемкость квартальной и месячной производственной программы цеха по деталям. Для этого необходимо перемножить...
-
Построение аналитической модели АОУ затруднено из-за отсутствия или недостатка априорной информации об объекте управления, а также из-за ограниченности и...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
Связь типов информационных систем с задачами принятия решений - Системы поддержки принятия решений
Применяются отдельные модели и методы для принятия оптимальных решений. Отметим, что в существенной мере характер всех поколений систем и их концепций...
-
Постановка задачи Имеющаяся база данных SQL имеет недостаточное количество полей и таблиц, не имеет упорядоченной структуры пользователей для работы с...
-
Обобщенный алгоритм решения задачи Необходимо рассчитать сумму налога на дарение, воспользовавшись налоговой шкалой. Если сумма подарка менее 80, то она...
-
Вычислить максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 на отрезке [a;b] с точностью е. L(x1), L(x2) - значения интерполяционного многочлена, построенного...
-
Варианты - Решение задач линейного программирования с использованием Microsoft Excel
Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл. 1.5). Таблица 1.5 Варианты задач к лабораторной работе № 1 №...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Характеристики ЛВС Используемый стандарт: IEEE 802.3ab -- стандарт, использующий витую пару категорий 5e. 1000BASE-T, стандарт Gigabit Ethernet....
-
Постановка задачи На стадии оперативного управления возможна замена материалов и комплектующих, указанных в спецификациях, их аналогами. Аналогами...
-
Постановка задачи, выбор предметной области Предметная область: "Автомобиль". Создание автомобиля будет состоять из трех этапов: выбор кузова, выбор...
-
Математическое описание в случае дозы интегральная основано на интегральной составляющей, в случае эффектов, экспоненциальной. Таким образом задержки...
Транспортная задача и ее решение методом потенциалов, Постановка задачи и ее математическая модель - Транспортная задача и ее решение методом потенциалов