Особенности транспортной задачи

 

1. Транспортная задача – это задача линейного программирования, записанная в канонической форме

2. Все коэффициенты ограничений транспортной задачи равны 0 или 1.

3. Всякая переменная входит только в два уравнения системы ограничений: в i-е уравнение системы (1) и в j-е уравнение системы (2).

4. Число переменных x_ij в задаче равно (mn).

5. Число ограничений в ТЗ равно (m + n).

6. Если сложить почленно все уравнения системы (1) и все уравнения системы (2), то получатся два одинаковых уравнения. Это значит, что уравнения системы ограничений являются линейно зависимыми. Одно из них можно выразить через другие. Ранг матрицы ограничений n+m-1, опорный план ТЗ содержит n+m-1 отличную от нуля компоненту.

Если опорный план ТЗ содержит (n + m – 1) не равный нулю компонент, то опорный план называется невырожденным, если меньше (m + n – 1) - вырожденным.

 

Определение опорного плана ТЗЛП

Как и в симплекс методе, решение задачи транспортной задачи линейного программирования осуществляется в 2 этапа:

1) Построение первоначального опорного плана ТЗ.

2) Его улучшение.

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

Рассмотрим 2 метода определения ОП ТЗ.

 

Метод северо-западного угла

Заполнение клеток начинается с левой верхней клетки таблицы («северо-западный угол») и заканчивается заполнением клетки (правой нижней).

Пример:

C=180*5+10*4+190*7+10*4+140*6+20*8+100*5=3810

 

Пункты отправления	Пункты назначения
B1	B2	B3	B4
A1
A2
A3
A4
Потребности

 

Замечание: Если на каждом шаге определяется перевозка , а при этом , то , вычеркивается либо строка k, либо столбец l, а в следующую заполняемую клетку помещается нулевая перевозка, и эта клетка считается занятой. При этом нулевая перевозка помещается в ту из соседних клеток, которой соответствует минимальный тариф.

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

 

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

На каждом шаге выбирается для заполнения клетка, имеющая минимальный тариф. Если таких клеток несколько, то выбирается любая из них.

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

Пример:

C=70*3+120*2+20*4+100*7+80*4+160*3+100*3=2330

 

 

Пункты отправления	Пункты назначения
B1	B2	B3	B4
A1			(4 шаг) 3	(1 шаг) 2
A2	(5 шаг) 4	(7 шаг) 7	(6 шаг) 4
A3	(2 шаг) 3
A4		(3 шаг) 3
Потребности

 

Метод потенциалов получения опорного плана транспортной задачи

 

Рассмотрим транспортную задачу и запишем к ней двойственную. Для этого каждому ограничению прямой задачи поставим в соответствие двойственную переменную. При этом двойственные переменные, соответствующие ограничениям (1), обозначим через u_i, а соответствующие (2) - v_j. Тогда

Числа u_i и v_j называют потенциалами соответственно пунктов отправления и назначения. Для того, чтобы план исходной задачи был оптимален, необходимо:

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

2). , , т.е. для свободной клетки сумма потенциалов меньше или равна тарифу.

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

 

Алгоритм метода потенциалов:

1). Построение первичного опорного плана.

2). Определение потенциалов пунктов отправления (u_i) и пунктов назначения (v_j).

Потенциалы находят из системы уравнений u_i + v_j = C_ij, где C_ij - тарифы, стоящие в заполняемых клетках таблицы. Число переменных в этой системе равно m + n, число уравнений (m + n – 1). Для нахождения решения системы один из потенциалов приравнивается произвольному числу (например, u₁=0) и последовательно находятся значения всех остальных потенциалов.

3). Проверка оптимальности плана.

Проверяем условия (2): . Вычисляем - оценки свободных переменных для оптимального базиса. Если все , то получаемый план является оптимальным, иначе - к шагу 4.

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

. Если таких клеток несколько, то для заполнения выбирается клетка, имеющая минимальный тариф.

5). Построение цикла пересчета для выбранной свободной клетки i₀ j₀.

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

После построения цикла его вершины последовательно отмечаются знаками “+” и “-”, причем свободной клетке приписывается знак “+”.

6). Определение величины перераспределения груза.

, где x_ij - перевозки, стоящие в вершинах цикла, отмеченных знаком “-”. Клетку, которой соответствует d, обозначим через i₁ j₁.

7). Сдвиг по циклу пересчета (перераспределение грузов).

В выбранную для заполнения свободную клетку (i₀,j₀) заносится значение d. Одновременно это число прибавляется к значениям перевозок, стоящих в клетках со знаком “+”, и вычитается из значений перевозок, стоящих в клетках со знаком “–”. Т.о. клетка (i₀, j₀) становится занятой, а i₁ j₁ - свободной.

