WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Государственный комитет Российской Федерации по высшему образованию Дальневосточный государственный университет ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ТРАНСПОРТНОГО ТИПА Учебно-методическое пособие по курсу "Методы Оптимизации" Владивосток 2003 2 УДК519.85 Тема, рассмотренная в данном пособии, относится к числу сравнительно простых для слушателей курса "Методы оптимизации". Поэтому студент, знакомый с общими основами теории выпуклого и линейного программирования, может самостоятельно освоить теорию и метод решения транспортных задач линейного программирования. Именно для этой цели предназначено это учебнометодическое пособие, представляющее сжатый конспект лекций по данной теме.

Подготовлено кафедрой процессов управления.

Составитель Л.В.Горячев Печатается по решению научно-методического Совета ДВГУ.

© Издательство Дальневосточного университета, 2003.

3 Настоящее методическое пособие предназначено для студентов – слушателей курса "Методы оптимизации". Вместе с учебно-методическими работами "Практический минимум по методам оптимизации", "Одномерная минимизация", "Выпуклые функции и их свойства"и т.д. оно образует учебно-методический комплекс для выполнения самостоятельной работы по данному курсу. Рассматриваемая тема относится к числу простых в курсе и поэтому доступна для самостоятельного изучения даже лишь с помощью данного пособия.

Задачи транспортного типа составляют специальный и довольно обширный класс задач линейного программирования. Объединяющим признаком этого класса служит наличие особого типа ограничений. Специфичность структуры матрицы условий таких задач делает неэффективным применение для их решения стандартного симплекс-метода и его математического обеспечения и требует использования специальных методов. Напомним основные свойства задач линейного программирования (Л.П.) Пусть дана задача ЛП в канонической форме: минимизировать линейную форму n cjxj (1) j=1 при условиях n aijxj = bi, i =1, 2,..., m (2) j=xj 0, j =1, 2,..., n (3) В векторно-матричной форме задача имеет вид (c, x) - min (1’) Ax = b (2’) x 0 (3’) Векторы Aj (j =1, 2,..., n) в матрице A называются векторами условий. Вектор x =(x1, x2,..., xn), удовлетворяющий условиям (1)-(3), называется планом задачи. Оптимальным планом задачи ЛП называется план, минимизирующий целевую функцию (1) План x называется опорным, если векторы Aj, отвечающие его положительным компонентам, линейно-независимы. Невырожденный опорный план содержит m положительных компонент, вырожденный опорный план содержит более чем n - m нулевых компонент/ Система линейно-независимых векторов Aj, отвечающих положительным компонентам опорного плана, образует его базис. Можно считать, что базис любого опорного плана состоит из m линейнонезависимых векторов.

Сформулируем основные теоремы ЛП, отражающие свойства планов задачи.

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

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

Доказательство этих теорем приводится в лекциях. Методы анализа и решения задач ЛП существенно опираются на теорию двойственности. Задача, двойственная к (1)–(3), формулируется следующим образом: найти вектор y =(y1, y2,..., ym)T, максимизирующий линейную форму m biyi (4) i=при условиях m aijyi cj, i =1, 2,..., n (5) j=или в векторно-матричной форме (b, y), AT y c Задачи (1)–(3) и (4)–(5) называют парой двойственных (сопряженных) задач.

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

Пара условий: xj 0, aijyi cj, j =1, 2,..., n называются сопряженными парами условий для задач (1)–(3) и (4)–(5).

Теорема. В каждой паре сопряженных условий на оптимальный планах: если одно свободное, то другое — закрепленное.

Перечисленные свойства задач ЛП широко используются для анализа задач транспортного типа.

Рассмотрение начнем с простейших моделей. Ких числу относится модель следующего типа:

n cjxj - min j=при условиях n xj = b, xj 0, j =1, 2,..., n j=В этой задаче система ограничений, кроме ограничений на знак переменных, состоит из одного уравнения. Поэтому опорный план содержит одну положительную компоненту, а оптимальный опорный план легко находится. Действительно, пусть min{cj} = cj, тогда компоненты оптимального опорного плана bj, j = jx = j 0, j = j Кэтой задаче приводится следующая:

