Транспортная задача линейного программирования

Решение транспортных задач линейного программирования

Среди всех задач линейного программирования (ЗЛП) особняком стоят несколько типов, в частности, транспортные задачи. Конечно, и их можно решить общепринятым симплекс-методом, но вычисления получатся неоправданно сложными и объемными из-за размерности задачи (например, для самой простой задачи с 3 складами и 3 поставщиками — 9 ограничений и 9 переменных).

Поэтому для решения транспортных задач были разработаны специальные методы: для нахождения опорного/начального плана (минимального элемента, северо-западного угла, Фогеля), и для нахождения оптимального плана (метод потенциалов, дифференциальных рент, распределительный метод).

Примеры решений транспортных задач ЛП некоторыми из этих методов приведены в этом разделе — изучайте, ищите похожие, решайте (также вы можете перейти к примерам решения ТЗ в Excel). Если вам нужна помощь в выполнении подобных заданий, перейдите в раздел: Решение контрольных работ по линейному программированию.

Примеры решения транспортной задачи онлайн

Задача 1. Из трех холодильников Ai, i=1..3, вмещающих мороженную рыбу в количествах ai т, необходимо последнюю доставить в пять магазинов Bj, j=1..5 в количествах bj т. Стоимости перевозки 1т рыбы из холодильника Ai в магазин Bj заданы в виде матрицы Cij, 3×5.
Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

Решение транспортной задачи методом потенциалов (pdf, 63 Кб)

Задача 2. Построить закрытую модель транспортной задачи.

Построение модели транспортной задачи (pdf, 50 Кб)

Задача 3. В таблице приведены исходные данные транспортной задачи: заданы удельные транспортные расходы на перевозку единицы груза, слева указаны возможности поставщиков, а сверху – спрос потребителей. Сформулируйте экономико-математическую модель транспортной задачи, распределительным методом найдите оптимальный план перевозок.
(таблица в файле)

Решение транспортной задачи распределительным методом (pdf, 79 Кб)

Задача 4. Решить транспортную задачу
1) методом потенциалов (опорный план построить всеми известными способами);
2) методом дифференциальных рент;
3) любым методом при ограничениях: x24≥4, x35≤5, x12=3.
(таблица в файле)

Решение транспортной задачи с ограничениями различными методами (pdf, 12 страниц, 124 Кб)

Примеры решений ЗЛП по разным темам

 

Переменными (неизвестными) транспортной задачи являются хij, i=1,2,…,m, j= 1, 2, …, п — объемы перевозок от каждого i-го поставщика каждому j -му потребителю.

Пример решения задачи. Решение транспортной задачи

Эти переменные можно записать виде матрицы перевозок:

.

Так как произведение сijхij определяет затраты на перевозку груза от i-го поставщика j -му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид:

F(X)=→ min.

Система ограничений задачи состоит из двух групп уравнений. Первая группа из т уравнений описывает тот факт, что запасы всех т поставщиков вывозятся полностью:

, i =1, 2, …, т.

Вторая группа из п уравнений выражает требование полностью удовлетворить запросы всех п потребителей:

, j= 1, 2,…, п.

Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:

F(X) =→ min,

, i=1, 2,…, т, , j=1, 2,…, п, хij ≥ 0, i =1,2,…, т, j=1,2,…, п.

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

=.

Такая задача называется задачей с правильным балансом, а ее модель ― закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.

Математическая формулировка транспортной задачи такова: найти переменные задачи Х=(хij), i =1, 2, …, т, j= 1, 2,…, п,удовлетворяющие системе ограничений, условиям неотрицательности и обеспечивающие минимум целевой функции. Математическая модель транспортной задачи может быть записана и векторномвиде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи:

х11х12 х1n x21 x22x2nxm1xm2xmn

Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной хij, является вектором-условием задачи и обозначается через Аij. Каждый вектор имеет всего т + п координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора Аij, стоит на i-м месте, а вторая на (т +j)мместе, т.е.

Номер

координаты

Обозначим через А0 вектор ограничений и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:

F(X) =→ min,

,

