Лекции Хуторецкий

Из единственности решения x(A0, b0) в задаче P0 следует, что j(A0, c0) > 0 для j N(β)(1).

Тогда j(A, c0) > 0 для j N(β) в некоторой окрестности точки (A0, b0, c0).

Теперь применение следствия 2.11 и теоремы 2.13 завершает доказательство. #

Обозначения.

Элементы матрицы B–1 Rm m обозначим βji, B–1 = (βji | j N(β), i 1, m ).

Пусть x(A, b) = (xj | j 1, n ), y(A, c) = (yi | i 1, m ).

Теорема 2.15. (об устойчивости ЗЛП в канонической форме). В условиях теоремы 2.14

для внутренней точки (A, b, c) из области устойчивости базиса β справедливы соотношения:

Отсюда, поскольку x(A, b) не зависит от c, а y(A, c) не зависит от b, получаем формулы (30).

По определению базисного решения, соответствующего базису β

xj = jibi для j N(β) и xj = 0 для j N(β).

i

Поэтому для внутренних точек (A, b, c) из области устойчивости базиса β выполняются соот-

ношения (31). #

Формулы (30), (31) аналогичны формулам (27), но для ЗЛП в канонической форме они выполняются не только в точке (A0, b0, c0), но и в любой внутренней точке области устойчи-

вости допустимого и оптимального базиса β.

Ограничим вариабельность параметров задачи P0.

Предположение 10. Матрица A0 не изменяется, возмущениям подвергаются только векторы b0 и c0. Параметрами возмущенной задачи являются координаты векторов b и c.

Определения и обозначения.

Набор (b, c) будем считать точкой в пространстве Rт+n.

Учитывая предположение 10, будем вместо P(A, b, c), P*(A, b, c), x(A, b), y(A, c) и (A, c)

писать P(b, c), P*(b, c), x(b), y(c) и (c).

(1) По следствию 1 на стр. 223 книги: Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006.

31

Пусть U ― множество всех точек (b, c), для которых базис β является допустимым и оптимальным в задаче P(b, c), а векторы x(b) и y(c), следовательно, оптимальны в задачах P(b, c) и P*(b, c) соответственно.

Следствие 2.13. U = {(b, c) | B0 1 b ≥ 0m, cб B0 1 D0 – cн ≥ 0n–m}.

Доказательство. По следствию 2.11 базис β является допустимым и оптимальным в задаче P(b, c), если и только если det(B) 0, B–1b ≥ 0m и (c) ≥ 0n. По определению все нену-

левые координаты вектора (c) входят в вектор cбB–1D – cн. Но B = B0 и D = D0 по предполо-

жению 10. Поэтому det(B) = det(B0) 0, а условия B–1b ≥ 0m и (c) ≥ 0n эквивалентны соотношениям B0 1 b ≥ 0m, cб B0 1 D0 – cн ≥ 0n–m. #

Следствие 2.14. Множество U является многогранным. На границе этого множества векторы x(b) и y(c) оптимальны в задачах P(b, c) и P*(b, c) соответственно, но x(b) является вырожденным или неединственным решением задачи P(b, c).

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

описывает его системой линейных неравенств относительно b и c. Если x(b1) является невы-

рожденным и единственным решением задачи P(b1, c1), то по теореме 2.14 некоторая окрест-

ность точки (b1, c1) в Rт+n входит в U. Тогда эта точка не может быть граничной для множе-

ства U. #

2.5.3. Каноническая форма: устойчивость оптимального решения Усилим предположение 10.

Предположение 11. Возмущения распространяются только на вектор с0. Параметрами возмущенной задачи являются координаты вектора с.

Определения и обозначения.

Учитывая предположения 10 и 11, будем вместо P(b, c), P*(b, c) и V(A, b, c) писать P(с),

P*(с) и V(с).