n cjxj - min j=при условиях n ajxj = b, xj 0, j =1, 2,..., n j=Замена переменной yj = ajxj приводит нас к предыдущей модели. Таким образом, решение одноиндексных транспортных задач (Т.З.) тривиально.

Простейшие двухлинейные Т.З. также не вызывают серьезных трудностей при анализе: найти набор X = xij, минимизирующий линейную форму m n cijxij i=1 j=при условиях n aijxij = ai, xij 0, i =1, 2,..., m, j =1, 2,..., n j=Эта задача распадается на m одноиндексных задач, решение которых тривиально. Оптимальный план исходной задачи формируется из оптимальных решений частных задач. Другой простейшей двухидексной задачей транспортного типа является задача: найти набор X = xij, минимизирующий m n cijxij i=1 j=при условиях m n aijxij = b, xij 0, i =1, 2,..., m, j =1, 2,..., n i=1 j=Эта задача сводится к уже рассмотренной простой нумерацией множества пар индексов (i, j) одним индексом k =1, 2,..., m· n.

Более сложной из известных двухиндексных Т.З. является следующая. Пусть в пунктах A1, A2,..., Am производится (или хранится) некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц. Указанный продукт потребляется в пунктах B1, B2,..., Bn, причем объем потребления в пункте Bi равен bi единиц. Допустим, что транспортные издержки, приходящиеся на единицу продукта при перевозке его из i-ого пункта производства в j-ый пункт потребления составляют cij денежный единиц. Требуется найти такой план перевозок (распределение продукта по потребителям), при котором потребности всех потребителей будут удовлетворены, весь продукт будет вывезен и при этом суммарные транспортные затраты будут минимальны.



Пусть xij — количество продукта, транспортируемое из пункта Ai в пункт Bj, математическая модель такой задачи имеет вид m n cijxij - min (6) i=1 j=при условиях n xij = ai, i =1, 2,..., m (7) j=m xij = bj, j =1, 2,..., n (8) i=xij 0 (9) Равенства (7) гарантируют полный вывоз продукта из всех пунктов производства, равенства (8) означают полное удовлетворение потребителей, условия (9) естественны. Т.З. в такой постановке определяется заданием вектора объемов производства a =(a1, a2,..., am)T, вектора объема потребления b =(b1, b2,..., bn)T ) и матрицы транспортных издержек c11 c12... c1n c21 c22... c2n c =...

...

...

cm1 cm2... cmn План Т.З. также удобно записать в виде матрицы x11 x12... x1n x21 x22... x2n X =...

...

...

xm1 xm2... xmn План X иногда называют планом перевозок, а компоненты xij — перевозками. Для задания и решения Т.З. удобно пользоваться таблицей b1 b2... bn a1 c11, x11 c12, x12... c1n, x1n a2 c21, x21 c22, x22... c2n, x2n.......

.......

.......

am cm1, xm1 cm2, xm2... cmn, xmn Для того, чтобы понять специфичность условий Т.З., запишем ее в развернутом виде при m = 2, n =3.

c11x11+c12x12+c13x13+c21x21+c22x22+c23x32 - min x11+ x12+ x13 = ax21+ x22+ x23 = ax11+ x21 = bx12+ x22 = bx12++x23 = bxij 0, i =1, 2,..., m, j =1, 2,..., n Матрица A коэффициентов ограничений имеет вид · · · 1 1 1 0 0 1 i - я позиция 0 0 0 1 1 A = 1 0 0 1 0 0, Aij = · · · 0 1 0 0 1 0 0 1 0 0 1 m + j - я позиция · · · Она сильно разряжена, ее вектор условий Aij имеет две отличные от нуля компоненты, равные 1, одна в i - ой позиции, а другая в m + j - ой позиции. Как следует из постановки, Т.З. имеет m · n ограничений-равенств и m · n переменных. Отметим наиболее важные свойства Т.З.

