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

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

Симплекс-метод решения задачи линейного программирования является универсальным и применим для решения любых таких задач. Однако существуют некоторые частные типы задач линейного программирования, которые, в силу некоторых особенностей своей структуры, допускают решение более простыми методами. К ним относится, в частности, так называемая транспортная задача.

Классическая транспортная задача линейного программирования формулируется следующим образом.

Имеется m пунктов отправления: А1, А2, . Am, в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно a1, a2, . am единиц. Кроме того, имеется n пунктов назначения: B1, B2, . Bn, подавших заявки соответственно на b1, b2, . bn единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов:

(3.28)

Известна стоимость cij перевозки единицы товара от каждого пункта отправления Ai до каждого пункта назначения Bj. Таблица (матрица) стоимостей перевозки сij задана:

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

При такой постановке задачи показателем эффективности плана перевозок является стоимость; поэтому поставленную задачу точнее называюттранспортной задачей по критерию стоимости.

Дадим этой задаче математическую формулировку. Обозначим xij — количество груза, отправляемого из i-го пункта отправления Аi в j-й пункт назначения Вj (i = 1, . m; j = 1, . n). Неотрицательные переменные x11, x12, . xmn (число которых, очевидно, равно mxn) должны удовлетворять следующим условиям:

1. Суммарное количество груза, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это даст нам m условий-равенств:

x11 + x12 + . + x1n = a1, x21 + x22 + . + x2n = a2, . xm1 + xm2 + . + xmn = am,
(3.29)

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

x11 + x21 + . + xm1 = b1, x12 + x22 + . + xm2 = b2, . x1n + x2n + . + xmn = bn,
(3.30)

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

или, гораздо короче,

(3.31)

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов (i = 1, . m; j = 1, . n), т.е. по всем комбинациям пунктов отправления с пунктами назначения.

Функция (3.31) линейна, ограничения — равенства (3.29), (3.30) также линейны. Перед нами — типичная задача линейного программирования с ограничениями-равенствами (ОЗЛП).

Как и всякую другую задачу линейного программирования, ее можно было бы решить симплекс-методом, но данная задача имеет некоторые особенности, позволяющие решить ее более просто. Причиной является то, чтовсе коэффициенты при переменных в уравнениях (3.29), (3.30) равны единице. Кроме того, имеет значение структура связей между условиями. Нетрудно убедиться, что не все m+n уравнений нашей задачи являются независимыми. Действительно, складывая между собой все уравнения (3.29) и все уравнения (3.30), мы должны получить одно и то же, в силу условия (3.28). Таким образом, условия (2), (3) связаны одной линейной зависимостью, и фактически из этих уравнений только m+n-1, а не m+n являются линейно независимыми. Значит, ранг системы уравнений (3.29), (3.30) равен

а, следовательно, можно разрешить эти уравнения относительно m+n-1 базисных переменных, выразив их через остальные, свободные.

Подсчитаем количество свободных переменных. Оно равно:

Мы знаем, что в задаче линейного программирования оптимальное решение достигается в одной из вершин ОДР, где по крайней мере(m-1) (n-1) значений xij должны быть равны нулю.

Условимся о терминологии. Значения xij количества единиц груза, направляемых из пункта Ai в пункт Bj мы будем называть перевозками.

Любую совокупность значений (xij) (i = 1. m; j = 1. n) будем называть планом перевозок, или просто планом.