Элементы матрицы B0 1 Rm m обозначим 0ji , B0 1 = ( ij0 | j N(β), i 1, m )/ Элементы матрицы B0 1 D0 Rm (n–m) обозначим dij, B0 1 D0 = (dij | i 1, m , j N(β)). Положим x0 = x(b0).

Пусть Uс ― множество всех векторов с, для которых базис β является допустимым и оптимальным в задаче P(b), а векторы x0 и y(с), следовательно, оптимальны в задачах P(с) и

P*(с) соответственно. Это область постоянства оптимального решения (ОПОР).

Теорема 2.16 (об устойчивости оптимального решения).

32

(а) ОПОР совпадает с множеством решений следующей системы линейных неравенств

относительно координат вектора c:

i 1

(б) Если c ОПОР, то x0 является оптимальным решением задачи P(c), а вектор двойствен-

ных оценок и максимальное значение ЦФ линейно зависят от c:

(в) Если вектор c является внутренней точкой ОПОР, то x0 ― единственное решение зада-

чи P(c). Если вектор c лежит на границе ОПОР и решение x0 невырожденное, то задача P(c)

имеет альтернативное решение.

Доказательство.

(а) Из определений и следствия 2.13 ясно, что

Uc = {с | (b0, c) U} = {c | cб B0 1 D0 – cн ≥ 0n–m}.

Отсюда, учитывая, что j(i) для i 1, m ― это номера базисных столбцов, получаем (32).

(б) Пусть c ОПОР. Из определения Uc и теоремы 2.13 следует, что x0 является оптималь-

ным решением задачи P(c), а y(c) ― оптимальное решение задачи P*(c). Но y(c) = cб B0 1 и xн0 = 0n–m. Это доказывает формулы (33).

(в) Если вектор c является внутренней точкой ОПОР, то все неравенства (32) являются строгими, j(c) > 0 для всех j N(β). Если вектор c лежит на границе ОПОР, то хотя бы одно из неравенств (32) выполняется как равенство. Тогда j(c) = 0 для некоторого j N(β). Отсюда следует утверждение (в).(1) #

В рамках предположения 11 рассмотрим случай, когда изменяться может только коор-

дината вектора c0 с номером s, cj = с0j для j s.

Обозначение. Допустим, что задачи P(c) и P0 различаются только значениями коэффи-

циента ЦФ при xs. Тогда Uc(s) ― множество всех значений cs, при которых базис β остается допустимым и оптимальным в задаче P(c).

Теорема 2.17 (ОПОР при изменении одного коэффициента ЦФ). Пусть задачи P(c) и P0

различаются только значениями коэффициента ЦФ при xs.

(а) Uc(s) ― это замкнутый промежуток в R (точка, отрезок, луч, прямая).

(б) Если cs Uc(s), то оптимальное решение задачи P(c) равно x0.

(1) По следствию 1 на стр. 223 книги: Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006.

33

(в) Пусть cs Uc(s). Если s N(β), то yi(c) = yi0 + (cs – сs0 ) 0si для всех i, иначе y(c) = y0.

(г) Если cs Uc(s), то V(c) = V(c0) + (cs – сs0 ) xs0 .

(д) Если cs Uc(s) и s N(β), то Uc(s) = (–∞, сs0 + s(с0)].

(e) Если решение x0 невырожденное и cs ― граница промежутка Uc(s), то задача P(c) имеет альтернативное решение.

Доказательство.

Утверждение (а) следует из того, что множество решений системы линейных нера-

венств (32) относительно одной неизвестной cs является многогранным множеством в R.

Утверждения (б) и (е) следуют из соответствующих утверждений теоремы 2.16.

Если s N(β), то s = j(i) для некоторого i. Тогда утверждение (в) следует из (33). Если же s N(β), то y(c) не зависит от cs и утверждение (в) справедливо.

Утверждение (г) следует из (33) с учетом того, что xs0 = 0 при s N(β).

Пусть s N(β). Тогда cs участвует только в одном неравенстве группы (32):