Теорема. Для разрешимости задачи (6)-(9) необходимо и достаточно выполнения условия баланса m n ai = bj i=1 j=Данное условие означает совпадение суммарного объема производства с суммарным объемом потребления. Транспортные задачи, для которых это условие выполняется, называются закрытыми.

Доказательство. Необходимость. Предполагаем, что Т.З. разрешима. Это означает совместность x ее условий. Пусть набор X = является планом, то есть удовлетворяет условиям (7) и (8).

ij Просуммируем условия (7) по i, а (8) – по j. В результате получим m n m m n m x = ai и x = bi ij ij i=1 j=1 i=1 i=1 j=1 i= откуда непосредственно следует равенство ai = bj.

Достаточность. Пусть условие баланса выполняется. Построим набор X = xij|, где xij = aibk, d = ai = bj. Очевидно, что построенный набор является планом Т.З. Действительно, n n ai x = bj = ai, i =1, 2,..., m ij d j=1 j=m m bj x = ai = bj, j =1, 2,..., n ij d i=1 i=x 0, i =1, 2,..., m, j =1, 2,..., n ij Таким образом множество допустимых планом Т.З. не пусто. Легко видеть, что оно также является ограниченным, выпуклым и замкнутым (выпуклый компакт). Линейная форма на выпуклом компакте ограничена снизу и достигает на нем своего минимума, то есть задача разрешима. Это свидетельствует о достаточности условия баланса.

Из приведенного выше примера Т.З. для m =2 и n =3 видна зависимость между условиямиравенствами. Действительно, сложив первые два условия и вычтя из полученного результата следующие два условия, мы получим последнее уравнение. Таким образом, каждое условие-равенство является следствием остальных условий.

Теперь убедимся, что число независимых условий-равенств Т.З. равно m + n - 1. Для этого достаточно найти в матрице A квадратную подматрицу порядка m + n - 1 с определителем, не равным нулю. Такую подматрицу нетрудно найти в матрице, составленной из векторов A1n, A2n,..., Amn, A11, A12,..., Ai n-1. Первые m + n - 1 строк такой матрицы образуют верхнюю треугольную подматрицу с диагональными элементами, равными 1, и определителем, отличным от нуля. Таким образом, в системе условий-равенств Т.З. одно условие излишнее и его можно отбросить. Однако это обычно не делают, чтобы не нарушать симметричность форм задачи.

Ранг матрицы условий A определяет число линейно-независимых векторов, составляющих базис Т.З. Таким образом, базис Т.З. состоит из m + n - 1 вектора, а невырожденный опорный план содержит m + n - 1 положительных компонент. Сказанное позволяет сформулировать:

Утверждение. Если все ai и bi — неотрицательные целые числа, то любой опорный план является целочисленным.

Доказательство. Оно вытекает из того, что ранг матрицы A условий Т.З. равен m + n - 1, а система базисных векторов содержит треугольную подматрицу m + n - 1 – го порядка. Данное утверждение сформулируем в несколько иной форме, имеющей многочисленные теоретические приложения.

Теорема. Любой минор матрицы A равен 0 либо ±1.





Доказательство. Применим метод математической индукции. Для миноров первого порядка утверждение очевидно, так как элементы A — нули и единицы. Допустим, что теорема верна для миноров матрицы A порядка k - 1, и докажем ее справедливость для миноров порядка k. Разделим обе строки матрицы A на две группы: первые m строк отнесем к 1 – ой группе, а следующие n — ко 2 – ой. Каждый столбец A содержит одну единицу среди строк 1 – ой группы. Пусть k — произвольный минор порядка k. Каждый столбец k содержит либо две единицы, либо одну единицу, либо будет нулевым. В последнем случае, очевидно, k =0. В случае, если хотя бы в одном столбце k содержится ровно одна единица, разлагая минор по этому столбцу, получаем, что k = ± k-1, где k-1 — некоторый минор матрицы A порядка k - 1. Если же во всех столбцах k — по две единицы, то среди строк k имеются представители как первой, так и второй групп строк матрицы A.