хij≥ 0, i =1,2,…, т, j=1,2,…, п.

Пример.Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице:

bjai

Решение. Введем переменные задачи (матрицу перевозок):

.

Запишем матрицу стоимостей:

.

Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц С и X:

F(X) =3х11+ 5х12 + 7х13 + 4х21 + 6х22 + 10х23.

Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.

Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам 1-го поставщика, а сумма перевозок во второй строке матрицы X — запасам 2-го поставщика:

х11 + х12 + х13 = 40, х21 + х22 + х23 = 50.

Это означает, что запасы поставщиков вывозятся полностью. Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:

х11+ х21 = 20,

х12+ х22 = 30,

х13+ х23 = 40.

Это означает, что запросы потребителей удовлетворяются полностью. Необходимо также учитывать, что перевозки не могут быть отрицательными:

хij≥ 0, i =1,2,…, т, j=1,2,…, п.

Следовательно, математическая модель рассматриваемой задачи такова: найти переменные задачи, обеспечивающие минимум функции

F(X) =3х11+ 5х12 + 7х13 + 4х21 + 6х22 + 10х23

и удовлетворяющие системе ограничений

и условиям неотрицательности хij≥ 0, i =1,2,…, т, j=1,2,…, п.

 


Дата добавления: 2014-01-04; Просмотров: 133; Нарушение авторских прав?;




Читайте также:

Транспортная задача и принципы ее решения

На сегодняшний день множество предприятий занимаются перевозкой продукции для ее дальнейшей реализации. Поэтому большое значение имеет процесс оптимизации грузоперевозок с целью минимизации затрат на доставку грузов. Этим вопросом занимается линейное программирование, точнее такое его направление, как решение транспортной задачи. Этот вопрос и будет рассмотрен далее в статье.

Спасибо, что читаете и делитесь с другими

Понятие транспортной задачи. Открытые и закрытые типы задач

Начнем с определения транспортной задачи. Условно говоря, у вас есть товар, расположенный на нескольких складах.

Решение транспортной задачи в Excel с примером и описанием

Необходимо доставить товар нескольким потребителям – это могут быть магазины, ларьки на рынке и т.д. – при этом у вас есть выбор из нескольких маршрутов. Каждый потребитель имеет свою потребность в товаре, кому-то нужно получить, к примеру, 10 тонн груза, а кому-то хватит и 5 тонн товара.

Ясно, что стоимость перевозки будет различаться в зависимости от количества перевозимого груза и дальности пути. Минимизировать нужно суммарные затраты на перевозку груза. Введем нужные обозначения, пусть $n$ – количество складов, а $m$ – количество точек назначения (потребителей). Через $С(i,j)=c_{ij}$ обозначим стоимость перевозки одной единицы груза из $i$-го склада к $j$-му потребителю.

При этом $a(i)=a_i$ означает запас груза у $i$-го склада, а $b(j)=b_j$ – потребность соответствующего потребителя. Ясно, что общая стоимость перевозки вычисляется как сумма всех затрат на перевозку товара от каждого склада к каждому потребителю. Пусть вас не пугает такая общая постановка задачи, если из какого-то склада нельзя перевезти товар, например из-за невыгодного расположения, то соответствующий $b$ можно установить равным нулю.