Остальные неравенства (32) эквивалентны j(с0) ≥ 0 для j N(β) \ {s} и выполняются, так как базис β оптимален в задаче P0. Поэтому множество решений системы неравенств (32) отно-

сительно cs имеет вид {cs | cs ≤ сs0 + s(с0)}, утверждение (д) доказано. #

В рамках предположения 11 формулы (30) принимают вид:

Если решить задачу P0 с помощью надстройки «Поиск решения» MS Excel, то отчет об устойчивости в столбцах «Допустимое Увеличение» и «Допустимое Уменьшение» укажет отклонения границ промежутков Uc(j) от с0j для всех j 1, n . Бесконечные границы, в частно-

сти, нижние границы Uc(j) для j N(β), заменяются числом 1E+30 = 1030.

Промежуток Uc(j) указывает, в каких границах изменение коэффициента ЦФ при xj со-

храняет оптимальность решения x0.

Утверждение (г) теоремы 2.17 позволяет решать, так называемую, обратную задачу:

как нужно изменить коэффициент с0j , чтобы при том же оптимальном решении оптимальное значение ЦФ стало равным заданной величине F? Если x0j = 0 (в частности, если j N(β)), то задача неразрешима без изменения базиса. Пусть x0j 0. Тогда из F = V(c) = V(c0) + (cs – сs0 ) x0j получаем

34

Это значение cj решает задачу, если оно лежит в Uc(j), в противном случае задача неразре-

шима без изменения базиса.

Утверждение (д) используют для решения другой обратной задачи: если j N(β), то на-

сколько нужно изменить коэффициент с0j , чтобы переменная xj могла с ненулевым значени-

ем войти в оптимальный план? Действительно, x0j = 0, так как xj ― небазисная переменная относительно базиса β. Если cj < с0j + j(с0), то x0 ― единственное решение задачи P(c). Что-

бы задача P(c) имела решение x1 x0, необходимо (при невырожденном x0 и достаточно),

чтобы выполнялось равенство cj = с0j + j(с0). В альтернативном решении x1 переменная xj

может иметь ненулевое значение. Следовательно, с0j нужно увеличить на j(с0).

2.5.4. Каноническая форма: устойчивость теневых цен Отменим предположение 11, сохраняя предположение 10.

Предположение 12. Возмущения распространяются только на вектор b0. Параметрами возмущенной задачи являются координаты вектора b.

Определения и обозначения.

Учитывая предположения 10 и 12, будем вместо P(b, c), P*(b, c) и V(A, b, c) писать P(b),

P*(b) и V(b).

Положим y0 = y(с0).

Пусть Ub ― множество всех векторов b, для которых базис β является допустимым и оптимальным в задаче P(b), а векторы x(b) и y0, следовательно, оптимальны в задачах P(b) и

P*(b) соответственно. Это область постоянства двойственных оценок (ОПДО).

Теорема 2.18 (устойчивость вектора двойственных оценок).

(а) ОПДО совпадает с множеством решений следующей системы линейных неравенств относительно координат вектора b:

(б) Если b ОПДО, то y0 является вектором двойственных оценок задачи P(c), а оптималь-

ное решение и максимальное значение ЦФ линейно зависят от b:

35

отклонения границ промежутков Ub(i) от bi0 для всех i 1, m . Число 1E+30 = 1030 заменяет бесконечные границы.

Промежуток Ub(i) указывает, в каких границах изменение правой части ограничения с номером i сохраняет вектор двойственных оценок y0.

Утверждение (в) теоремы 2.19 позволяет решать следующую обратную задачу: как

нужно изменить параметр bi0 (например, запас ресурса i), чтобы в оптимальном плане значе-

ние переменной xs (например, производство продукта s) было равно заданной величине v ≥ 0?

Если s N(β) или βsi = 0, то xs(b) не зависит от bi и задача неразрешима без изменения базиса.

Если это значение bi не лежит в Ub(i), то xs = v в оптимальном плане недостижимо без изме-

