1. Исследование функции на безусловный экстремум 3

• Название: 1. Исследование функции на безусловный экстремум 3
• Дата: 20.12.2018
• Размер: 0.69 Mb.
• Имя файла: 1541130846473078.docx
• Тип: Исследование; #61169
• страница: 5 из 6

5. Задача транспортного типа

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

Под транспортной задачей (ТЗ) обычно понимают задачу выбора плана перевозок некоторого товара от m источников (пунктов производства, поставщиков) к n стокам (станциям назначения, пунктам сбыта), обеспечивающего минимальные транспортные затраты. При этом предполагают, что а) мощность i-го источника равна S_i>0, i=1, ..., m; б) мощность j-го стока равна D_j>0, j=1,...,n; в) стоимость перевозки единицы товара от i-го источника к j-му стоку (тариф) равна c_ij (в условных денежных единицах).

Для математического описания транспортной задачи вводятся переменные х_ij, обозначающие объемы поставок товара из i-го источника к j-му стоку (в условных единицах объема товара ).

Таким образом, получаем модель ТЗ в виде задачи линейного программирования

ΣΣc_kjx_kj→ min; (1)

Σх_ij= S_i, (i=1,...,m);

Σх_ij= D_j, (j=1,..., n); (2)

x_ij≥0, i=1,...,m, j=1,..., n
Задача (1) с ограничениями (2) может быть решена стандартным симплекс-методом. Однако, специфика ограничений (каждое неизвестное входит только в два уравнения системы (2) с коэффициентами, равными 1) позволяет разработать специальные методы решения ТЗ и задач, которые сводятся к задачам транспортного типа (задача о назначениях, задача выбора кратчайшего пути, задача о замене оборудования и т.п.).

Формы представления ТЗ.

Задача (1), (2) может быть представлена в виде так называемой транспортной таблицы (матричная форма) (Рис.1 ) или в виде сети с ориентированными ребрами (Рис.2). Узлы сети соответствуют источникам и стокам ТЗ, ребро, соединяющее узлы i и j, – доставке товара из i-го источника к j-му стоку. Для каждого узла указывается его мощность, для каждого ребра – стоимость доставки груза (тариф).

Систему уравнений (2) можно представить в эквивалентном виде

Σх_ij= S_i, (i=1,...,m);

-Σх_ij= -D_j, (j=1,..., n); (2’)

Тогда для представления задачи (1), (2’) удобнее использовать следующую форму транспортной таблицы (Рис. 3). Свободные места в таблице соответствуют нулевым коэффициентам при соответствующих переменных. Источникам соответствуют коэффициенты 1, а стокам - коэффициенты -1. В сетевой форме этой записи задачи будут соответствовать мощности стоков, равные (–D_j ).

сток источник	1	…	j	…	n	поставки
1	x11 c11	…	x1j c1j	…	x1n c1n	S1
…	…	…	…	…	…	…
i	xi1 ci1	…	xij cij	…	xin cin	Si
…	…	…	…	…	…	…
m	xm1 cm1	…	xmj cmj	…	xmn cmn	Sm
		…		…
спрос	D1	…	Dj	…	Dn

Рис.1


c₂₃
S₁

S₂

D₁

D₂

D₃

c₂₂

c₂₁

c₁₁

c₁₂

c₂₃

Рис.2.

			Объем поставок
		x11 x12 ...x1n		x21 x22 ...x2n	...		xm1 xm2 ...xmn
Поставки	1 2 … m	1 1 … 1		1 1 … 1	…		1 1 … 1	S1 S2 ,,, Sm
спрос	1 2 ... n	-1 -1 … -1		-1 -1 … -1	…		-1 -1 … -1	-D1 -D2 ... -Dn
		c11 c12 ...c1n		c21 c22 ...c2n	...		cm1 cm2 ...cmn

Рис. 3

При классической постановке ТЗ предполагается выполнение условия

Σ S_i -Σ D_j =0 (3)

то есть, суммарная мощность всех источников равна суммарной мощности всех стоков (закрытая форма ТЗ). Однако, это условие не является принципиальным, так как при его нарушении можно ввести фиктивный источник, если Σ S_i -Σ D_j <0, (или фиктивный сток, если Σ S_i -Σ D_j >0), мощность которого равна величине невязки, положив тарифы на перевозку в этот фиктивный узел равными нулю.
Стратегия и методы решения ТЗ

Задача (1),(2) есть задача линейного программирования с ограничениями – равенствами. Число переменных в задаче равно nm. Система ограничений состоит из m+n уравнений, ранг системы равен m+n-1, то есть, любое допустимое базисное решение ТЗ будет содержать m+n-1 базисных переменных.

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

Методы нахождения начального плана перевозок.

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

Пользуясь таблицей (1), распределяем груз, начиная с загрузки левой верхней (северо-западной) клетки (1,1), двигаясь из нее по строке вправо или по столбцу вниз. В клетку (1,1) заносим x₁₁=min (S₁,D₁). При S₁1 запас первого поставщика будет исчерпан и в дальнейшем первая строка не рассматривается и x_1k=0, k=2,...,n. На следующих шагах последовательно распределяются запасы второго, …, n-го поставщиков, пока не будет полностью удовлетворен спрос первого потребителя.