Теперь можно перейти к математической формулировке задачи. На языке формул задача примет следующий вид: $$\sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \to \min$$ при следующих ограничениях: $$ \left\{ \begin{array}{l} \sum_{j=1}^{n} x_{ij} = a_i,\\ \sum_{i=1}^{m} x_{ij} = b_j,\\ x_{ij} \geq 0, c_{ij} \geq 0, a_{i} \geq 0, b_{j} \geq 0,\\ i=1,2,…,m; j=1,2,…,n. \end{array} \right. $$ В такой постановке все ясно и дальнейших пояснений не требуется. Остается только решить транспортную задачу.

Существует две разновидности транспортной задачи – открытая и закрытая. Закрытая задача характеризуется тем, что суммарная потребность всех потребителей равна суммарным запасам всех складов. То есть, весь товар на всех складах будет реализован полностью. Математически это пишется как $$ \sum_{i=1}^{m} a_i =\sum_{j=1}^{n} b_j.$$

В открытой задаче суммарная потребность и суммарные запасы не совпадают. Например, какой-то склад не реализуется товар полностью, появляются остатки продукции. В этом случае процесс решения транспортной задачи немного усложняется, потребуется ввести фиктивного поставщика или потребителя с нулевыми стоимостями перевозки.

Решение транспортной задачи: пример постановки, основные методы

Рассмотрим пример постановки простой транспортной задачи.

В следующей таблице приведены стоимости перевозок единицы товара из определенного склада к определенному потребителю.

Например, число 7 в последней строке означает, что на перевозку единицы товара из склада №3 к заводу С тратится семь условных единиц денег. При этом 350+350+500=350+350+250+250=1200. Следовательно, потребности заводов равны запасам всех складов – это закрытая задача.

Для того чтобы решить транспортную задачу используется множество методов. В зависимости от особенностей задачи используются метод потенциалов, дифференциальных рент (для поиска оптимального плана), метод северо-западного угла, метод наименьшего элемента (для поиска опорного плана) и т.д. До сих пор одним из самых популярных остается симплексный метод в силу его универсальности. Этот метод хорошо реализован в надстройке «Поиск решения», доступной в стандартной программе Excel. Достаточно активировать «Поиск решения» и ввести условия, и вы получите подробное решение.

Подробные примеры: Транспортные задачи с решениями.

Спасибо, что читаете и делитесь с другими

Дополнительно:

Еще статьи о методах решения задач линейного программирования

СОДЕРЖАНИЕ

Введение 5

1 Объект исследования 6

2 Математическое обеспечение 8

2.1 Математическая модель 82.2 Выбор метод составления опорного плана 92.3 Нахождение оптимального решения 11

3 Практическая реализация 13

4 Руководство пользователя 17

Заключение 19

Библиографический список 20

Приложение А. Блок-схема 21

Приложение Б. Листинг программы 22

ВВЕДЕНИЕ

В любой сфере своей деятельности человек неизбежно сталкивается с задачами оптимизации. Экономическое планирование, управление, распределение ограниченных ресурсов, анализ производственных процессов, проектирование сложных объектов всегда должно быть направлено на поиск наилучшего варианта с точки зрения намеченной цели.

Одной из распространенных задач оптимизации является задача о минимизации затрат при транспортировке грузов. Данная задача является одной из центральных в экономическом планировании наряду с задачей максимизации доходов при ограниченных ресурсах.

Задача минимизации затрат сводится к отысканию наименьшего значения функции, которую принято называть целевой. Целевая функция является линейной функцией своих аргументов, а условия, определяющие их допустимые значения, имеют вид линейных уравнений и неравенств.

В рамках реальных экономических задач число аргументов целевой функции обычно бывает очень большим. Поэтому практическая реализация алгоритмов решения таких задач принципиально невозможна без использования современной вычислительной техники.

Целью данной курсовой работы является поиск оптимального распределения транспортных средств по маршрутам. За счет правильного составления плана можно минимизировать затраты на перевозку.

1 ОБЪЕКТ ИССЛЕДОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ

Однородная транспортная задача есть прикладная задача линейного программирования, в которой требуется найти оптимальный план транспортировки некоторого однородного продукта из конечного числа пунктов поставки с заданными объемами производства в конечное число пунктов потребления с известными объемами потребностей:

· минимизирующий суммарную стоимость транспортировки,

· не превышающий объем производства в каждом пункте поставки,

· полностью покрывающий потребности в каждом пункте потребления,

при заданной стоимости перевозки единицы транспортируемого продукта между каждой парой пунктов поставки и потребления.

Транспортная задача была впервые сформулирована Хитчкоком и с тех пор применяется для решения практических задач доставки и распределения однородных продуктов.

Для решения транспортной задачи разработано несколько методов, каждый из которых отличается от другого методом заполнения матрицы перевозок. Существуют два типа транспортной задачи: открытая и закрытая. Транспортная задача называется открытой если сумма запасов товара на складах отличается от суммы потребностей товаров у магазинов. Транспортная задача называется закрытой, если сумма запасов товара на складах равняется сумме потребностей магазинов. Решение существует только для закрытой транспортной задачи, поэтому если транспортная задача открытая, то ее надо привести к закрытому типу. Для этого в случае, если запас товара на складах превышает потребность магазинов, то вводят фиктивного потребителя, который выбирает весь избыток товара. В случае же, если существует дефицит товара, т.е. потребность магазинов больше, чем запас товаров на складах, то вводят фиктивного поставщика, с фиктивным запасом товара на складе. В обоих случаях в матрице тарифов перевозок данному складу или магазину проставляется нулевая цена перевозки.

В качестве задания транспортная задача имеет следующий вид:

Таблица 1

В таблице 1 приведены расходы на транспортировку партий товаров с трех фабрик (А, Б и В) к четырем складам (Г, Д, Е и Ж). в ней также приведены количество товара на каждой из фабрик и вместимость складов. Требуется определить маршруты, по которым следует направлять товары, чтобы минимизировать общие расходы.

2 МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ 2.1 Математическая модель

Имеется m пунктов поставки (поставщиков) и n пунктов потребления некого однородного продукта. Для каждого поставщика i = 1,…,m задан объем производства Ai , а для каждого потребителя j = 1,…,n задан объем потребления Bj и известна стоимость доставки единицы продукта Ci,j из пункта производства i в пункт потребления j. Управляемые параметры Xi,j характеризуют объем перевозки между каждым поставщиком i = 1,…,m и потребителем j = 1,…,n. В случае сбалансированного производства и потребления:

A1 + … + Am = B1 + … + Bn (1)

оптимальный план транспортировки соответствует минимизации линейной целевой функции:

(2)

при m линейных ограничениях по поставке:

Xi,1 + … + Xi,j + … + Xi,n = Ai , i = 1,…,m (3)

и n линейных ограничениях пo потреблению:

X1,j + … + Xi,j + … + Xm,j = Bj , j = 1,…,n, (4)

а также при очевидном условии неотрицательности управляемых переменных:

, i = 1,…,m и j = 1,…,n.

(5)2.2 Выбор метод составления опорного планаРешение транспортной задачи, после того, когда было установлено, что она открытая либо устранен путем коррекции несбалансированность ее, начинается с составления опорного плана, то есть отыскания начального базисного решения.Существует большой выбор методов составления опорного плана, рассмотрим некоторые из них. Метод минимального элемента. Алгоритм метода минимального элемента состоит в следующем.

Как решить транспортную задачу?

Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности у потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D. Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения. Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай, когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. В дальнейшем весь процесс повторяется до тех пор, пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазиновМетод Фогеля. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей выбирается строка или столбец с максимальной разность. В выбранной строке или столбце, как и в методе минимального элемента, заполняется клетка с наименьшим значением тарифа. Затем обнулявшаяся строка или столбец исключаются из рассмотрения и весь процесс повторяется до полного исчерпания запаса товаров на складах. Метод двойного предпочтения. В начальной своей стадии этот метод похож на метод минимального элемента, но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется, минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу минимального элемента в эту клетку заносится значение D=MIN(A,B), соответствующие запас и потребность уменьшаются на эту величину.Обнулившаяся строка или столбец исключаются из рассмотрения и процесс повторяется, начиная с первого не исключенного столбца. Если найденный минимальный элемент не минимален в своей строке, то происходит переход к следующему столбцу и так до тех пор, пока не будет найден такой элемент. Метод северо-западного угла. Просматривается матрица тарифов перевозок C, начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клетки оставшейся матрицы и так до тех пор пока весь запас товаров не будет исчерпан.

Метод Фогеля приводит к лучшему начальному решению, чем два других метода. Однако он сложен для реализации на ЭВМ, так включает в себя множественные проверки, а также метод наименьшего расстояния. Несмотря на то, что метод наименьших расстояний дает лучшее начальное решение, чем метод «северо-западного» угла, он также сложен из-за большего числа различных проверок и постоянного определения минимума. Метод северо-западного угла наиболее прост, так базисное решение получается путем последовательного перехода по столбцам и строкам. Кроме этого стоит учитывать, что алгоритм выбора начального базисного решения не влияет на алгоритм поиска оптимального решения, то есть в любом случае дальнейшее решение задачи происходит по одной и той же схеме. Исходя из этого, при программной реализации задачи для поиска начального решения был выбран метод «северо-западного» угла. Даже если при этом потребуется большее количество итераций для поиска оптимального решения, более выгодно использовать этот метод, так как в этом случае возрастает точность решения, при этом структура программы будет заметно проще.

2.3 Нахождение оптимального решения задачиТак как не известно: оптимален ли полученный опорный план или нет, то стоит провести оценки базисных и небазисных переменных. Для этого воспользуемся методом потенциалов.

В этом методе строке i и столбцу j ставятся в соответствие числа Ui и Vj. Для каждой базисной переменной Хij текущего решения потенциалы Ui и Vj должны удовлетворять условию:


Виды моделей транспортной задачи

Транспортная задача

Рассмотрим так называемую транспортную задачу по критерию стоимости.

Решение транспортных задач линейного программирования

Данная задача используется для оптимизации планирования грузоперевозок.

Постановка задачи

1. В m пунктах отправления , которые будем в дальнейшем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим .

Однородный – одного вида (например: пищевые продукты, одежда, обувь, ткани).

2. Данный продукт потребовался в n пунктах , которые будем называть потребителями. Объем потребителя обозначим .

3. Известны расходы на перевозку единицы продукта из пункта в пункт , которые равны и приведены в матрице транспортных расходов .

4. Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором

1) весь продукт вывозится из пунктов в пункты в соответствии с потребностью

