Транспортная задача - Использование методов линейного программирования
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.
Имеется ряд пунктов производствас объемами производства в единицу времени (месяц, квартал), равными соответственнои пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:
Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю -- эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые.
Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:
При этом каждый потребитель получает нужное количество продукта:
И каждый поставщик отгружает весь произведенный им продукт:
Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.
Рассмотрим таблицу.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы -- пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем -- значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi, j=0), называют свободными, а ненулевые -- занятыми (xi, j>0).
В1 |
В2 |
Вn |
Всего | |
A1 |
C1,1 |
C1,2 |
C1,n |
А1 |
A2 |
C2,1 |
C2,2 |
C2,n |
А2 |
Am |
Cm,1 |
Cm,2 |
Cm, n |
Аm |
B1 |
B2 |
Bn |
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.
Производственно-транспортная задача
Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).
Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.
Похожие статьи
-
Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее...
-
Ранг системы ограничений T. З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или...
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Составление опорного плана методом северо-западного угла - Транспортная задача
Заполнение таблицы 1 начинаем с левого верхнего угла. Сумма поставок по строке равна запасу соответствующего пункта отправления, а сумма поставок по...
-
Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Метод наименьшей стоимости - Транспортная задача линейного проектирования
При этом методе на каждом шаге построения опорного плана первой заполняется клетка оставшейся части таблицы, которая имеет наименьшее расстояние. Если...
-
Существует несколько способов построения опорного плана. Это метод северо-западного угла, метод наименьшей стоимости, приближенный метод Фогеля. Суть...
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Постановка задачи Постановка практической задачи ЛП включает следующие основные этапы: - определение показателя эффективности, переменных задачи, -...
-
Оптимизация задачи методом потенциалов - Транспортная задача линейного проектирования
Метод потенциалов позволяет автоматически, без размышления выделять свободные клетки с отрицательной ценой цикла и определять их цены. В соответствии с...
-
Цель работы. В городе имеется четыре АТС со свободной номерной емкостью (1,2,3,4). Известно количество свободных телефонных номеров на каждой станции....
-
Введение - Транспортная задача линейного проектирования
В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная...
-
Пересчет симплекс-таблицы. - Транспортная задача
Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...
-
Решение транспортной задачи с помощью Mathcad, Список используемых источников - Транспортная задача
Задаем начальное значение х Задаем количество пунктов отправления и пунктов потребления : Неизвестные параметры транспортной задачи обозначим:...
-
Заключение, Список литературы - Транспортная задача линейного проектирования
В курсовом проекте изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного...
-
Это задача оптимизации, в которой переменные принимают только два значения: "единица - ноль". Пример - задача "коммивояжера". Цель работы: минимизировать...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
Метод Фогеля - Транспортная задача линейного проектирования
В большинстве случаев, этот способ делает опорный план наиболее близкий к оптимальному. Использовать этот метод рекомендуется при расчетах вручную. В...
-
Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Вариант №1 1. Выбрать и обосновать наиболее эффективный метод решения задачи. 2. Разработать алгоритм и программу для решения задачи в общем виде. 3....
-
Варианты - Решение задач линейного программирования с использованием Microsoft Excel
Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл. 1.5). Таблица 1.5 Варианты задач к лабораторной работе № 1 №...
-
Формулировка задачи - Линейное программирование
Даны линейная функция Z=С1 х1 +С2 х2 +...+СN xN (1.1) И система линейных ограничений A11 x1 + a22 x2 +... + a1N ХN = b1 A21 x1 + a22 x2 +... + a2N ХN =...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Аннотация В статье рассматриваются два способа уменьшения времени вычисления дерева решений для задач линейного параметрического программирования с...
-
Введение - Использование методов линейного программирования
Линейное программирование -- область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся...
-
Прямое использование предсказания позволяет воспроизводить звук, но с плохим качеством. Поэтому этот метод имеет много различных разновидностей,...
-
Решение транспортной задачи средствами Microsoft Exel - Транспортная задача
Многие задачи экономико-математического моделирования являются оптимизационными, т. е. в них требуется найти максимальное (минимальное или равное...
-
Математическое обеспечение позволяет использовать методы автоматизированного поиска оптимальных вариантов при проектировании системы. Часто при решении...
-
В курсовой работе в соответствии с заданием на проектирование решается задача разработки программы вычисления определенных интегралов численными...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Понятие линейной стохастической сети Одним из важных этапов технологического проектирования электронных вычислительных средств является расчет запусков...
-
Задачи линейного программирования - Использование методов линейного программирования
1. С помощью средств Excel найти решение задачи линейного программирования. L(Х) = 14х -9х2 - х4 +6,4х5 min; 0,9 х + 10х2 -28х4 +5х5 245, 0,8 х+ 1,7х2...
-
1. Каковы основные этапы решения задач ЛП в MS Excel? 2. Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений? 3. В чем...
-
Для того, чтобы разработать оптимальный метод интеграции сторонних систем в существующую ИТ-инфраструктуру систем компании, требуется точно поставить...
-
Метод Гаусса. Метод Гаусса решения систем линейных уравнений состоит в последовательном исключении неизвестных и описывается следующей процедурой. С...
Транспортная задача - Использование методов линейного программирования