нения базиса. Если же bi Ub(i), то xs(b) = v. Оптимальный план x(b) задачи P(b) находим по формулам, приведенным в утверждении (в) теоремы 2.19.

Еще одна обратная задача решается на основании утверждения (г) теоремы 2.19: при каком значении bi оптимальное значение ЦФ в задаче P(b) равно F? Из уравнения

F = V(b) = V(b0) + (bi – bi0 ) yi0

видим, что V(b) при yi0 = 0 не зависит от bi, вследствие чего задача неразрешима без измене-

ния базиса. Пусть yi0 0. Тогда из приведенного выше уравнения найдем

bi = bi0 + F V (b0 ) . yi0

Если это значение bi не лежит в Ub(i), то V(b) = F недостижимо без изменения базиса. Если же bi Ub(i), то bi решает задачу. Соответствующий оптимальный план находим, как в преды-

дущей обратной задаче.

Литература

Абрамов Л.М., Капустин В.Ф. Математическое программирование. Изд-во ЛГУ, 1981 (глава 2, §4; главы 4 – 7).

Ашманов С.А. Линейное программирование. М.: Наука, 1981 (главы I – III, V; глава 7, §§1 – 4).

Вагнер Г. Основы исследования операций. В 3 т. Том 1. М.: Мир, 1972 (главы 2 – 5).

Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980 (гла-

ва 3).

37

Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998

(§§1 – 7).

Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966 (главы 3, 5 – 7, 12).

Интриллигатор М. Математические методы оптимизации и экономическая теория. М.:

Айрис-пресс, 2002 (глава 5).

Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006 (глава 4).

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

Вэтом разделе мы будем говорить о задачах линейного программирования транспорт-

ного типа. Задачи этого класса имеют обширные приложения и эффективно решаются (бла-

годаря специфической структуре ограничений).

3.1.Предварительные сведения

3.1.1.Графы и сети

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

Простой конечный ориентированный граф (далее ― просто граф) есть пара G = (V, E),

где V ― конечное множество, элементы которого называются вершинами графа, и E ― мно-

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

шины графа занумерованы, то можно отождествлять вершину с ее номером.

Ребро ― это пара разнонаправленных дуг. Если (i, j) E и (j, i) E, то говорят, что в графе есть ребро [i, j] (или [j, i]).

Если (i, j) ((i, j) E → (j, i) E), то граф называется неориентированным. Взвешенным

называется граф, дугам (или вершинам) которого поставлены в соответствие какие-то число-

вые параметры.

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

Две вершины называются соседними, если есть дуга, их соединяющая.

Говорят, что вершина и дуга инцидентны, если вершина является начальной или конце-

вой для этой дуги; две дуги инцидентны если они инцидентны одной вершине.

Последовательность вершин i1, …, im+1 называется путем, если для всех k 1, m в графе есть дуга (ik, ik+1). Эта последовательность называется цепью, если в графе есть ребро [ik, ik+1]

для всех k 1, m . Вершина i1 называется начальной вершиной пути (цепи), вершина im+1 ― ко-

нечной вершиной пути (цепи). Если i1 = im+1, то путь (цепь) называется контуром (циклом).

38

Цепь, путь, цикл, контур называются простыми, если в соответствующей последова-

тельности i1, …, im+1 никакие две вершины, за исключением, может быть, первой и послед-

ней, не совпадают.

Сеть ― ориентированный граф без контуров.(1)

Дерево ― неориентированный граф без циклов.

Ориентированное дерево ― это дерево, в котором выделен корень (любая вершина) и

все ребра заменены дугами, ориентированными одинаково (от корня или к корню).

Неориентированный (ориентированный) граф называют связным (сильно связным), ес-

ли между любыми двумя его вершинами существует цепь (путь).

Граф G = (V, E) называется полным, если E = V 2.