2) общая величина транспортных издержек будет минимальной.

Обозначим количество продукта, перевозимого из пункта в пункт через . Тогда получим матрицу перевозок .

А также матрицу стоимости перевозок (иногда ее называют «матрицей тарифов»)

Тогда целевая функция задачи имеет вид

(1)

а ограничения выделяют следующим образом:

(2)

(Условие по потребности)

(3)

(Условие по запасам)

(4)

Необходимым и достаточным условием того чтобы задача имела решение, является условие баланса:

(5)

Транспортная задача, в которой имеет место равенство (5) называется закрытой.

Решение транспортной задачи состоит из 2-х этапов:

1) Нахождение первоначального опорного плана.

2) Нахождение оптимального плана перевозок по методу потенциалов.

 

Виды моделей транспортной задачи

Модель транспортной задачи включает в себя: целевую функцию (1) и систему ограничений (2), (3) и (4).

Модель транспортных задач бывает 2-х типов.

1. Закрытая модель .

Для того чтобы решать транспортную задачу ее необходимо привезти к закрытому виду.

Для закрытых моделей доказана теорема о существовании допустимого плана.

Теорема. Для того чтобы транспортная задача имела допустимые планы необходимо и достаточно, чтобы объем запасов совпадал с объемом потребностей.

2. Открытые модели:

2а) Запасы превышают потребности

В этом случае вводится фиктивный потребитель , потребности которого равны . Стоимость перевозки единицы груза от поставщиков к -му потребителю равна 0.

2б) Потребности превышают запасы

В этом случае вводится фиктивный поставщик . Запасы которого равны .

 

Построение первоначального опорного плана

В транспортной задаче существуют понятия вырожденного и невырожденного плана.

План невырожденный, когда количество занятых клеток равно , где m – число поставщиков, n – число потребителей.

План вырожденный, когда количество занятых клеток .

Если план оказывается вырожденным, то следует часть свободных клеток условно считать занятыми. Для этого в них реально записываются нули, которые стоят там «негласно». Это делают в одной или нескольких клетках, исходя из требования, состоящего в том, что общее число занятых клеток должно быть . В дальнейшем с другими клетками обращаются как с занятыми.

 

 



Дата добавления: 2016-09-06; просмотров: 137 | Нарушение авторских прав


Похожая информация:



Поиск на сайте:





Добавить комментарий