60

7.Специальные задачи линейного программирования.

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного продукта из m пунктов отправления в n пунктов назначения .

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

Мы возьмем в качестве критерия оптимальности минимальную стоимость перевозок всего груза.

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

( 7.1.0)

при условиях

( 7.1.0)

( 7.1.0)

( 7.1.0)

где

- тарифы перевозок единицы груза из i - го пункта отправления в j - ый пункт назначения.

- запасы груза в i - м пункте отправления

- потребность в грузе в j - м пункте назначения

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

Определение 1.

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

Определение 2.

План , при котором функция ( 7.1 .0) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записываются в виде:

Пункты отправления	Пункты назначения ............ ............					Запасы
............
............
Потребности		............		............

Естественно:

( 7.1.0)

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

Если условие ( 7.1 .0) не выполняется, то модель транспортной задачи называется открытой.

Теорема 1.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие ( 7.1 .0).

Замечание.

(приведение транспортной задачи открытого типа к закрытой).

Если условие ( 7.1 .0) не выполняется, то возможны два случая:

1. ;

2. .

Если транспортная задача открытого типа и запасы пункта А превосходят потребности, то есть , то вводится фиктивный (n + 1) пункт назначения с потребностью

и соответствующие тарифы считаются равными нулю.

Полученная задача является транспортной задачей, для которой выполняется равенство ( 7.1 .0).

Аналогично, если транспортная задача открытого типа и потребности пункта B превосходят запасы, то есть , то вводится фиктивный (m + 1) пункт отправления с запасом груза

и соответствующие тарифы считаются равными нулю.

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

Исходная задача:

Число переменных в транспортной задаче равно n x m, а число уравнений ( 7.1 .0) и ( 7.1 .0) равно n + m. Так как предполагаем, что выполнено условие ( 7.1 .0) (транспортная задача закрытого типа), то число линейно-независимых уравнений равно (n + m - 1). Следовательно, опорный план транспортной задачи может иметь (n + m - 1) отличных от нуля неизвестных.

Замечание.

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

Опорный план считается невырожденным, если число элементов в матрице равно в точности (n + m - 1).

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

Существует несколько методов определения опорного плана и несколько методов определения оптимального плана.

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

1. метод северо-западного угла;

2. метод минимального элемента;

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

Для определения оптимального плана используются:

1. метод потенциалов;

2. метод дифференциальных рент.

и ряд других методов.

7.1.1Определение опорного плана транспортной задачи методом северо-западного угла.

Замечание.

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

(n + m - 1) шагов.

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

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

Рассмотрим метод северо-западного угла на примере.

Пример.

Имеется 4 пункта назначения и 3 пункта отправления.

Запасы грузов соответственно равны:

потребности:

Матрица C(тарифы) имеет следующий вид:

Пункты отправления	Пункты назначения				Запасы
					50
					30
					10
Потребности	30	30	10	20

Получили начальный опорный план методом северо-западного угла.

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

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

Теорема 2.

(для транспортной задачи)

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

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

Числа называются потенциалами:

- потенциалы пунктов назначения;

- потенциалы пунктов отправления.

Базируясь на этой теореме можно построить алгоритм нахождения решения транспортной задачи.

Суть метода:

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

Иногда, в литературе встречается запись , но эта запись ничего не меняет;

1. после определения всех потенциалов для каждой свободной клетки определяется число

;

1. если среди чисел нет положительных, то опорный план, в соответствии с теоремой 2, является оптимальным;

1. если существует хотя бы одна свободная клетка, в которой , то исходный план не является оптимальным;

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

Замечание.

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

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

Ребра располагаются вдоль строк и вдоль столбцов.

В каждой вершине цикла встречаются ровно два звена: одно из которых находится в строке, а другое - в столбце.

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами:

отмеченная точка не является вершиной.

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

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

Перемещение грузов осуществляется по следующим правилам:

1. каждой из клеток, связанной циклом с данной свободной клеткой ( ) приписывают определенный знак(свободной клетки приписывают знак «+», а всем остальным клеткам поочередно знаки «+» и «-»).

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

В результате описанных преобразований(преобразований по пунктам (1) и (2)) свободная клетка становится занятой, а ранее занятая клетка - клетка, в которой стояло наименьшее значение в вершинах цикла(на значит, что наименьшее из всех), становится свободной. Таким образом занятых клеток (n + m - 1).