Реферат: Методы линейного программирования для решения транспортной задачи

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

Первый случай. Среди отмеченных клеток имеется одна клетка, единственная в ряду (строке или столбце) (табл.5).

Откажемся от этой клетки, исключим эту строку из рассмотрения. Тогда придем к таблице, у которой строк на единицу меньше, а число столбцов сохранилось. Число строк в сумме с числом столбцов будет меньше (k +l ) на одну единицу, но и число отмеченных клеток уменьшится на одну. Для этого случая можно построить цикл по принятому допущению. Этот цикл возьмем и для нашей таблицы, так как в соответствии с оговоркой вершины цикла могут быть и не вo всex отмеченных клетках.

Второй случай. Нет таких ситуаций, когда клетка одна. В каждой строке (столбце) больше чем одна клетка (или нет ни одной) (табл.6).

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

Выше было показано, что теорема справедлива для k =2, l =2, т.е. для k +l =4. По доказанному она справедлива для случаев: k +l =5, т.е. k +l >4; k +l =6, т.е. k +l >5; k +l >6 и т.д., т.е. для любого макета.

Допустимый план Х (xij ) называется ациклическим (нециклическим), если набор клеток с отличными от нуля компонентами плана xij >0 не содержит ни одного цикла.

Пример ациклического плана приведен в табл.7,

где точки обозначают клетки, в которых xij >0 (xij <0 недопустимы по смыслу задачи). Как покажем ниже, среди ациклических планов есть оптимальный.

Если в ациклическом плане Х (xij ) число положительных компонентов

N = k + l - 1 (остальные компоненты - нули), то элементы aij матрицы тарифов из набора клеток, в которых расположены xij >0, будем называть Х -отмеченными.

Если же число положительных компонент плана N < k + l - l, то к клеткам, занятым положительными xij добавляем недостающие до (k +l -1) из нулевых клеток, лишь бы присоединенные клетки вместе с уже взятыми не допускали циклов. Тарифы aij всех взятых клеток, равно как и сами клетки, включаются в число Х -отмеченных.

Больше (k + l - 1) число компонент ациклического плана не может быть: , так как уже при N=k+l по доказанной выше теореме всегда из выбранных клеток можно построить цикл.

Теорема 2 (основная теорема). Если для некоторого плана Х= (xij ) kl транспортной задачи можно подобрать систему из k+l чисел u1 , u2 ,…, ui, …, uk ; vl , v2 ,…, vj ,…, vl , удовлетворяющую следующим условиям: vj - ui £ aij для всех i = 1, 2,., k ; j = 1, 2,., l , а для xij >0 (xij (-X )) vj - ui = aij , то план Х будет оптимальным.

Числа ui , vj называются потенциалами пунктов отправления и пунктов назначения; условия vj - ui £ aij и vj - ui = aij называют условиями потенциальности плана Х .

К каждой клетке (i , j ) относятся два потенциала: i -ro пункта отправления ui и j -ro пункта назначения vj . Условия потенциальности словесно можно сформулировать так: разность потенциалов для всех без исключения клеток должна быть меньше или равна тарифу, а для занятых (Х -отмеченных) клеток она должна быть точно равна тарифу. План, удовлетворяющий этим условиям, называется потенциальным.

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

Доказательство. Допустим, что для некоторого плана Х (xij ) условия потенциальности выполнены, т.е. существует такая система чисел ui и vj , которая удовлетворяет условиям vj - ui = aij и vj - ui £ aij (табл.8).

Иными словами, пусть план Х потенциален. Докажем, что этот план будет оптимальным. План Х дает значение функционалу

.

Так как мы еще не знаем, оптимален план Х или нет, то возьмем заведомо оптимальный план Х' (x ¢ij ) и посмотрим, какое значение он доставляет функционалу:

(транспортные расходы минимальны). Выполняются ли условия потенциальности для плана Х' - неизвестно, но каждой клетке (i , j ) макета 8, исходя из потенциальности плана Х , соответствует неравенство vj - ui £ aij или, наоборот, aij vj - ui. Возьмем из каждой клетки макета соответствующий х'ij , умножим его на левую и правую части последнего неравенства и сложим. Получим неравенство

.

Двойную сумму в правой части обозначим для краткости буквой S:

К-во Просмотров: 299
Бесплатно скачать Реферат: Методы линейного программирования для решения транспортной задачи