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

2. Двухиндексные задачи линейного программирования. Стандартная транспортная задача (тз).

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

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

Исходные параметры модели тз

  1. m – количество пунктов отправления, n – количество пунктов назначения.
  2. ai – запас продукции в пункте отправления Ai (i =1,m) [ед. тов.].
  3. bj – спрос на продукцию в пункте назначения Bj ( j =1,n) [ед. тов.].
  4. cij – тариф (стоимость) перевозки единицы продукции из пункта отправления Ai в пункт назначения Bj [руб./ед. тов.].

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

Составим таблицу затрат (табл. 1.1) таким образом, чтобы в ней фигурировали все издержки по перевозке единицы про­дукции от поставщика Аi к потребителю Bj. Эту таблицу назы­вают матрицей транспортных расходов:

По аналогии составляем матрицу неизвестных, где хij — это количество единиц продукции, доставляемой постав­щиком Ai потребителю Bj (табл. 2).

Читайте также:  Верстка документа adobe indesign

Объединим обе матрицы, поместив данные матрицы транс­портных расходов в верхнем правом углу каждой клетки, а не­известные— в центре каждой клетки (табл. 1.3).

Такую таблицу обычно называют матрицей (или планом) перевозок, а числа xij— перевозками.

К табл. 1.3 добавим снизу еще одну строку, где запишем числа, характеризующие потребность каждого потребителя, а справа—еще одни столбец, в котором будем указывать нали­чие продукции у поставщиков. В результате имеем новую таблицу (табл. 1.4), которая включает все условия и все неизвестные задачи. В клетке, расположенной на пересече­нии последней строки с последним столбцом и разделенной по диагонали, определим наличие баланса. Для этого подсчитаем наличие продукции у поставщиков, которая будет равна сумме всех данных последнего столбца, и потребность в этой продук­ции потребителей, равную сумме всех данных последней строки. Если обе суммы окажутся равными, то уравнение ба­ланса выполняется и задача разрешима.

Количество единиц продукции в пунктах назначения

Количество единиц продукции в пунктах потребления

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

Исходная таблица (табл. 1.5) до ее заполне­ния должна иметь такой же вид, что и таблица условий (см. табл. 1.4); свободными в ней должны быть середины клеток.

Количество единиц продукции в пунктах назначения

Количество единиц продукции в пунктах потребления

  1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей Х=(хij) называется допустимым планом транспортной задачи.
  2. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т.е. равен (m+n-1). Следовательно, число линейно независимых уравнений равно (m+n-1), они образуют базис, а соответствующие им (m+n-1) переменные будут являться базисными.
  3. Допустимый план базисной задачи, имеющий не более (m+n-1) отличных от нуля величин хij называется опорным.
  4. Если в опорном плане число отличных от нуля компонент равно в точности (m+n-1), то план является невырожденным, если меньше, то план называется вырожденным.
  5. План Х=(хij), при котором функция (1.4) принимает свое минимальное значение, называется оптимальным планом ТЗ.
  6. Для решения ТЗ необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения:
  1. Модель ТЗ, удовлетворяющая условию (1.6), называется закрытой. Если указанное условие не выполняется, то модель называется открытой.

В случае превышения запаса над заявками

Вводится фиктивный (n+1) пункт назначения с потребностью

При вводится фиктивный (m+1) пункт отправления с запасом груза и соответствующие тарифы принимаются равными нулю: сm+1,j=0, .

  1. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф — если задача поставлена на максимум целевой функции.
  1. При построении исходного опорного плана задачи (или, как его еще называют, первоначальной матрицы перевозок) исполь­зуют различные методы, например метод северо-западного угла, который состоит в заполне­нии табл. 5 в направлении от левого верхнего угла к пра­вому нижнему.

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

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

План Х=(хij) ТЗ будет являться оптимальным, если существует система m+n чисел i, j называемых потенциалами, удовлетворяющая условиям:

Потенциалы означают оплату за перевозку единицы груза в пунктах отправления и назначения соответственно, поэтому их сумма равна транспортному тарифу i+j=cij.

Введем обозначение оценки свободной клетки таблицы

Если среди оценок ij нет положительных (задача поставлена на минимум), то опорный план считается оптимальным.

Алгоритм оценки оптимальности плана методом потенциалов включает следующие этапы:

  1. Построение первого опорного плана;
  2. Проверка вырожденности плана. Потенциалы могут быть только рассчитаны для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (m+n-1), то не хватит количества уравнений для определения потенциалов , поэтому вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n-1). Нуль вводят в клетку с наименьшим тарифом, например в клетку одновременно вычеркиваемых строки и столбца таблицы при составлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы.
  3. Определение значения функции цели .
  4. Проверка условия оптимальности. Определяем потенциалы. Для каждой занятой клетки таблицы записываем уравнение i+j=cij. Получим систему (m+n-1) уравнений с (m+n) переменными. Так как число переменных больше числа уравнений (m+n>m+n-1), то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов задают произвольное значение, например, 1=0. В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы.

Определяем оценки свободных клеток ij.

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

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

  • вершины ломаной лежат в центрах клеток матрицы, при­чем только одна вершина расположена в свободной клетке, а остальные в базисных;
  • звенья ломаной располагаются параллельно либо стро­кам, либо столбцам матрицы;
  • в каждой вершине пересекаются только два звена;
  • никакие три вершины не лежат на одной прямой;
  • вершина, лежащая в свободной клетке матрицы, счита­ется положительной, и около нее ставится знак «+»;
  • все остальные вершины получают знак « + » или «—» с таким расчетом, чтобы любые две соседние вершины имели разные знаки.

Например, если базисные клетки матрицы отметить круж­ками, а остальные оставить свободными, то ломаные линии, изображенные на рис. 1,а-в, являются циклами пересчета, так как удовлетворяют всем шести перечисленным выше усло­виям.

Ломаная, изображенная на рис. 1, г, не является циклом пересчета, так как она не замкнута.

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

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

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

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее – х. В свободную вершину цикла запишем число х, на которое осуществляем сдвиг; выберем направление пересчета, например по часовой стрелке от свободной вершины цикла; двигаясь вдоль вершин цикла в указанном направлении, прибавляем поочередно к числам, расположенным в положи­тельных вершинах, (+х), а к числам, расположенным в отри­цательных вершинах цикла, (-х).

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

Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения хij, то при распределении груза план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем причем предпочтение отдается клетке с наименьшим тарифом. Нулей вводится столько, чтобы во вновь полученном плане число занятых клеток было равно (m+n-1).

Значение целевой функции на каждой итерации можно рассчитать следующим образом:

(задача поставлена на минимум);

(задача поставлена на максимум).

Источник

Оцените статью