Замечание: при сдвиге по циклу пересчета число занятых клеток остается const = n + m – 1. Если d соответствует нескольким клеткам таблицы, то освобождают одну из них, а в остальные записываются нулевые перевозки и считают их занятыми. Нулевые перевозки записываются и в клетки, которые имеют меньшие тарифы.

8). Переход к шагу 2.

Замечание: если при построении двойственной задачи, одну двойствен­ную переменную обозначают через u_i, а другую через v_j, то условие оптимальности:

 

Пример:

 

B1	B2	B3	B4
A1		+ 4	– 3
A2		– 7	+ 4
A3
A4

 

- занят.

 

B1	B2	B3	B4
A1		+ 4		– 2
A2		– 7		+ 4
A3
A4

 

 

B1	B2	B3	B4
A1
A2
A3
A4

Пересчитав u, v и D, получим, что это оптимальный план ( <0).

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

 

Прикладные задачи транспортного типа.

 

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

 

1. Задача выбора (задача о назначениях)

Имеется n исполнителей и n видов работ, которые они могут выполнять. - производительность i-го исполнителя при выполнении j работы. Каждый исполнитель может выполнять один вид работ, каждая работа может быть выполнена одним исполнителем. Требуется таким образом распределить исполнителей по видам работ, чтобы общая производительность была максимальной.

Введем переменные , где , если i-й исполнитель назначен на j-работу, - иначе.

Модель:

Иногда задача о назначениях формулируется как целочисленная (т.е. добавляется условие x_ij = 1 или x_ij = 0). Однако это требование излишне, т.к. если а_iи b_iцелочислены "i, j, то opt план ТЗ тоже будет целочисленным.

Иногда задача о назначениях формулируется как задача минимизации, если в качестве используется время, затраченное i-тым исполнителем на выполнении j-той работы.

Если рассматривается задача максимизации, то, умножив целевую функцию на (–1), переходим к обычной ТЗ.

Иногда используется следующий метод: в каждой строке находится максимальная производительность и приравнивается к 0.

.

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

Примеры задач о назначениях:

Ø закрепление исполнителей за видами работ;

Ø закрепление за станками операций по обработке деталей;

Ø назначение претендентов на вакантные места при составлении штатного расписания.

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

Пусть имеется m групп лиц A_i (i = 1,…, m) по a_i человек в каждой и n категорий работ B_j (j = 1,…, n) по b_j единиц в каждой. Известна производительность C_ij лица i-той группы при выполнении j-той категории работ. Необходимо определить, сколько лиц из каждой группы и на какую категорию работ назначить, чтобы суммарная производительность была максимальной.

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

Предполагается, что .

Если , вводят фиктивную группу лиц, если наоборот – фиктивную категорию работ.

 

Пример. Задача планирования, подготовки и распределения кадров.

Пусть b₁ … b_n – вакантные должности, а₁ … а_m – категории специалистов различных профилей, подлежащих распределению.

Пригодность специалиста i-того профиля при назначении его на должность j обозначим числом C_ij. Тогда модель – см. выше.

x_ij – количество выпускников специальности i, планируемое на замещение должности j.

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

 

2. Распределительная задача

В моделях ТЗ речь шла о перевозке однородного продукта. Естественно, что на практике чаще возникает задача перевозки ряда продуктов. Если рассматриваемые продукты качественно совершенно различны (например, уголь, цемент, сахар), то задача определения opt плана перевозок распадается на ряд обычных ТЗ (по углю, цементу, сахару).

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

Задачи оптимального распределения взаимозаменяемых ресурсов получили название распределительных задач.

Постановка задачи. Найти оптимальное распределение m различных взаимозаменяемых ресурсов, имеющихся в количествах а₁ … а_m для удовлетворения n различных потребностей b₁ … b_n при заданных значениях C_ij – оценки использования i-того ресурса на удовлетворение j-х потребностей; l_i – количество единиц j-х потребностей, которые удовлетворяются единицей i-х ресурсов.

Тогда модель:

Здесь x_ij – количество единиц i-х ресурсов, используемых для удовлетворения j-х потребностей.

Если через x_ij обозначить количество единиц j-х потребностей, которые обеспечиваются ресурсами i-того вида, то получится эквивалентная модель:

где – количество единиц i-того ресурса, необходимого для удовлетворения единицы j-х потребностей. C_ij – оценки единицы j-х потребностей, которые обеспечиваются i-ми ресурсами.