Граф G = (V1 V2, E) называется двудольным, если V1 V2 = и E V1 V2. Граф G = (V1 V2, E) является полным двудольным, если V1 V2 = и E = V1 V2.

3.1.2. Вполне унимодулярные задачи

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

Минор матрицы ― это определитель ее квадратной подматрицы.

Порядок минора равен k, если соответствующая подматрица имеет размерность k k.

Матрица называется абсолютно (или вполне) унимодулярной, если значения всех ее ми-

норов принадлежат множеству {0, 1, –1}.

Многогранное множество называется целочисленным, если все его угловые точки яв-

ляются целочисленными.

Заметим, что каждый элемент абсолютно унимодулярной матрицы принадлежит мно-

жеству {0, 1, –1}, так как является ее минором порядка 1.

Теорема 3.1 (связь абсолютной унимодулярности целочисленности).(2) Пусть A Rn m, b Rm. Матрица A абсолютно унимодулярна тогда и только тогда, когда многогранное мно-

жество {x Rn | Ax = b, x ≥ 0n} является целочисленным при любом целочисленном векторе b.

Теорема 3.2 (абсолютная унимодулярность ЗЛП в канонической форме).(3) Для ЗЛП с целочисленным вектором правых частей ограничений, матрица которой абсолютно унимо-

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

(1)В контексте задач транспортного типа произвольный граф часто называют транспортной сетью.

(2)Доказательство: Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974 (теорема

8.8).

(3) Доказательство легко получить, анализируя способ приведения произвольной ЗЛП к канонической форме (см. теорему 2.1 и сноску к ней). В указанной выше книге Т. Ху аналогичный результат доказан для ЗЛП в стандартной форме (следствие из теоремы 8.8).

39

Следствие 3.1. Предположим, что ЗЛП разрешима и удовлетворяет условиям теоремы

3.2. Тогда все БДР канонической формы задачи и оптимальное решение задачи, найденное симплекс-методом, являются целочисленными.

Доказательство. Пусть P ― разрешимая ЗЛП с абсолютно унимодулярной матрицей и целочисленным вектором правых частей ограничений, P1 ― эквивалентная ей задача в кано-

нической форме с абсолютно унимодулярной матрицей и целочисленным вектором правых частей ограничений (существует по теореме 3.2). Многогранное множество допустимых ре-

шений задачи P1 является целочисленным по теореме 3.1, а его угловые точки совпадают с БДР задачи P1 по следствию 2.3. Следовательно, симплекс-метод найдет целочисленное оп-

тимальное БДР задачи P1. Способ приведения произвольной ЗЛП к канонической форме га-

рантирует целочисленность соответствующего решения задачи P. #

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

следующий достаточный признак.

Теорема 3.3 (признак абсолютной унимодулярности).(1) Матрица абсолютно унимоду-

лярна, если выполнены следующие условия.

(а) Каждый элемент матрицы равен 0, 1 или –1.

(б) В каждом столбце матрицы есть не более двух ненулевых элементов.

(в) Множество строк матрицы можно разбить на два подмножества такие, что:

(в1) если столбец содержит два ненулевых элемента одного знака, то соответствующие строки входят в разные подмножества;

(в2) если столбец содержит два ненулевых элемента разных знаков, то соответствую-

щие строки принадлежат одному подмножеству.

3.2.Транспортная задача в матричной постановке

3.2.1.Основная модель

Транспортная задача в матричной постановке (ТЗМП), которую называют также за-

дачей Хичкока, формулируется следующим образом.

Пусть в экономической системе m поставщиков и n потребителей некоторого товара.

Поставщик i может за рассматриваемый период поставить не более Si ≥ 0 единиц товара

(мощность), а потребитель j хотел бы получить в течение того же периода не менее Dj ≥ 0

единиц товара (потребность). Затраты на доставку единицы товара от поставщика i потреби-

телю j равны cij. Цель ЛПР ― удовлетворить потребности с минимальными затратами.

(1) Доказательство: Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974 (теорема

8.9).

40