При S₁>D₁спрос первого потребителя будет полностью удовлетворен и в дальнейшем первый столбец не рассматривается и x_k1=0, k=2,...,n.. На следующих шагах последовательно удовлетворяется спрос второго, …, m-го потребителя.

Если S₁=D_1, то в одну из клеток выбывающих первой строки и первого столбца (лучше в клетку с наименьшим тарифом) заносится так называемый базисный нуль, и x_k1=x_1k=0, k=2,...,n. В оставшейся таблице распределение ресурсов начинается с северо-западного угла, то есть, с клетки (2,2).

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

Последней будет заполнена клетка (m,n).

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

Метод минимальной стоимости.

Метод аналогичен предыдущему, но на каждом шаге заполнение клеток начинается с клетки, которой соответствует наименьшее значение тарифа c_ij; при наличии нескольких клеток с одинаковым тарифом заполняется любая из них. В клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключается строка. соответствующая поставщику, запасы которого исчерпаны, либо столбец. соответствующий потребителю, спрос которого удовлетворен полностью. Если в процессе заполнения таблицы одновременно исключаются строка и столбец (это происходит при полном исчерпывании запаса и полном удовлетворении спроса), то в одну из свободных клеток записывается базисный нуль. Клетка с базисным нулем не должна образовывать цикл с ранее занятыми клетками.

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

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

Введем следующие понятия:

1. 
   Цикл – замкнутая ломаная с вершинами в клетках и звеньями, расположенными вдоль строк и столбцов матрицы перевозок. В каждой вершине встречаются два звена, причем одно из них располагается по строке, а другое – по столбцу. Число вершин цикла четно. Циклом может быть самопересекающаяся ломаная, то точки самопересечения не могут быть вершинами цикла.
   
2. 
   Означенный цикл – цикл, одной из вершин которого приписан знак »+» и при обходе цикла в каком-либо направлении знаки вершин чередуются.
   
3. 
   Сдвиг по циклу на величину Q≥0. При этом значения x_k1, стоящие в положительных вершинах цикла. увеличиваются на Q, а стоящие в отрицательных вершинах цикла уменьшаются на Q.
   

Задача, двойственная к ТЗ (1),(2), запишется в виде:

F(u₁,...,u_m,v₁,...,v_n)= Σ S_i u_i+Σ D_jv_j→ max; (4)

u_i+ v_j≤c_ij; i=1,...,m, j=1,..., n (5)

где двойственные переменные u_i и v_j свободные по знаку.

При этом, по теореме о дополняющей нежесткости, для того, чтобы планы пары двойственных задач х_ij⁰ и u_i⁰, v_j⁰, удовлетворяющие ограничениям (2),(3) и (4), были оптимальными необходимо и достаточно, чтобы выполнялись условия

х_ij⁰(c_ij- u_i⁰- v_j⁰₎=0, i=1,...,m, j=1,..., n (6)

Числа u_i и v_j, i=1,...,m, j=1,..., n, будем называть потенциалами источников и стоков, соответственно

То есть, для оптимального плана ТЗ необходимо выполнение условий:

1. 
   каждой базисной клетке в транспортной таблице соответствует сумма потенциалов. равная тарифу этой клетки.
   
2. 
   каждой свободной клетке соответствует сумма потенциалов, не превышающая тарифа этой клетки.
   

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

1. 
   Найти начальный план перевозок методом северо-западного угла или методом минимальной стоимости.
   
2. 
   Для каждой из m+n-1 базисных клеток составить уравнение u_i+ v_j= c_ij. Решить полученную систему (m+n-1) уравнений с (m+n) неизвестными, для определенности приравняв одну из переменных, например. u₁, нулю. Остальные потенциалы при этом определятся однозначно.
   
3. 
   Для каждой свободной клетки вычислить относительные оценки ∆_ij= c_ij-(u_i+ v_j).
   
4. 
   проанализировать относительные оценки:
   

• 
  если все относительные оценки неотрицательны, то задача решена и получен оптимальный план перевозки;
  
• 
  если среди оценок есть отрицательные, найти наименьшую отрицательную и пометить соответствующую клетку транспортной таблицы знаком «*».
  

5. 
   Для свободной клетки (i,j) с выбранной оценкой, помеченной «*», построить означенный цикл, взяв эту клетку со знаком “+”. Все остальные вершины цикла должны располагаться в базисных клетках.
   
6. 
   Выполнить сдвиг по построенному циклу на величину Q, равную наименьшему из тарифов в отрицательных вершинах цикла. Если наименьшее значение достигается в нескольких отрицательных вершинах, то во всех таких вершинах. кроме одной, при сдвиге следует поставить базисный нуль для сохранения числа базисных клеток равным (m+n-1)..Элементы матрицы, не входящие в цикл. остаются без изменений.
   
7. 
   Перейти на шаг 2.
   

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

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

Замечание 3. Введение дополнительных ограничений может привести к невозможности найти оптимальный план перевозок.