Выбирая любую строку k из первой группы, прибавляем к ней остальные строки из этой группы.

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

Анализ Т.З., как и любой части ЛП, существенно опирается на результаты теории двойственности. Введем вектор W (v1, v2,..., vn, -u1, -u2,..., -um)T, где vj — двойственные переменные, отвечающие условиям (8), -ui — отвечают условиям (7), i =1, 2,..., m, j =1, 2,..., n. Знак минус перед ui принят ради удобства интерпретации задачи. Переменные vj и -ui называют потенциалами столбцов и строк соответственно.

Согласно общему правилу построения двойственных задач ЛП, задача, двойственная к Т.З., имеет вид n m bjvj - aiui - max (10) j=1 i=при условии vj - ui cij, i =1, 2,..., m, j =1, 2,..., n (11) Ограничения на знаки двойственных переменных отсутствуют, поскольку условия (7)–(8) прямой задачи имеют вид равенств. Согласно общим свойствам пар двойственных задал ЛП, для любых планов X = xij mn и W (v1, v2,..., vn, -u1, -u2,..., -um)T прямой и двойственной задач, соответственно, справедливо неравенство m n n n cijxij bjvj - aiui i=1 j=1 j=1 i=Непосредственно из условий двойственности задачи следует, что ее допустимый план определяется с точностью до const. Действительно, если W (v1, v2,..., vn, -u1, -u2,..., -um)T — допустимый план, то W (v1 + h, v2 + h,..., vn + h, -(u1 + h), -(u2 + h),..., -(um + h))T также допустим, в чем можно убедиться подстановкой W в условия.

Численный анализ Т.З. существенно опирается на следующий признак оптимальности Теорема. Для оптимальности опорного плана X = xij транспортной задачи необходимо и достаточно существование чисел v1, v2,..., vn, -u1, -u2,..., -um таких, что vj - ui cij, i = 1, 2,..., m, j =1, 2,..., n и vj - ui = cij, при xij 0.

xДоказательство. Необходимость. Если X0 = — оптимальный опорный план, то ему отвечаij ет система оценок столбцов матрицы A, которая удовлетворяет условиям, совпадающим с условиями теоремы.

Достаточность. Пусть существует такая система чисел, что условия теоремы справедливы. Тогда m n m n n m cijx0 = (vj - ui)x0 = bjvj - aiui ij ij i=1 j=1 i=1 j=1 j=1 i=Равенство целевых функций сопряженных задач на допустимых планах свидетельствует об оптимальности этих планов. Очевидно, что оптимальному опорному плану отвечает система потенциалов vj - ui (оптимальный план двойственной задачи), такая, что неравенства выполняются для всех i и j, а базисным компонентам отвечают равенства. Мы уже отмечали, что базис невырожденного опорного плана состоит из m + n - 1 вектора, таково же число базисных компонент. Значит xматрица невырожденного опорного плана X0 = содержит m + n - 1 положительных элеij mn ментов. Опорный план обладает наглядным геометрическим свойством, которое легко обнаружить на матрице плана.

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

Приведем примеры планов, содержащих цикл:

4 5 1 0 2 3 1 0 0 1 2 0 0 1 0 X1 = X2 = X3 = 2 5 0 0 3 0 0 0 8 0 6 2 0 1 3 0 0 5 В матрице X1 цикл образуют компоненты x12, x42, x43, x13, в матрице X2 цикл образован компонентами x11, x21, x23, x43, x42, x12, в матрице X3 в цикле участвуют перевозки x11, x21, x22, x32, x34, x14.

Легко видеть, что векторы-условия Aij, отвечающие компонентам цикла, линейно-зависимы. Например, для цикла X2 вектора A11, A12, A42, A43, A23, A21 линейно-зависимы. Действительно, 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 - + - + - = 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 Следствие. Из компонент опорного плана нельзя составить цикл.

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

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

xk Допустим, что мы находимся на k – ой итерации метода и имеем опорный план Xk =.

ij mn Рассмотрим очередную k +1 итерацию.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.