План (xij) будем называть допустимым, если он удовлетворяет условиям (3.29), (3.30) (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны.

Допустимый план будем называть опорным, если в нем отличны от нуля не более r = m+n-1 базисных перевозок xij, а остальные перевозки равны нулю.

План (xij) будем называть оптимальным, если он, среди всех допустимых планов, приводит к наименьшей стоимости всех перевозок.

Перейдем к изложению методов решения транспортной задачи (ТЗ). Эти методы не требуют манипуляций с симплекс-таблицами, а сводятся к более простым операциям непосредственно с таблицей, где в определенном порядке записаны все условия ТЗ. Такую таблицу мы будем называть транспортной таблицей.

В транспортной таблице записываются

— пункты отправления и назначения,

— запасы, имеющиеся в пунктах отправления,

— заявки, поданные пунктами назначения,

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

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

Образец транспортной таблицы дан в табл.3.8.

Для краткости в дальнейшем будем обозначать пункты отправления — ПО, пункты назначения — ПН. В правом верхнем углу каждой клетки проставлены стоимости перевозки единицы товара (груза) из ПО Аi в ПН Bj. В правом столбце помещены запасы товара в каждом ПО, в нижней строке — заявки, поданные каждым ПН. Для ТЗ сумма запасов равна сумме заявок; общее значение этой суммы записывается в правой нижней ячейке таблицы.

ПН ПО B1 B2 . Bn Запасы аi
A1 C11 C12 . C1n a1
A2 C21 C22 . C2n a2
: : . . . . : :
Am Cm1 Cm2 . Cmn am
Заявки bj b1 b2 . bn

Выше мы показали, что ранг системы уравнений-ограничений ТЗ равен r = m+n-1, где m — число строк, а n — число столбцов транспортной таблицы. Значит, в каждом опорном плане, включая оптимальный, будут отличны от нуля не более, чем m+ n-1 перевозок.

Ячейки (клетки) таблицы, в которых мы будем записывать эти отличные от нуля перевозки, условимся называть базисными, а остальные (пустые) свободными.

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

— сумма перевозок в каждой строке таблицы должна быть равна запасу данного ПО;

— сумма перевозок в каждом столбце должна быть равна заявке данного ПН;

— общая стоимость перевозок — минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной таблицы 3.8.

При описании этих преобразований нам удобно будет пользоваться нумерацией клеток таблицы (подобной нумерации клеток шахматной доски). Клеткой (Аi,Bj) или, короче, клеткой (i,j) мы будем называть клетку, стоящую в i-й строке и j-м столбце транспортной таблицы. Например, самая верхняя левая клетка будет обозначаться (1,1), стоящая под ней (2,1) и т.д.

Читайте также:  Pubg mobile официальный эмулятор 4pda

3.5.2. Нахождение опорного плана

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения, или, как мы будем говорить, опорного плана. В отличие от общего случая ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует.

Построение опорного плана.

Воспользуемся так называемым «способом северо-западного угла». Пояснить его проще всего будет на конкретном примере.

Пример 1. Условия ТЗ заданы транспортной таблицей (см. табл.3.9)

ПН ПО B1 B2 В3 B4 В5 Запасы аi
A1
A2
А3
A4
Заявки bj

Требуется найти опорное решение ТЗ (построить опорный план).

Перепишем табл.2 и будем заполнять ее перевозками постепенно, начиная с левой верхней ячейки (1,1) («северо-западного угла» таблицы). Будем рассуждать при этом следующим образом. Пункт B1 подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте А1, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1 удовлетворена, а в пункте А1 осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта В2 (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3 В составе заявки пункта В3 остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А2, чем его запас будет исчерпан, и еще 9 возьмем из пункта А3. Из оставшихся 18 единиц пункта А3 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 покроет заявку (см. табл.3.10).

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

Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является не только допустимым, но и опорным решением транспортной задачи.

ПН ПО B1 B2 В3 B4 В5 Запасы аi
A1
A2
А3
A4
Заявки bj

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию r = m+n — 1 = 8. Остальные клетки — свободные (пустые), в них стоят ненулевые перевозки, их число равно (n — 1)(m — 1) = 12. Значит, наш план — опорный и поставленная задача построения опорное плана решена.

Последнее изменение этой страницы: 2017-02-08; Нарушение авторского права страницы

1. Постановка задачи и ее математическая модель 3

2. Модели транспортной задачи 7

2.1. Закрытая модель транспортной задачи 7

2.2. Открытая модель транспортной задачи 8

3. Определение оптимального и опорного плана транспортной задачи

4. Методы определения первоначального опорного плана 12

4.1. Метод минимального элемента 12

4.2. Метод аппроксимации Фогеля 14

5. Методы определения оптимального плана 16

5.1. Венгерский метод 16

5.2. Метод потенциалов 17

Список использованной литературы 19

Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования — задачи о назначениях, сетевые, календарного планирования.

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

1. Постановка задачи и ее математическая модель

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi …, Аm, в которых сосредоточены запасы однородных продуктов в количестве a1, . аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1, . Вm, потребность которых в указанных продуктах составляет b1, . bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта
Ai в пункт Вj, i [pic]1, …, m; j [pic]1, . n. Предположим, что
[pic] т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

Пусть хij — количество единиц продукта, поставляемого из пункта Аi в пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:
[pic] (1)
Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что
[pic], i [pic]1, …, m (2)
Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие полного удовлетворения спроса:
[pic], j [pic]1, …, n (3)
Объемы перевозок — неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены: xij [pic]0, i [pic]1, . m; j [pic]1, . n (4)

Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.
Определение 1.
Всякое неотрицательное решение системы линейных уравнений
[pic], j [pic]1, …, n и [pic], i [pic]1, …, m, определяемое матрицей X=(xij)(i [pic]1, …, m; j [pic]1, . n), называется планом транспортной задачи.

Определение 2.
План X*=(x*ij)(i [pic]1, …, m; j [pic]1, . n), при котором функция
[pic] принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные записываются в виде таблицы 1.

Таблица 1.
|Пункты отправления|Пункты назначения |Запасы |
| |В1 |… |Bj |… |Bn |А1 |
|A1 |C11 |… |C1j |… |C1n |a1 |
| |X11 | |X1j | |X1n | |
|… |… |… |… |… |… |… |
|Ai |Ci1 |… |Cij |… |Cin |ai |
| |Xi1 | |Xij | |Xin | |
|… |… |… |… |… |… |… |
|Am |Cm1 |… |Cmj |… |Cmn |am |
| |Xm1 | |Xmj | |Xmn | |
|Потребности |b1 |… |bj |… |bn | |

Очевидно, общее наличие груза у поставщиков равно [pic], а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.
[pic], (5) то модель такой транспортной задачи называется закрытой.
В ряде случаев не требуется, чтобы весь произведенный продукт в каждом пункте производства был реализован. В таких случаях баланс производства и потребления может быть нарушен:
[pic], i [pic]1, . m.
Введение этого условия приводит к открытой транспортной модели.
Теорема 1.
Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

Читайте также:  Как напечатать картинку нужного размера

2. Модели транспортной задачи

2.1. Закрытая модель транспортной задачи

Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть [pic]= M > 0[pic].

Тогда величины xij = aibj /M (i = 1,2,3, . m; j = 1,2,3, . n) являются планом, так как они удовлетворяют системе ограничений
( 2 ) и ( 3 ) .
Действительно, подставляя значения в (2) и (3) , находим

[pic] = bj .
Выберем из значений Cij наибольшее C( = max Cij и заменим в линейной функции ( 1 ) все коэффициенты на C( тогда, учитывая ( 2 ) , получим

[pic],
Выберем из значений Cij наименьшее C((=min Cij и заменим в линейной функции все коэффициенты на C(( ; тогда, учитывая ( 2 ) имеем
[pic]
Объединяя два последних неравенства в одно двойное , окончательно получаем
C((M ( Z ( C( M, т. е. линейная функция ограничена на множестве планов транспортной задачи.

2.2. Открытая модель транспортной задачи

Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие [pic], называется открытой. Для открытой модели может быть два случая: a) суммарные запасы превышают суммарные потребности [pic]; b) суммарные потребности превышают суммарные запасы [pic].
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции
[pic] при ограничениях
[pic], i = 1, 2, . m, (случай а)
[pic], j = 1, 2, . n;
[pic], i = 1, 2, . m, (случай б)
[pic], j = 1, 2, . n, xij ( 0 (i = 1, 2, . m; j = 1, 2, . n).
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 = [pic]. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 = [pic].
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.

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

3. Определение оптимального и опорного плана транспортной задачи

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

Число переменных Xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше — то выраженным.

Для определения опорного плана существует несколько методов. Три из них — метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля — рассмотрены ниже.

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

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них — метод потенциалов и Венгерский метод — рассматриваются ниже.

4. Методы определения первоначального опорного плана

4.1. Метод минимального элемента

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел
[pic]и [pic]. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Пример

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
|2 |3 |4 |15|
|11|6 |10|1 |
|8 |9 |3 |3 |
|4 |1 |2 |21|
|10|20|10| |

Решение:
Задача сбалансирована.
Строим первоначальный опорный план методом минимального элемента.

1. Выясним минимальную стоимость перевозок. [pic]Первая перевозка будет осуществляться с пункта производства [pic]в пункт потребления [pic]и она составит максимально возможное число единиц продукта [pic]:. В этом случае, потребности пункта потребления [pic]будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки [pic].Выясним минимальную стоимость перевозок (без учета столбца № 2).

2. [pic]Вторая и третья перевозки будут осуществляться с пункта производства [pic]и [pic]в пункт потребления [pic]и

[pic]соответственно и составят максимально возможное число единиц продукта : [pic], [pic];

4. Четвертая перевозка осуществляется с пункта [pic]в пункт потребления

[pic], т.к. [pic](без учета первого, второго столбца и четвертой строки). [pic].

Читайте также:  Как поменять черный фон на белый

5. Пятая перевозка осуществляется с пункта [pic]в пункт потребления

[pic], т.к. [pic](без учета первого, второго столбца, третьей и четвертой строки). [pic].

6. Шестая перевозка осуществляется с пункта [pic]в пункт потребления

[pic]т.к. [pic](без учета первого, второго столбца, первой, третьей и четвертой строки).

[pic]
Опорный план имеет вид;
|10|5 |0 |
|0 |1 |0 |
|0 |3 |0 |
|0 |11|10|

4.2. Метод аппроксимации Фогеля

При определении опорного плана транспортной задачи методом аппроксимации
Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.
Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.
Если минимальная стоимость одинакова для нескольких клеток столбца
(строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).
Пример
Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:
(Здесь мы перенесли потребности в верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента
Решение:
|2 |2 |2 |
|2 |2 |2 |
|2 |- |2 |
|- |- |2 |
|- |- |- |

Опорный план имеет вид:
|7|0 |8|
|0|1 |0|
|3|0 |0|
|0|19|2|

5. Методы определения оптимального плана

5.1. Венгерский метод

Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план перевозок, не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0
(xij[0])m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

Если эти условия являются равенствами, то матрица Хo — решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk (xij[0])m,n. Близость этой матрицы к решению задачи характеризует число Dk — суммарная невязка матрицы Хk:

В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl — оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю.
Соответствующая матрица Хk является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 — суммарная невязка подготовительного этапа).

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

5.2. Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам
Аi соответствуют числа ui, пунктам Bj — числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij — стоимости перевозки единицы продукции между пунктами Аi и Вj:

vj[k] – ui[k] Cij, i 1, . m; j 1, …, п.

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

Список использованной литературы

1. Е. Г. Гольштейн, Д. Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 1993.

2. И. Л. Акулич, В. Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2000.

Репетиторство

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

Цель работы: научиться решать транспортные задачи и задачи

распределения ресурсов в среде MS Excel

1. Изучение видов транспортной задачи и методов её решения.

2. Изучение видов распределительной задачи и методов её решения.

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

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

Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

Пример 1. Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: первый- 120 условных единиц, второй- 100 и третий 80 единиц. Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и 120 условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i-го пункта отправления в j-й пункт потребления.

Требуется перевезти продукт с минимальными затратами.

Ссылка на основную публикацию
Adblock detector