При оформлении задания в MS Word - установить параметры листа (для этого задания): ориентация – альбомная.

Методические указания по выполнению задания 4:

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

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

Транспортная задача по критерию стоимости формулируется следующим образом:

В m пунктов отправления А₁, А₂, …, А_m находится а₁, а₂, …, а_m единиц однородного груза, который должен быть доставлен в n пунктов потребления В₁, В₂, …, В_n в количестве b₁, b₂, …, b_n. Известны транспортные издержки c_ij перевозок единицы груза из i -ого пункта отправления в j -тый пункт потребления. Требуется составить план перевозок, то есть найти, сколько единиц груза должно быть отправлено из i -того пункта отправления в j -тый пункт потребления, чтобы полностью удовлетворить потребности и получить минимальные суммарные издержки.

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

В таблице указаны x_ij (i = 1, …, m, j = 1, …, n), x_ij ³ 0 – число единиц груза, перевозимого из i -того пункта поставки А_i в j -тый пункт потребления В_j; a_i – запасы груза i -того поставщика А_i (a_i ³ 0); b_j – потребности в грузе потребителя В_j (b_i ³ 0); c_ij – издержки или тарифы.

Планом транспортной задачи называется матрица m*n: X= (x_ij)_m*n.

В дальнейшем план задачи будет строиться непосредственно в таблице (матрице) перевозок.

Матрицей тарифов или издержек называется матрица D = (c_ij)_m*n.

Суммарная стоимость перевезенного груза определяется целевой функцией

Z = c₁₁x₁₁ + c₁₂x₁₂ + … + c_1nx_1n + … + c_m1x_m1 + c_m2x_m2 + … +c_mnx_mn = c_ij x_ij (1)

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

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

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

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

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

Теорема 2. Ранг матрицы системы ограничений транспортной задачи на единицу меньше числа уравнений, то есть

Тогда неизвестные будут базисными, а остальные будут свободными и, следовательно, равными нулю.

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

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

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

1) на одной строке или на одном столбце могут располагаться только две вершины цикла;

2) начальная точка или вершина цикла находится на той же строке, что и конечная;

3) если исходный план содержит циклы, то он не является опорным;

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

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

1) Метод северо-западного угла. В этом методе не обращая внимания на тарифы, начинаем заполнять таблицу перевозок с левого верхнего угла. В клетку (1,1) поместим груз х₁₁=min(a₁,b₁).

Если окажется, что a₁>b₁, тогда х₁₁=b₁. В этом случае потребности первого потребителя будут полностью удовлетворены и первый столбец исключается из рассмотрения, т.е. x_i1=0, i=1,2,…m. Далее переходим в клетку (1,2). Помещаем туда груз x₁₂=min(a₁-b₁, b₂). В зависимости от того, какое из чисел будет больше, переходим либо к заполнению клетки (1,3), либо (2,2) и т.д. Если a₁<b₁, то х₁₁=a₁, тогда запасы поставщика А₁ полностью исчерпаны и первая строка исключается из дальнейшего рассмотрения. Переходим к рассмотрению клетки (2,1), в которую помещаем груз x₂₁=min(a₂, b₁- a₁). Затем переходим к летке либо (3,1), либо (2,2).

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

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

2) Метод минимального элемента. В таблице перевозок находится клетка, соответствующая минимальному тарифу с_ij. В эту клетку помещают груз х_ij=min(a_i,b_j). Если a_i>b_j, то x_ij = b_j, тогда потребности потребителя B _j полностью удовлетворены и j -й столбец полностью исключается из рассмотрения. В оставшейся части таблицы снова находят клетку с наименьшим тарифом и снова помещают туда максимально возможный груз, который определяется как минимум между поставщиком и потребителем.

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

Одним из способов проверки плана на оптимальность является Метод потенциалов.

Суть этого метода состоит в том, что всем поставщикам A_i ставятся в соответствие числа u_i, называемые потенциалами поставщиков, а всем потребителям B_j ставятся в соответствие числа v_j – потенциалы потребителей. Затем для заполнения клеток составляется система уравнений u_i + v_j = с_ij. Всего уравнение с переменными.

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

Далее находят косвенные тарифы незаполненных пустых клеток по найденным u_i и v_j: с_ij^’ = u_i + v_j и сравнивают косвенные тарифы с тарифами перевозок. Составляют разности, называемые оценками S_ij = с_ij - с_ij^’. Если получится, что все оценки неотрицательные, то план будет оптимальным, а значение целевой функции, соответствующее этому плану будет минимальным.

Если среди оценок есть отрицательные, то план не оптимальный. Для улучшения плана в этом случае желательно включить в план ту клетку, для которой получается минимальная отрицательная оценка.

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

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

В обоих случаях открытую транспортную задачу преобразуют в закрытую. Если , то вводят фиктивного потребителя, для которого , тогда .

В этом случае в матрице перевозок появляется столбец. При этом тарифы перевозки грузов этому фиктивному потребителю считают равными нулю.

Если , то вводят фиктивного поставщика, для которого , тогда .

В этом случае в матрице перевозок появляется строка. При этом тарифы перевозки грузов этому фиктивному поставщику также считают равными нулю.