Примеры решения задач по линейному программированию

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

Эта страница подготовлена для студентов любых специальностей и охватывает полностью предмет «линейное программирование».

Если что-то непонятно вы всегда можете написать мне в воцап и я вам помогу!

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

К оглавлению…

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

При этом на переменные наложены линейные ограничения:

Здесь коэффициенты — заданные числа, а величины — неизвестные. Каждое из ограничений системы — одно из трех возможных: .

Совокупность целевой функции (1.1) и системы ограничений (1.2) называется математической моделью задачи линейного программирования.

Любой набор чисел , удовлетворяющий системе ограничений (1.2), называется допустимым решением данной ЗЛП. Допустимое решение, на котором достигается требуемый экстремум целевой функции (1.1), называется оптимальным решением данной ЗЛП. Множество всех допустимых решений данной ЗЛП называется допустимой областью.

Возможно эта страница вам будет полезна:

Предмет математическое программирование

Примеры построения математических моделей задач линейного программирования

К оглавлению…

Задача линейного программирования с двумя переменными. Графическое решение ЗЛП с двумя переменными

К оглавлению…

Математическая модель ЗЛП с двумя переменными такова

где

данные числа.

Введем на плоскости прямоугольную систему координат. Тогда допустимую область задачи (2.1) можно изобразить графически, как множество точек плоскости, координаты которых удовлетворяют сразу всем неравенствам задачи (2.1). Рассмотрим неравенство

Каждое такое неравенство определяет полуплоскость, лежащую по одну сторону прямой

Координаты точек другой полуплоскости удовлетворяют противоположному неравенству

Чтобы определить, какую именно полуплоскость определяет данное неравенство, достаточно взять произвольную точку плоскости () (например, начало координат) и подставить в неравенство числа . Если оно удовлетворится, то полуплоскость, в которой лежит данная точка, — искомая. В противном случае нужная полуплоскость лежит по другую сторону прямой

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

Пример задачи с решением:

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

Целевая функция принимает одно и то же значение во всех точках прямой . Такая прямая называется линией уровня целевой функции.

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

Значения целевой функции неограниченно возрастают, если перемещать прямую в направлении ее нормали — вектора-градиента . Значения целевой функции неограниченно убывают, если перемещать прямую в направлении вектора —. То положение прямой, при котором ее дальнейшее перемещение дает пустое пересечение с допустимой областью, и будет искомым. Множество оптимальных точек состоит из точек пересечения последней линии уровня с допустимой областью. На рис. 2.5 показан случай, когда максимум целевой функции достигается в точке , а минимум — во всех точках отрезка . При этом

Пример задачи с решением:

Понятие об анализе на чувствительность

К оглавлению…

Цель анализа на чувствительность — показать, как изменится оптимальное решение данной ЗЛП, если изменить коэффициенты целевой функции или правые части системы ограничений, или коэффициенты при переменных в левой части системы ограничений.

Для ответа на подобные вопросы не нужно заново решать ЗЛП. Оказывается, что, располагая оптимальным решением ЗЛП и некоторой дополнительной информацией, можно провести анализ на чувствительность, не возвращаясь к началу решения. Как это делается в общем случае, мы увидим позже. А сейчас рассмотрим пример.

Пример задачи с решением:

Первая задача анализа на чувствительность

К оглавлению…

Требуется ответить на такие вопросы:

  • На сколько можно изменить (увеличить или уменьшить) правую часть некоторого ограничения, чтобы оптимальное значение целевой функции не изменилось?
  • На сколько нужно изменить правую часть некоторого ограничения, чтобы улучшить значение целевой функции?

Ответим на эти вопросы для нашего примера. Максимум целевой функции достигается во всех точках отрезка , лежащего на прямой . Ограничение называют связывающим, а остальные ограничения — несвязывающими. Если бы максимум достигался в вершине, а не на отрезке, то связывающими оказались бы два ограничения, соответствующие прямым, на пересечении которых лежит эта вершина. Правая часть ограничения (число 100) называется дефицитным ресурсом, правые части несвязывающих ограничений называются недефицитными ресурсами. Эти определения пришли из-фкономики, когда требовалось дать содержательную трактовку решения ЗЛП, математическая модель которой описывала реальную экономическую проблему.

В оптимальной точке связывающие ограничения превращаются в равенства, а несвязывающие — в строгие неравенства. Это значит, что правую часть несвязывающего ограничения можно увеличить (если это ограничение ) или уменьшить (если это ограничение ) на некоторое число, но оптимальное решение задачи останется прежним.

Если, например, увеличить правую часть ограничения , сделать ее больше нуля, прямая переместится вниз. Но до тех пор, пока точка пересечения прямой с прямой лежит выше точки по-прежнему достигается во всех точках отрезка и равен 1000. В частности, точка (35; 7,5) будет одним из оптимальных решений задачи. Последний раз это произойдет, когда точки и сольются. Подставляя в уравнение координаты точки , получаем, что

Как только а превзойдет число 9,5, оптимальной станет точка пересечения отрезка и прямой

В этом случае всегда нужно производить 35 единиц продукции . Количество единиц продукции определяется из уравнения

Значит, если , система ограничений становится несовместной.

Отметим, что неравенство

можно переписать в виде

и трактовать следующим образом: объем сбыта продукции составляет не менее 60% всего объема реализованной продукции плюс дополнительно а единиц.

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

Тогда прямая начнет перемещаться вверх (рис. 2.9).

При перемещении вверх прямой отрезок , в конце концов, стянется в точку (35; 70/3). Уравнение прямой :

В точке , лежащей на пересечении прямых

становятся связывающими оба ограничения:

Допустимая область — четырехугольник максимум целевой функции достигается в точке и равен

Если запас сырья превзойдет величину 490/3 , то ограничение по запасу сырья перестанет влиять на форму допустимой области (уже не будет связывающим) и, значит, на оптимальное решение. Объем запаса сырья не следует увеличивать сверх числа 490/3, это не приведет к росту прибыли.

Вторая задача анализа на чувствительность

К оглавлению…

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

У нас всего одно связывающее ограничение. Мы показали, что целевую функцию можно увеличить на 1900/3 единицы, если увеличить запасы сырья на 190/3 единицы.

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

где — номер соответствующего ограничения.

В нашем примере ценность единственного ресурса равна

Другими словами, увеличение на единицу объема ресурса приведет к росту целевой функции на 10 единиц.

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

Третья задача анализа на чувствительность

К оглавлению…

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

Рассмотрим такую целевую функцию

где — заданные числа; — параметр, который может принимать любое значение из интервала . Выберем линию уровня целевой функции, на которой она равна 0, ее уравнение

Эта прямая проходит через точку (0,0) — начало координат — при любых значениях . Условно «разрешим» параметру принимать также значения . Уравнение (2.2) перепишем в виде

Коэффициент равен тангенсу угла наклона прямой (2.3) к оси . Изменение величины означает вращение прямой (2.3) относительно начала координат. Когда , прямая (2.3) совпадает с осью ; когда , прямая (2.3) совпадает с осью .

Таким образом, когда , прямая

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

Пусть . Тогда, если вектор направлен по оси в отрицательную сторону (справа налево). При вектор с направлен по оси вертикально вверх. При вектор направлен по оси в положительную сторону (слева направо) (рис. 2.10). Вращение происходит по часовой стрелке. На рис. 2.10 показано также, как происходит вращение вектора при других сочетаниях знаков коэффициентов .

В качестве самостоятельного упражнения предлагается построить подобную диаграмму для вектора , когда целевая функция такова:

где — заданные числа; — параметр, .

Обратимся к целевой функции

Выясним, как влияет на оптимальное решение величина стоимости одной единицы продукции . Перепишем целевую функцию в виде

Начнем со значения , не рассматривая отрицательные значения стоимости, и будем увеличивать этот коэффициент (рис. 2.11).

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

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

Пусть . Если возрастает, то линия уровня (вместе с вектором-градиентом) вращается против часовой стрелки.

Максимум целевой функции будет достигаться в вершине , в которой

При некотором линия уровня станет параллельна прямой . Тогда максимум целевой функции будет достигаться во всех точках отрезка .

Параллельность прямых означает пропорциональность коэффициентов при переменных в уравнениях этих прямых.

Уравнение прямой

Уравнение линии уровня

Отсюда . Итак, когда , максимум достигается во всех точках отрезка и равен 1000.

Если , максимум достигается в вершине . Определим ее координаты. Точка лежит на пересечении прямых

откуда

Наконец, если формально положить , то можно назвать оптимальную вершину — это снова вершина .

Подведем итоги.

  1. достигается во всех точках отрезка и равен 700.
  2. достигается в вершине (35; 7,5) и равен
  3. Оптимальными являются точки отрезка ,
  4. . Оптимальная точка — вершина (150/7; 100/7),
  5. Максимум достигается в вершине .

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

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

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

Рассмотрим ограничение по запасам сырья из нашего примера

Заменим константу 2 переменной и рассмотрим уравнение прямой

Будем менять коэффициент от 0 до . Прямая (2.4) проходит через точку (0; 25) при любых значениях коэффициента . Когда меняется от 0 до , прямая (2.4) совершает поворот на 90° из начального горизонтального положения ( = 0) в конечное вертикальное . Легко убедиться, что вращение происходит по часовой стрелке (рис. 2. 12).

Когда достигается в точке (35; 70/3): если продукция совсем не требует расхода сырья, ее нужно изготовить как можно больше. Но ограничения не позволяют изготовить более 35 единиц продукции . Оптимальное значение находится из уравнения

Если

Точка будет оптимальной до тех пор, пока прямая = 100 будет проходить выше вершины . Последний раз максимум будет достигаться в точке , когда прямая = 100 пройдет через нее. Определим значение .

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

Значит, вершина является оптимальной, пока значения лежат в интервале (4/21; 2). Координаты вершины :

Как только значение превзойдет 2, оптимальная точка переместится в вершину . Так будет, пока вершина не сольется с вершиной (15,10). При этом коэффициента равен (100-4 * 10)/15 =4.

Итак, если 2 < < 4, максимум достигается в точке . Ее координаты можно найти, решив систему уравнений

Отсюда

Когда

Если становится больше 4, от допустимой области остается только треугольник . Оптимальная вершина — , ее координаты таковы:

определяется из условия

Тогда

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

Значит, если

допустимая область пуста, ЗЛП не имеет решения.

Подведем итоги.

  1. Оптимальная вершина —
  2. Оптимальная вершина — . Она лежит на пересечении прямых . Координаты вершины
  3. . Оптимальное решение достигается во всех точках отрезка . Вершина (150/7; 100/7) лежит на пересечении прямых Вершина (35; 7,5) лежит на пересечении прямых .
  4. . Максимум целевой функции достигается в точке с координатами . Точка лежит на пересечении прямых .
  5. . Оптимальная вершина-. Точка лежит на пересечении прямых .
  6. . Допустимая область пуста, задача не имеет решения.

Опорные решения. Определение канонической формы задачи линейного программирования

К оглавлению…

Говорят, что ЗЛП задана в каноническом виде, если ее целевая функция максимизируется. Система ограничений — это система линейных уравнений, а на все переменные наложено условие неотрицательности. Кроме того, предполагается, что число переменных больше числа уравнений, т.е. система ограничений имеет бесконечно много решений. Таким образом, каноническая форма ЗЛП такова:

Задачу (3.1) — (3.2) можно записать компактней. Обозначим через

-мерный вектор неизвестных; через

-мерный вектор коэффициентов целевой функции; через

-мерный вектор правых частей; через

матрицу размера коэффициентов системы линейных уравнений (3.2).

Тогда задача (3.1) — (3.2) записывается так

где -мерный нуль-вектор; — скалярное произведение векторов и .

Приведение произвольной задачи линейного программирования к каноническому виду

К оглавлению…

Чтобы представить задачу (3.1) — (3.2) в канонической форме, нужно уметь:

1) переходить от задачи минимизации целевой функции к задаче максимизации целевой функции;

2) переходить от неравенств к уравнениям;

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

Под выражением «нужно уметь переходить» понимается утверждение о переходе от исходной ЗЛП к ЗЛП, заданной в канонической форме так, чтобы, зная оптимальное решение канонической ЗЛП, указать оптимальное решение исходной.

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

Переход от неравенств к уравнениям. Рассмотрим неравенство

Пусть вектор

некоторое решение этого неравенства. Тогда

Обозначим разность

через . Тогда и вектор

решение уравнения

Пусть теперь вектор

есть решение уравнения

Так как , то вектор

решение неравенства

Установлено взаимно однозначное соответствие между всеми решениями неравенства (3.3) и уравнения (3.4). В этом смысле неравенство (3.3) эквивалентно уравнению (3.4).

Так как в целевую функцию переменная не входит, то значения на соответствующих друг другу решениях неравенства (3.3) и уравнения (3.4) совпадают. Другими словами, неравенство

приводится к уравнению

если прибавить дополнительную неотрицательную переменную к левой части неравенства.

Аналогично из неравенства

получается эквивалентное уравнение

Для этого из левой части неравенства (3.5) следует вычесть дополнительную неотрицательную переменную .

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

Как удовлетворить требованию неотрицательности переменных

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

где

Система уравнений (3.2) примет вид

Вместо целевой функции

рассмотрим целевую функцию

Любому решению

системы (3.2) можно поставить в соответствие бесконечно много решений

системы (3.7), (3.7′), где

Но для всякого такого решения значение целевой функции (3.8) на нем равно

т.е. равно значению целевой функции (3.1) на решении .

Обратно, каждому решению

системы (3.7), (3.7′), ставится в соответствие решение

системы (3.2), где

причем значения целевых функций (3.1) и (3.8) на этих решениях совпадают.

Поэтому, если

оптимальное решение задачи (3.7), (3.7′), (3.8), максимизирующее целевую функцию (3.8), то вектор

оптимальное решение задачи (3.1), (3.2). На векторе целевая функция (3.1) достигает своего максимума.

Пример задачи с решением:

Решение системы линейных уравнений по методу Гаусса (методу исключения неизвестных)

К оглавлению…

Рассмотрим систему линейных уравнений с уравнениями и неизвестными, причем .

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

  1. Почленное умножение всех коэффициентов и правой части некоторого уравнения на одно и то же число.
  2. Прибавление к одному из уравнений системы линейной комбинации других уравнений.

Используя перечисленные преобразования, систему (3.9) можно привести к виду, для которого описание множества решений системы (3.9) не представляет труда. Для этого в каждом Уравнении нужно оставить переменную, которая исключается из всех остальных уравнений системы. Такая переменная называется базисной переменной данного уравнения. Базисная переменная входит в свое уравнение с коэффициентом 1, во все остальные уравнения эта переменная входит с коэффициентом 0. Любую переменную можно сделать базисной в любом уравнении.

Пример задачи с решением:

Опорные решения

К оглавлению…

Далее будем считать, что система (3.9) и эквивалентная ей система (3.15) являются системой ограничений некоторой канонической ЗЛП. Поэтому на переменные наложены условия неотрицательности. Свободные переменные системы (3.15) уже не совсем свободны. Они могут принимать только неотрицательные значения и только такие, что вычисленные по формулам (3.16) значения базисных переменных также получаются неотрицательными.

Среди бесконечного множества решений системы (3.15) мы выделим конечный набор решений, каждое из которых называется опорным. Исключительная роль опорных решений (ОР) при поиске оптимального решения ЗЛП будет обоснована позже. А сейчас просто определим, что такое опорное решение.

Пусть система (3.9) записана в стандартной форме. Решение, в котором все свободные переменные равны нулю, и есть опорное. Следовательно, в любом опорном решении базисные переменные равны правым частям системы ограничений.

Чтобы все базисные переменные были неотрицательными, все правые части должны быть неотрицательными.

Система (3.13) не позволяет получить ОР. Если положить

Попробуем найти несколько ОР системы (3.10). Для этого каждый раз нужно указать пару базисных переменных и привести систему к стандартной форме. Если обе правые части окажутся неотрицательными, ОР налицо. В общем случае можно выбрать наборов базисных переменных, всего, следовательно, ОР не более чем штук. Для системы (3.10) получаем вариантов выбора базисных переменных. Один из них — — мы уже рассмотрели, осталось 5 возможностей:

Перейдем от системы (3.13) к системе, в которой базисная переменная первого уравнения — . Для чего поделим на -1,4 все коэффициенты первого уравнения и исключим затем из второго уравнения. Получим систему

ОР таково:

Коротко это можно записать так:

Сделаем теперь базисной переменной второго уравнения. Поделим все коэффициенты второго уравнения на 5/7 и затем исключим из первого уравнения. Получим систему

Соответствующее OP:

Переход от одного опорного решения к другому

К оглавлению…

Мы видели, как менялась система (ЗЛО) после совершения над уравнениями элементарных преобразований. Менялись коэффициенты при неизвестных и правые части, но не менялось множество решений этой системы. Далее будут выведены формулы, по которым можно пересчитать коэффициенты при неизвестных и правые части системы, приведенной к стандартной форме, когда в одном из уравнений заменяется базисная переменная.

Пусть в -м уравнении базисной была переменная , а станет переменная . Следовательно, переменная xs входит в -е уравнение с ненулевым коэффициентом . Чтобы переменная стала базисной, она должна входить в -е уравнение с коэффициентом 1. Значит, все коэффициенты при неизвестных и правую часть -го уравнения нужно разделить на число . Потом нужно исключить переменную из всех остальных уравнений системы. Если в -е уравнение переменная входит с коэффициентом , чтобы исключить ее из -го уравнения, нужно прибавить к нему -е уравнение (после деления на число ), умноженное на число —. Выпишем -е и -е уравнения до и после преобразований. В скобках указаны коэффициенты после преобразований.

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

Вычисления новых коэффициентов удобно свести в таблицу (табл. 3.1). Покажем расчеты на примере. Обратимся к системе (3.18) и заменим во втором уравнении базисную переменную на переменную .

В табл. 3.1 «упакована» система уравнений. Но в строках и столбцах стоят только коэффициенты при переменных, обозначения переменных вынесены в первую строку.

В части I табл. 3.1 записана система (3.18), в части II — преобразованная система. Базисная переменная заменена на переменную .

Чтобы переменная стала базисной во втором уравнении, нужно поделить все коэффициенты второго уравнения на число 1,2 — коэффициент при . Назовем коэффициент опорным элементом таблицы, покажем в таблице опорный элемент жирным курсивом. Новые коэффициенты второго уравнения указаны в части I табл. 3.1 в скобках рядом со старыми.

В части II табл. 3.1 можно заполнить вторую строку.

Пересчитаем элементы первой строки.

Во второй строке части I табл.3.1 в скобках записаны отношения Поэтому сразу можно записать:

Чтобы каждый раз не пользоваться громоздкой формулой, можно обратиться к простому геометрическому правилу пересчета коэффициентов («диагональному» правилу).

Нужно мысленно соединить пересчитываемое число и опорный элемент диагональю прямоугольника, а затем построить вторую диагональ. Так, если соединить число -4/5 с опорным элементом , то на второй диагонали окажутся числа . Чтобы получить новое значение коэффициента , нужно из прежнего значения вычесть произведение чисел, стоящих на второй диагонали, т.е.

Теперь можно указать новое OP:

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

Вырожденные и невырожденные опорные решения

К оглавлению…

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

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

В любом решении такого уравнения хотя бы одна из двух переменных меньше нуля. Исключим переменную из второго уравнения, а переменную из первого. Исходная система станет выглядеть так:

Если считать базисной переменйой первого уравнения переменную , получим OP = (1; 0; 0; 0); если считать, что базисная переменная первого уравнения — это , получается ОР = (0; 0; 1; 0). Оба эти ОР вырожденные, только одна базисная переменная больше нуля. После умножения на -2 второго уравнения и исключения из первого система приводится к виду

Никаких новых ОР не получено. Но теперь базисная переменная второго уравнения — . Таким образом, если задано вырожденное ОР, нужно дополнительно указать, какие из равных нулю переменных свободные, какие — базисные.

Выражение целевой функции Z через свободные переменные. Оценки свободных переменных

К оглавлению…

Рассмотрим каноническую ЗИП с системой ограничений, приведенной к стандартному виду.

Выразим свободные переменные через базисные и подставим эти выражения в целевую функцию . Когда целевая функция зависит только от свободных переменных, ее анализ упрощается, ведь свободные переменные могут принимать почти любые значения. Нужно только позаботиться о выполнении условия (3.22′) — неотрицательности всех переменных.

где через обозначены соответственно числа:

Числа

называются оценками свободных переменных

Число — это значение целевой функции , когда все свободные переменные равны 0.

Коротко выражение для оценки можно записать так: , где — вектор коэффициентов целевой функции при базисных переменных. В общем случае первая компонента этого вектора равна коэффициенту целевой функции при базисной переменной первого уравнения, вторая компонента вектора — коэффициент целевой функции при базисной переменной второго уравнения, последняя, -я компонента вектора — коэффициент целевой функции при базисной переменной -го уравнения.

Вектор

это вектор коэффициентов при переменной в системе (3.23).

Число — это скалярное произведение векторов и , где вектор

состоит из правых частей системы (3.22).

Число — это коэффициент при свободной переменной в целевой функции .

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

Выразим целевую функцию через свободные переменные (табл. 3.2).

В первой строке табл. 3.2 над переменными

записаны соответствующие коэффициенты целевой функции.

Число записано в последней строке столбца правых частей.

Числа

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

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

Итак, после исключения переменных и целевая функция такова:

Подчеркнем, что формулы

описывают одну и ту же целевую функцию, если только подставлять в эти выражения решения системы (3.25). Заметим еще, что запись

можно представить в виде

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

Это означает, что новые значения оценок свободных переменных и число можно пересчитывать, как и числа по формулам (3.19).

Анализ значений целевой функции Z, выраженной через свободные переменные. Признак неограниченности целевой функции в допустимой области

К оглавлению…

Рассмотрим ЗЛП из предыдущего примера. Выразим базисные переменные и целевую функцию через свободные переменные.

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

Тогда

На OP = (0,0,0, 4, 6) целевая функция равна -6. Можно ли увеличить значение ? Можно, если оставить, например, и равными нулю, а переменную сделать больше нуля. Тогда целевая функция возрастет, ведь

Можно ли беспредельно увеличивать значения ? Нет, ведь нужно следить за тем, чтобы переменные и оставались неотрицательными. Так как можно записать:

Переменная остается неотрицательной, пока верно неравенство Когда

Целевая функция увеличилась на 16. Новое ОР — = (0,4, О, 0, 18). Теперь базисными переменными стали переменные и . В табл. 3.3 показаны соответствующие преобразования.

Базисные переменные и целевая функция выражаются через свободные переменные так

Можно ли продолжать увеличивать ? Оставим переменные и равными нулю. От переменной целевая функция и базисные переменные зависят так

Если , значения переменных также больше нуля, а целевая функция неограниченно возрастает с возрастанием .

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

Теперь можно легко сформулировать общий признак неограниченности целевой функции в допустимой области.

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

Действительно, полагая все свободные переменные, кроме , равными 0, получаем, что

Для любой базисной переменной имеем:

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

Аналогично формулируется признак неограниченности целевой функции снизу.

, если существует такая свободная переменная , что а все коэффициенты

В этом случае

поэтому с возрастанием значения целевая функция убывает.

Попытаемся найти минимум целевой функции Для чего возвратимся к выражениям (3.28), (3.29) и к части I табл. 3.3.

Из (3.28) следует, что можно сделать меньше числа -6, если оставить переменные равными 0, а переменную сделать больше 0. Увеличивать переменную беспредельно нельзя. Если , то базисные переменные выражаются через так:

поэтому максимально возможное значение = 6, тогда переменная обратится в 0. Это значит, что получено новое ОР — = (0; 0; 6; 16; 0), на котором

Базисные переменные этого OP—, ; свободные переменные — . В табл. 3.4 преобразования выглядят следующим образом:

Целевая функция и базисные переменные выражаются через свободные переменные так:

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

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

К оглавлению…

Рассмотрим следующую ЗЛП

Система (3.31) такова, что — базисная переменная первого уравнения, — второго. Соответствующее ОР — вектор = (6; 0; 0; 0; 2), целевая функция на нем равна = -3 * 6 — 2 х 2 = -22.

Выразим целевую функцию и базисные переменные через свободные переменные.

Тогда

Можно ли подобрать такое допустимое решение системы (3.31), на котором целевая функция была бы меньше -22? Нельзя! И это сразу видно из (3.32). Когда все свободные переменные равны нулю, = -22. Но стоит хотя бы одной свободной переменной стать больше нуля, как сразу увеличится, в (3.32.) все свободные переменные входят с положительными коэффициентами. Итак, = -22, достигается минимальное значение целевой функции на ОР = (6; 0; 0; 2).

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

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

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

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

Соответствующие ОР являются оптимальными.

Попробуем найти максимум целевой функции (3.30). Из (3.32) следует, что целевую функцию можно увеличить, если одну из переменных сделать больше нуля. Пусть, например, переменная станет больше нуля, а переменные останутся равными нулю. Тогда

Переменную можно увеличивать до тех пор, пока обе переменные неотрицательны. Переменная станет равной нулю, когда = 3; переменная станет равной нулю, когда = 2. Значит, не может быть больше 2. При = 2 получается новое ОР: =(2; 2; 0; 0; 0).

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

Выведем общее правило, позволяющее определить, какую из базисных переменных должна заменить выбранная свободная переменная. Как мы только что видели, это должна быть та базисная переменная, которая первой обращается в 0 при увеличении свободной переменной.

Пусть — свободная переменная, которую нужно сделать больше нуля, чтобы увеличить (уменьшить) целевую функцию. Пусть — базисные переменные, которые зависят от (в предположении, что все остальные свободные переменные равны нулю) следующим образом:

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

Из уравнения

следует, что обращается в 0, когда

Следовательно, та переменная обращается в 0 первой, для которой отношение (3.36) минимально. В только что рассмотренном примере min (6/2; 2/1) = 2, достигался он на отношении, соответствующем базисной переменной (базисной переменной второго уравнения). Поэтому переменная сменила во втором уравнении в качестве базисной переменную .

Базисная переменная заменяется в том уравнении, для которого достигается минимум отношения

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

Так как

то увеличивать можно до тех пор, пока не обратится в 0, т.е. до числа 0,4. Тогда

Очередное ОР:

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

Обратимся к табл. 3.6. Не будем больше явно выписывать выражения для — они легко определяются по таблице.

Продолжим увеличение . Пусть переменная станет больше 0, т.е. превратится в базисную переменную.

Так как

то переменная будет только возрастать при увеличении , а переменная будет уменьшаться. Она уменьшится до нуля, когда станет равной 2,4/1 = 2,4. На новом OP = (0; 0; 2,4; 2,8; 0) целевая функция равна -6,8 + 5 х 2,4 = 5,2.

Перейдем к табл. 3.7, где записана стандартная форма системы уравнений при ОР , когда базисными являются переменные (в первом уравнении) и (во втором уравнении).

Оценки всех свободных переменных положительные,

Целевую функцию нельзя более увеличить. Оптимальные значения переменных:

Теорема о достижимости оптимального значения целевой функции задачи линейного программирования на опорном решении

К оглавлению…

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

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

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

Новое значение переменной равно числу

а новое значение равно числу

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

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

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

В случае вырожденности ОР признак оптимальности не является необходимым. Приведем пример, подтверждающий это утверждение. Рассмотрим такую ЗЛП.

Для ОР = (0; 0; 0; 1) признак оптимальности не выполняется, так как . Целевую функцию можно было бы увеличить, если можно было бы увеличить переменную . Но как только станет больше 0, переменная станет меньше 0. Поэтому . Если поменять в первом уравнении базисные переменные, заменить переменной то система ограничений и целевая функция примут вид

Теперь все оценки свободных переменных положительны, поэтому ясно, что на векторе = (0; 4; 0; 2; 2) целевая функция достигает максимума.

Для дальнейшего нам потребуется знать, как меняется ЗЛП, если изменить ее правые части. Рассмотрим пример.

Пример задачи с решением:

Симплекс-метод решения задачи линейного программирования. Описание симплекс-метода

К оглавлению…

Симплекс-метод изобрел американский математик Дж. Данциг. Метод основан на доказанных в предыдущей главе свойствах опорных решений и состоит из следующих шагов (предполагается, что исходная ЗЛП приведена к каноническому виду).

Шаг 1. Получить исходное ОР данной задачи.

Шаг 2. Проверить, выполняется ли для данного ОР признак оптимальности. Если это так, оптимальное решение получено, конец. В противном случае перейти к шагу 3.

Шаг 3. Проверить, выполняется ли для данного ОР признак неограниченности целевой функции в допустимой области. Если это так, задача не имеет решения. Конец. В противном случае перейти к шагу 4.

Шаг 4. Если ищется максимум целевой функции, выбрать любую свободную переменную с отрицательной оценкой (например, переменную с наименьшим номером); если ищется минимум целевой функции, выбрать любую свободную переменную с положительной оценкой (например, переменную с наименьшим номером). Выбранная свободная переменная становится базисной.

Шаг 5. Выбрать уравнение, в котором заменяется базисная переменная. Номер этого уравнения определяется по правилу минимума:

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

Шаг 6. Перейти к новому ОР, используя формулы (3.20).

Шаг 7. Перейти к шагу 2.

Решение оформляется в так называемых симплекс-таблицах. Построенные ранее табл. 3.1-3.13 являются симплекс-таблицами.

Так как число ОР конечно, через конечное число шагов алгоритм закончит работу либо на шаге 2, либо на шаге 3.

Чтобы описанный алгоритм заработал, нужно научиться получать исходное ОР данной ЗЛП. Если система ограничений приведена к каноническому виду, получение стандартной формы системы уравнений — задача того же порядка сложности, что и нахождение оптимального решения в соответствии с шагами 2-7.

Описанию способа получения исходного ОР посвящен следующий параграф.

Получение исходного ОР. Метод искусственного базиса

К оглавлению…

Пусть система уравнений ЗЛП приведена к каноническому виду

Но система ограничений (4.1) не записана в стандартной форме, в уравнениях (4.1) не выделены базисные переменные.

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

В каждое из уравнений системы (4.1) добавлена искусственная базисная переменная. ЗЛП (4.2) — (4.3′) можно начать решать симплекс-методом. Относительно решения задачи (4.2) — (4.3′) можно сказать следующее.

  1. Целевая функция ограничена снизу числом 0, , ведь по условию . Следовательно, случай невозможен, задача (4.2) — (4.3′) всегда имеет решение.
  2. Если , то система (4.1) не имеет ни одного решения, уравнения (4.1) несовместны: если — допустимое решение системы (4.1), то — допустимое решение системы (4.3). Но , противоречие с предположением .
  3. Если , то все искусственные переменные равны 0. Следовательно, в оптимальном ОР задачи (4.2) — (4.3′) базисными являются переменные системы (4.1). Тогда искусственные переменные можно просто отбросить и перейти к системе (4.1), записанной в стандартной форме.

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

Пример задачи с решением:

Об альтернативных оптимальных решениях задачи линейного программирования

К оглавлению…

Решая ЗЛП графически, мы видели, что оптимальное решение не обязательно единственно. Экстремум целевой функции может достигаться во всех точках некоторого отрезка, тогда оптимальных решений бесконечно много. Обобщим этот результат на случай задачи с переменными.

Если оценка некоторой свободной переменной равна нулю, то переход к ОР, в котором эта переменная станет базисной, не приведет к изменению значения целевой функции на новом ОР, ведь

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

Пример задачи с решением:

Об анализе на чувствительность

К оглавлению…

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

Примеры задач с решением:

Основы теории двойственности. Определение пары двойственных задач

К оглавлению…

Рассмотрим пару задач линейного программирования, связанных между собой симметричными зависимостями. В частности, целевая функция одной задачи максимизируется, другой — минимизируется. Задачу, для которой требуется найти максимум целевой функции, назовем задачей (1), симметричную ей задачу — задачей (2). Условимся все ограничения-неравенства задачи (1) записывать в виде , все ограничения-неравенства задачи (2) — в виде . Целевую функцию задачи (1) обозначим буквой , целевую функцию задачи (2) — буквой .

Задачи (1) и (2) называют парой двойственных задач линейного программирования (или просто двойственной парой), если выполнены следующие соотношения:

  1. В задаче (1) неизвестных и ограничений (без учета условий неотрицательности), в задаче (2) неизвестных и ограничений (без учета условий неотрицательности). Ограничения задачи (1) находятся во взаимно однозначном соответствии с переменными задачи (2). Переменные задачи (1) находятся во взаимно однозначном соответствии с ограничениями задачи (2). Переменные задачи (1) обозначим через ; переменные задачи (2) — через .
  2. Матрицы ограничений задач (1) и (2) взаимно транспонированы. Строка коэффициентов системы ограничений задачи (1)— это столбец коэффициентов системы ограничений задачи (2) и наоборот. Если — это коэффициенты при переменной в -ом ограничении задачи (1), , то в задаче (2) коэффициент стоит при переменной в -м ограничении.
  3. Правые части системы ограничений задачи (1) — это коэффициенты целевой функции задачи (2); коэффициенты целевой функции задачи (1) — это правые части системы ограничений задачи (2). Если — правая часть -го ограничения задачи (1), то — коэффициент при в целевой функции задачи (2), . Если — коэффициент при в целевой функции задачи (1), то — правая часть -го ограничения задачи (2 ), .
  4. Каждому ограничению-неравенству задачи (1) соответствует условие неотрицательности ассоциированной с этим ограничением переменной задачи (2). Каждому ограничению-равенству задачи (1) соответствует переменная задачи (2) без ограничений на знак. Наоборот, каждому ограничению-неравенству задачи (2) соответствует неотрицательная переменная задачи (1), каждому ограничению-равенству задачи (2) соответствует переменная задачи (1) произвольного знака.

Задача (1) называется двойственной задаче (2); задача (2) — двойственной задаче (1).

Из определения двойственной пары следует, что отношение двойственности взаимное, задача, двойственная двойственной, совпадает с исходной задачей.

Примеры задач с решением:

Несколько замечаний об умножении матриц

К оглавлению…

Умножить матрицу на матрицу можно, если число столбцов матрицы равно числу строк матрицы . Если матрица содержит строк и столбцов, а матрица состоит из строк и столбцов, то произведение — это матрица, в которой строк и столбцов, причем

Вектор — частный случай матрицы. В зависимости от ситуации, вектор можно считать вектор-строкой (1 строка и столбцов) или вектор-столбцом ( строк, 1 столбец).

Так, в записи векторы и — это вектор-столбцы. Это же равенство можно записать так: , но теперь и — вектор-строки.

Вектор-строку можно умножать на матрицу слева, в результате получится вектор-строка. Вектор-столбец можно умножать на матрицу справа, в результате получится вектор-столбец. Например,

Произведение матриц транспонируется по правилу

К оглавлению…

Транспонированная вектор-строка — это вектор-столбец; транспонированный вектор-столбец — это вектор-строка. В частности, система ограничений задачи (5.4): , где и — это вектор-столбцы, транспонируется так: , где и уже вектор-строки. Далее будут использованы обе возможности записи системы ограничений в матрично-векторной форме.

Множество решений системы линейных уравнений не изменится, если матрицу и вектор-столбец умножить слева на одну и ту же невырожденную матрицу . Система эквивалентна системе .

Единичной матрицей называется квадратная матрица, в которой на главной диагонали стоят единицы, а остальные элементы равны 0.

Если — квадратная невырожденная матрица, то существует невырожденная матрица называемая обратной матрице , такая, что

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

Столбцы матрицы — это столбцы коэффициентов при переменных .

Система линейных уравнений эквивалентна системе , а в матрице первые строк и столбцов образуют единичную матрицу, переменные в этой системе — базисные.

Несколько замечаний о свойствах скалярного произведения векторов

К оглавлению…

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

Если векторы и неотрицательны, , то

, где — квадратная матрица с строками.

Теоремы двойственности

К оглавлению…

Теорема 1 (основное неравенство теории двойственности).

Если и — произвольные допустимые решения пары двойственных задач (5.3), (5.4), то

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

Следствие 1. Если допустимые решения и пары двойственных задач (5.3) и (5.4) таковы, что , то и — оптимальные решения этих задач.

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

Следствие 2. Если целевая функция задачи (5.3) не ограничена сверху на допустимом множестве задачи (5.3), то у задачи (5.4) нет ни одного допустимого решения. Если целевая функция задачи (5.4) не ограничена снизу на допустимом множестве задачи (5.4), то у задачи (5.3) нет ни одного допустимого решения.

Пусть, например, целевая функция не ограничена сверху, а у задачи (5.4) есть допустимые решения и — одно из них. Обозначим через значение целевой функции на ректоре . В силу неограниченности целевой функции существует такое допустимое решение задачи (5.3), на котором Получено противоречие с основным неравенством.

Первая теорема двойственности

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

Будем предполагать, что известно оптимальное решение задачи (5.3). Чтобы провести доказательство в другую сторону, нужно привести задачу (5.4) к каноническому виду.

Одновременно с общим доказательством покажем на конкретном примере, как, имея оптимальную симплекс-таблицу для задачи (5.3), получить оптимальное решение задачи (5.4).

Примеры задач с решением:

Вторая теорема двойственности

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

Необходимое и достаточное условие оптимальности допустимых решений и можно записать в виде совокупности равенств. Пусть

Тогда

В силу допустимости векторов

можно записать такую цепочкуравенств:

Скалярное произведение неотрицательных векторов

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

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

Условия (5.10) называются условиями дополняющей нежесткости.

Другими словами, если переменная задачи (5.3) отлична от нуля, соответствующее ей -e ограничение двойственной задачи обращается в строгое равенство.

Приведенные рассуждения легко обратить (провести их в обратном порядке). Тогда из условий (5.10) вытекает равенство целевых функций и задач (5.3) и (5.4).

Примеры задач с решением:

Двойственный симплекс-метод

К оглавлению…

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

При решении задачи (5.3) симплекс-методом идет перебор допустимых решений задачи (5.3). На всех итерациях, кроме последней, векторы не являются допустимыми решениями задачи (5.4). Но условия дополняющей нежесткости выполняются всегда. Действительно, если (т.е. — базисная переменная), то . Это означает, что -е ограничение двойственной задачи превращается в строгое равенство на векторе .

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

Пример задачи с решением:

Двойственность и анализ на чувствительность

К оглавлению…

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

Щей анализа на чувствительность опишем, решая следующую задачу линейного программирования

Применим метод искусственного базиса (табл. 5.5).

Оптимальные значения переменных:

Кроме того,

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

Матрицу можно вычислить непосредственно по матрице , а можно и по оптимальной симплекс-таблице. Нужно только продолжить формально вычисление столбца . Если эти вычисления выполнить, коэффициенты при переменной будут такими:

Как уже было показано, столбцы матрицы — это столбцы оптимальной симплекс-таблицы, которые были единичными в исходной симплекс-таблице. Таким образом,

Контроль:

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

Изменение значений правых частей системы ограничений

Пусть изменился вектор правых частей . Изменение правых частей исходной системы уравнений влечет изменение последнего столбца (столбца правых частей) симплекс-таблиц. Обозначим вектор новых правых частей через . Положим , где —: вектор-столбец изменений правых частей. Тогда новый столбец правых частей в последней симплекс-таблице будет таким:

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

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

Обе правые части по-прежнему больше 0. Оптимальное решение ЗЛП

дается вектором

Изменение коэффициентов целевой функции

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

Включение в исходную модель дополнительных переменных

Если в исходную модель включаются новые переменные

то в матрице появляются новые столбцы; образующие матрицу :

Вектор коэффициентов целевой функции получает размерность , в целевой функции появляются новых коэффициентов, Обозначим через вектор .

В последней симплекс-таблице матрица расширится на матрицу

а у вектора оценок появятся новые компоненты

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

Пусть, например, задача (5.26) изменилась так:

Здесь

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

Включение дополнительных ограничений

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

Пусть в систему ограничений задачи (5.30) добавилось неравенство . Превратим неравенство в уравнение . Переменная становится базисной переменной третьего уравнения. Чтобы добавить это уравнение в оптимальную симплекс-таблицу, нужно выразить базисные переменные и через свободную переменную (см. табл. 5.5, ч. III):

Уравнение

примет вид

Последняя симплекс-таблица станеттакой (табл. 5.6):

В табл. 5.6 стоит недопустимое решение, так как . Поиск оптимального решения следует продолжить с помощью двойственного симплекс-метода.

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

К оглавлению…

Математическая модель транспортной задачи (ТЗ) рассматривалась в главе 1. Повторим ее описание.

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

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

Кроме того, будем рассматривать только закрытые ТЗ, когда сумма всех запасов равна сумме всех потребностей

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

Ограничения (6.2) называют ограничениями по запасам (их штук). В каждом таком ограничении записано условие полного использования запасов данного поставщика.

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

Любую открытую

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

Условие ТЗ удобно записывать в матрице, которая называется матрицей перевозок. В ней + 1 строка и + 1 столбец. В первой строке указаны величины потребностей, в первом столбце — значения запасов. В клетках внутренней матрицы (их штук) записывают стоимости перевозок и сами перевозки. Стоимости перевозок условимся записывать в правом верхнем углу клеток. Нумеровать будем только строки и столбцы внутренней матрицы.

Ниже приведена матрица перевозок закрытой ТЗ с тремя поставщиками и пятью потребителями (табл. 6.1).

Если бы, например, потребность равнялась не 60, а 40, нужно было бы ввести еще одного потребителя с потребностью и с нулевыми стоимостями . Матрица перевозок тогда станет следующей (табл. 6.2).

Запишем математическую модель первой из указанных задач. В ней 3×5 = 15 переменных.

Методы получения исходного допустимого решения ТЗ

К оглавлению…

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

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

Для рассматриваемой ТЗ получается исходное решение, представленное в табл. 6.3 (нулевые перевозки не пишутся).

Найдем значение целевой функции.

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

Целевая функция равна:

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

Минимальное значение стоимости равно 2, таких стоимостей 3:

Начнем, например, с перевозки . Максимально возможное значение равно 10. Полагаем = 10 и вычеркиваем первый столбец. Запасы первого поставщика теперь равны 20. Обратимся к перевозке Ее нужно положить равной 20, так как . Теперь вычеркиваются первая строка и пятый столбец. Далее полагаем и вычеркиваем третью строку. Четвертому потребителю требуется доставить еще 10 единиц товара. В матрице остались не-вычеркнутыми вторая, третья, четвертая клетки второй строки. Минимальная стоимость в невычеркнутых клетках равна 4 . Полагаем . Затем полагаем

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

Задача, двойственная к транспортной задаче. Соотношения двойственности и описание метода потенциалов

К оглавлению…

Математическая модель двойственной задачи. Построим задачу, двойственную к ТЗ. Начнем с простого примера. Пусть , а сама модель следующая:

Дадим переменным сквозную нумерацию

и запишем систему ограничений так, чтобы в -м столбце стояла переменная

Затем построим математическую модель двойственной задачи.

Двойственные переменные, соответствующие ограничениям по запасам, традиционно обозначаются буквой . Двойственные переменные, соответствующие ограничениям по потребностям, обозначаются буквой . В нашем случае получились две двойственные переменные , три двойственные переменные : . Ограничений в двойственной задаче 6, а ее математическая модель такова

Условия неотрицательности на двойственные переменные не накладываются, ведь все ограничения транспортной задачи — это ограничения-равенства.

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

при ограничениях

Соотношения двойственности и описание метода потенциалов.

Для пары двойственных задач (6.1) — (6.4) и (6.5) — (6.6) условия дополняющей нежесткости формулируются следующим образом.

Допустимые решения и двойственной пары (6.1) — (6.4) и (6.5) — (6.6) оптимальны тогда и только тогда, когда справедливы равенства:

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

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

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

Проверим на оптимальность решение, найденное по методу северо-западного угла. Оно заведомо не оптимально, по методу минимальной стоимости построено решение с меньшим значением целевой функции.

Так как ненулевых перевозок 7:

то для определения восьми неизвестных потенциалов имеется 7 уравнений:

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

Мы удовлетворили всем условиям дополняющей нежесткости. Найдем для каждой незанятой клетки сумму соответствующих потенциалов и сравним ее со стоимостью, записанной в этой клетке,

Ограничения двойственной задачи нарушаются четыре раза. Соответствующие клетки называются потенциальными, в матрице они отмечены знаком «•» (табл. 6.5).

Проверим на оптимальность решение, полученное по методу минимальной стоимости (табл. 6.6).

В этой матрице всего 6 ненулевых перевозок. Для определения восьми неизвестных потенциалов имеется всего 6 уравнений.

Пусть , тогда

Цепочка расчета потенциалов оборвалась, не хватает одного условия. Запишем в матрице явно еще одну перевозку, хотя ее значение и равно 0, так, чтобы восстановить оборванную цепочку расчетов, добавить недостающее условие дополняющей нежесткости. Нулевую перевозку нужно проставить в любой клетке, для которой один потенциал известен, а другой — неизвестен. Значение неизвестного потенциала находится из условия дополняющей нежесткости, как будто в клетке стоит ненулевая перевозка. Например, занесем нулевую перевозку в клетку (1; 3). Теперь эта клетка считается занятой, для нее должно выполняться равенство

Значение потенциала известно, поэтому значение можно найти:

Появление этого нуля можно обосновать и так. На втором шаге пришлось вычеркнуть и первую строку, и пятый столбец (именно из-за этого и «потерялось» одно условие дополняющей нежесткости). Вычеркнем только пятый столбец, а первую строку оставим (хотя запасы первого поставщика равны 0). Тогда еще через шаг в клетку с минимальной стоимостью 3 заносится нулевая перевозка и вычеркивается первая строка. Ясно, что подобный прием позволяет и в случае применения метода северозападного угла, и для метода минимальной стоимости всегда вычеркивать на промежуточных шагах только строку или столбец. На последнем шаге вычеркнутся и строка, и столбец, а в матрице окажется занятых клеток. Быть может, в некоторых из них будут стоять нулевые перевозки.

Далее находятся потенциалы

и

Проверка на соответствие системе ограничений двойственной задачи показывает, что нарушается условие так как 0 +4 > 3 (см. табл. 6.6). И это решение не оптимально.

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

Циклы в матрице

К оглавлению…

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

Из определения цикла следует, что звенья могут пересекаться, но только не в вершинах.

Свойства циклов.

  1. В каждой строке (столбце) матрицы лежит четное число вершин цикла. Это следует из того, что у каждой вершины цикла есть ровно одна вершина, смежная с ней и расположенная в той же строке (столбце). Поэтому в каждой строке (столбце) матрицы вершины цикла разбиваются на непересекающиеся пары смежных вершин.
  2. Число вершин цикла четно. Это свойство непосредственно следует из свойства 1.
  3. Если в матрице с строками и столбцами произвольно отмечены клеток, то существует цикл, все вершины которого лежат в отмеченных клетках.

Доказательство проведем методом математической индукции по числу

База индукции. Если

цикл очевиден.

Индуктивное предположение. Пусть утверждение верно для всех , не превосходящих некоторого числа .

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

а) В матрице есть строка (столбец), в которой (котором) лежит не более одной отмеченной клетки. Мысленно удалив эту строку (столбец), получим матрицу с строками и столбцами, в которой отмечены не менее клеток. По предположению индукции в такой матрице строится цикл.

б) В каждой строке (столбце) матрицы лежит не менее двух отмеченных клеток. (Несущественное замечание: случай б) возможен тогда, когда , а в каждой строке (столбце) лежат ровно две отмеченные клетки.)

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

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

а) Этот цикл единственен.

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

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

Из единственности цикла следует утверждение б).

Выберем произвольную вершину цикла и отметим ее знаком «+». Перейдем по строке (столбцу) в смежную вершину и отметим ее знаком «-». Обходя последовательно вершины цикла, припишем им поочередно знаки «+» и «-», пока не пометим все вершины (рис. 6.4). Число вершин в цикле четно, противоречия при расстановке знаков не случится. Любая пара смежных вершин окажется помеченной разными знаками, поэтому в любой строке (столбце) матрицы число вершин цикла, которым приписан знак «+», равно числу вершин цикла, которым приписан знак «-». Цикл, вершины которого помечены описанным способом, называется означенным циклом.

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

Рассмотрим матрицу перевозок транспортной задачи, в которой стоит допустимое решение ТЗ, состоящее из т + п — 1 перевозок. Некоторые из перевозок могут быть нулевыми. Клетки матрицы перевозок с явно указанными перевозками назовем занятыми, остальные клетки — свободными.

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

Действительно, в силу указанного в параграфе 6.2 свойства таких решений, в матрице перевозок существует строка (столбец), в которой (котором) лежит только одна занятая клетка. В такой строке (столбце) нельзя поместить вершину цикла. После вычеркивания этой строки (столбца) в матрице вновь появляется строка (столбец) с единственной перевозкой. И в этой строке (столбце) не может лежать вершина цикла. В результате окажутся вычеркнутыми все строки и столбцы матрицы, места для цикла нет. Цикл пересчета. Циклом пересчета называется означенный цикл, построенный в матрице перевозок ТЗ. Все вершины цикла, кроме одной, лежат в занятых клетках, и только одна вершина, причем помеченная знаком «+», лежит в свободной клетке. Пример цикла пересчета показан в табл. 6.7. Свободная клетка — (1,5).

Сдвигом по циклу пересчета на число называется следующая операция. Ко всем перевозкам, стоящим в клетках, содержащих вершины цикла со знаком «+», прибавляется число . Из всех перевозок, стоящих в клетках, содержащих вершины цикла со знаком «-», вычитается число . Значит, чтобы перевозки остались неотрицательными, число не должно превышать минимальной из перевозок, отмеченных знаком «-».

После сдвига по приведенному в табл. 6.7 циклу пересчета на число 10 получится матрица перевозок, приведенная в табл. 6.8.

Сдвиг по циклу переводит допустимое решение ТЗ в другое допустимое решение. Это вытекает из свойства 5 циклов (см. выше): в каждой строке (столбце) матрицы лежит одинаковое число вершин цикла пересчета, отмеченное знаками «+» и «-», сумма перевозок, стоящих в каждой строке (столбце), не меняется после сдвига по циклу. Это и означает допустимость нового решения (сумма перевозок в -й строке равна запасам -го поставщика; сумма перевозок в -м столбце равна потребности -го потребителя, ).

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

Для решения из табл. 6.7 максимальная величина сдвига равна , сразу две перевозки обратятся в 0. Чтобы число занятых клеток по-прежнему было равно 7, проставим явно нулевую перевозку в одной из освободившихся клеток. Пусть это будет клетка с меньшей стоимостью . Результаты сдвига показаны в табл. 6.9.

Новое значение целевой функции равно

Целевая функция уменьшилась на 200 единиц.

Из свойства 4 циклов (параграф 6.4) следует, что если в матрице перевозок стоит такое допустимое решение ТЗ, что нельзя построить цикл, все вершины которого лежат в занятых клетках, после сдвига по циклу пересчета цикл, все вершины которого лежат в занятых клетках, вновь не строится.

Начнем с матрицы перевозок с допустимым решением, построенным по методу северо-западного угла или минимальной стоимости. Если это решение окажется неоптимальным, будем его улучшать, уменьшать значение целевой функции ТЗ, проводя сдвиг по циклу пересчета. Всякий раз в матрице перевозок окажется допустимое решение с перевозками (некоторые могут равняться 0).

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

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

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

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

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

Таким образом, если клетка — потенциальная, целевая функция уменьшится в результате сдвига по циклу. Докажем формулу (6.9).

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

Изменение целевой функции после сдвига по циклу равно

ведь в соответствии с правилами сдвига перевозки, отмеченные знаком «+», увеличиваются на , перевозки, отмеченные знаком «-», уменьшаются на .

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

Подставляя формулы (6.11) в (6.10), получим

В рассмотренном примере клетка (1, 5) была потенциальной:

Величина сдвига

Как уже было сказано, целевая функция уменьшилась на 200 единиц.

Проверим на оптимальность вновь полученное решение (табл. 6.10).

Положим , тогда

В матрице имеется единственная потенциальная клетка — (2, 5), так как

Построим для нее цикл пересчета. Так случилось, что в одной из вершин, помеченных знаком «-», стоит нулевая перевозка. Сдвиг можно произвести только на величину = 0. Изменения целевой функции не будет,

Но после сдвига нулевая перевозка переместится во вторую строку (табл. 6.11). Проверим на оптимальность новое решение.

Если

Клетка (1, 3) — потенциальная,

Построим для потенциальной клетки цикл пересчета. Можно произвести сдвиг по циклу на величину = 20. Оставим нулевую перевозку в клетке (1,5) , клетка (2,3) станет свободной (табл. 6.12). Новое значение целевой функции равно 470, она уменьшилась на 20 единиц,

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

Оптимальные значения переменных:

Описание метода потенциалов

К оглавлению…

Чтобы решить ТЗ методом потенциалов, нужно выполнить следующие действия.

  1. Определить исходное допустимое решение ТЗ по методу северо-западного угла или минимальной стоимости. В этом решении должны быть заданы перевозок, некоторые из них могут равняться 0.
  2. В соответствии с условиями дополняющей нежесткости рассчитать значения потенциалов правилу , если клетка занята перевозкой.
  3. Проверить, удовлетворяют ли найденные значения потенциалов системе ограничений задачи, двойственной к транспортной: . Если это так, то вектор и вектор — оптимальные решения соответственно ТЗ и двойственной задачи. В противном случае перейти к шагу 4.
  4. Выбрать любую потенциальную клетку (такую клетку, что для нее ) и построить для выбранной клетки цикл пересчета. Произвести сдвиг по циклу на величину , где — перевозки, стоящие в вершинах цикла, отмеченных знаком «-».

После сдвига по циклу значение целевой функции ТЗ уменьшится на величину . Перейти к шагу 2.

Еще один пример (блокирование перевозок)

К оглавлению…

Решим такую транспортную задачу (табл. 6.13.) при дополнительном условии, что все запасы третьего поставщика должны быть полностью вывезены.

Эта задача открыта,

Нужно добавить еще одного потребителя с потребностью

Дополнительное условие означает, что третий поставщик не может поставлять товар фиктивному потребителю, поэтому . Если существуют такие допустимые решения нашей ТЗ, что , то оптимальное решение — одно из них (когда ). После закрытия задачи матрица перевозок примет вид (табл. 6.14).

Найдем исходное допустимое решение по методу минимальной стоимости и проверим его на оптимальность (табл. 6.15).

Целевая функция равна

После расчета потенциалов выясняется, что в матрице имеется одна потенциальная клетка — (2, 5), так как

Построим для этой клетки цикл пересчета. Величина сдвига

Проверим на оптимальность новое решение (табл. 6.16).

Потенциальных клеток больше нет,

Оптимальные значения перевозок:

Неиспользованными остались 10 единиц запасов первого поставщика и 30 единиц запасов второго. Оптимальные значения переменных двойственной задачи:

Паросочетания. Определения и примеры

К оглавлению…

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

Припишем каждому ребру вес . Задача о максимальном паросочетании (ЗМП) ставится так: найти паросочетание максимального веса. Вес паросочетания определяется как сумма весов ребер, составляющих паросочетание:

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

В частном случае, когда вес всех ребер равен единице, ЗМП сводится к задаче о наибольшем паросочетании (ЗНПС). Далее мы рассмотрим частный случай ЗМП — задачу о назначениях (ЗН), которая часто встречается в приложениях, а также транспортную задачу (ТЗ), которая является обобщением ЗН.

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

— чередующаяся.

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

Чередующаяся цепь называется увеличивающей, если ее первая и последняя вершины открыты. Рассмотренная только что цепь является увеличивающей.

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

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

Основная теорема о наибольших паросочетаниях

К оглавлению…

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

Необходимость следует из определения увеличивающей цепи.

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

Обозначим через подграф — множество ребер, входящих только в одно из двух паросочетаний и . Никакая вершина из не может иметь степень, большую 2, в противном случае два или более ребер из (или ) будут смежными, что противоречит определению паросочетания. Значит, каждая из компонент связности графа есть либо изолированная вершина, либо простая цепь, либо цикл (рис. 7.3).

Цепь типа б) (см. рис. 7.3) существовать не может, она является увеличивающей для , что противоречит исходному предположению.

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

Остаются следующие возможности: а), г) и циклы типа д) с четным числом ребер. У каждого из этих графов четное число ребер и ровно половина из них принадлежит , а другая половина — . Значит, граф содержит поровну ребер из и . Добавляя к ним ребра, принадлежащие одновременно и , и , получаем, что число ребер в равно числу ребер в , т.е. — наибольшее паросочетание.

Рассмотрим в качестве примера граф, изображенный на рис. 7.2. В этом графе выделено паросочетание

Ребра увеличивающей цепи

не лежащие в , образуют новое паросочетание

изображенное на рис. 7.4.

Открытых вершин больше нет, поэтому не существует никаких увеличивающих относительно цепей, — наибольшее паросочетание.

Наибольшее паросочетание в двудольном графе

К оглавлению…

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

Если нужно показать, что граф является двудольным, для него принимают обозначение , подразумевая, что

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

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

Пусть во множестве содержится вершин, во множестве вершин. Обозначим через величину, равную 1, если в паросочетание включено ребро

и равную 0 в противном случае. Кроме того, =0, если в графе отсутствует ребро . Тогда задача линейного программирования записывается так: максимизировать

Условия (7.2) и (7.3) означают, что никакие два выбранных ребра не могут иметь общих вершин. Запишем задачу, двойственную задаче (7.1) — (7.3). Обозначим через двойственные переменные, соответствующие условиям (7.2), через — двойственные переменные, соответствующие условиям (7.3), через — двойственные переменные, соответствующие условиям (7.3′) . Тогда двойственная задача есть задача минимизации суммы

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

Обозначим через переменную, равную нулю, если вершина не вошла в -разделяющее множество, и равную единице в противном случае, . Для вершин множества введем обозначение . Кроме того, вводятся переменные , чтобы в задаче 1) — (7.3′) было переменных, равна 0, если (в графе есть ребро ),и равна 1,если (ребро (V., fr) в графе отсутствует). Тогда задача (7.4)—(7.6) и будет математической моделью задачи отыскания в двудольном графе минимального -разделяющего множества вершин.

Среди оптимальных решений задач (7.1) — (7.3) и (7.4) — (7.6) всегда есть целочисленные, ведь в любом графе, безусловно, существуют и минимальное -разделяющее множество вершин, и наибольшее паросочетание, поэтому можно воспользоваться первой теоремой двойственности, не обращая внимания на условия целочисленности переменных

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

Число ребер в наибольшем паросочетании двудольного графа равно числу вершин в минимальном -разделяющем множестве вершин. Эта теорема называется теоремой Кенига—Эгервари, по имени венгерских математиков, которые впервые ее доказали. Первоначально эта теорема формулировалась не для двудольных графов, а для так называемых (0, 1 )-матриц. К такой постановке мы обратимся в следующем параграфе,

Алгоритм отыскания увеличивающей цепи для паросочетания в двудольном графе

К оглавлению…

В дальнейшем будет удобно задавать двудольный граф с помощью матрицы из строк и столбцов. Чтобы упростить обозначения, перенумеруем вершины в каждом из множеств и будем обозначать ребро парой номеров его вершин: . На пересечении -й строки и -го столбца матрицы стоит 1, если в графе есть ребро

и стоит 0, если такого ребра нет. Подобные матрицы называются (0,1 )-матрицами. Строки и столбцы матрицы назовем общим термином «ряд». Клетки с единицами назовем допустимыми, с нулями — недопустимыми. Множество рядов покрывает допустимые клетки данной таблицы, если каждая допустимая клетка содержится хотя бы в одном ряду из этого множества. Совокупность допустимых клеток назовем независимой, если никакие две клетки не лежат в одном ряду.

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

В этих определениях теорема Кенига — Эгервари принимает вид: максимальное число независимых допустимых клеток равно минимальному числу рядов, покрывающих все допустимые клетки.

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

Шаг 1. Пометить все строки , не содержащие кружков (эти строки соответствуют открытым вершинам множества , меткой . Если таких строк нет, то данное паросочетание — наибольшее.

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

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

Шаг 4. Повторять шаги 2, 3 до тех пор, пока

а) либо будет помечен столбец, не содержащий кружка;

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

В случае б) ни одной увеличивающей цепи для паросочетания построить нельзя, оно — наибольшее. В случае а) перейти к шагу 5.

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

Пример задачи с решением:

Задача об оптимальных назначениях

К оглавлению…

Задача об оптимальных назначениях (ЗН) — это ЗМП для полного двудольного графа. Часто ей придается следующая формулировка. Имеется работ и исполнителей. Пусть — доход от выполнения -м исполнителем -й работы. Требуется назначить каждого исполнителя на одну и только одну работу так, чтобы суммарный доход был наибольшим.

Построим математическую модель задачи. Обозначим через переменную, равную единице, если -й исполнитель назначен на -ю работу, и нулю — в противном случае. Тогда ЗН сводится к такой задаче линейного программирования: максимизировать

при условиях

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

Часто ЗН формулируется как задача минимизации, если — не доход, а затраты на выполнение -м исполнителем -й работы. Так как целевая функция транспортной задачи, обобщающей ЗН, минимизируется, в дальнейшем и для целевой функции ЗН будем искать минимум. А переход от задачи минимизации к задаче отыскания максимума целевой функции осуществляется просто. Пусть

Положим,

Тогда задача минимизации выражения и задача максимизации функции

эквивалентны.

Если в ЗН число работ не равно числу исполнителей, достаточно ввести соответствующее дополнительное число работ (исполнителей) с одинаковыми затратами, равными нулю.

Далее будем считать, что матрица затрат квадратная.

Запишем задачу, двойственную к ЗН. Обозначим через двойственные переменные, соответствующие ограничениям (7.8) ; через — двойственные переменные, соответствующие ограничениям (7.9) .

Двойственная задача такова: максимизировать

при условиях

По второй теореме двойственности допустимые решения и , задач (7.7)—(7.9′) и (7.10)— (7.11)оптимальны тогда и только тогда, когда

(Условия дополняющей нежесткости).

Предположим, что найдено некоторое допустимое решение задачи (7.10) — (7.11).

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

а) в паросочетание вошли ребер;

б) число ребер паросочетания меньше .

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

В случае б) вектор — не оптимальное решение задачи (7.10) — (7.11), его можно улучшить. Прочеркнем в матрице затрат непомеченные строки и помеченные столбцы. Все допустимые клетки вычеркнутся, в матрице останутся только такие стоимости , для которых . Положим , если строка помечена, а столбец не помечен. Тогда .

Изменим значения двойственных переменных по правилу

Чтобы доказать допустимость нового решения, достаточно показать, что

если строка помечена, а столбец не помечен. Но это следует из способа выбора . При этом на новом решении целевая функция двойственной задачи увеличилась. Действительно, пусть число ребер в наибольшем паросочетании равно ; число непомеченных строк равно , число помеченных столбцов равно . Тогда . Целевая функция двойственной задачи на новом решении равна:

Теперь можно снова найти в матрице затрат те клетки, для которых

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

Формальное описание алгоритма.

Шаг 1. Найти допустимое решение двойственной задачи, положив

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

Шаг 2. Положить

Шаг 3. Решить задачу о наибольшем паросочетании, считая допустимыми клетки с нулями в матрице . Возможны два случая:

а) в паросочетание вошли ребер;

б) в паросочетание вошли ребер.

В случае а) перейти к шагу 6, в случае б) — к шагу 4.

Шаг 4. Прочеркнуть непомеченные строки и помеченные столбцы (минимальное покрывающее множество рядов) в матрице и найти минимальный элемент в оставшейся части матрицы ().

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

Перейти к шагу 2.

Шаг 6. Положить , если ребро входит в наибольшее паросочетание, — в противном случае. ЗН решена.

Для удобства вычислений шаг 5 можно записать несколько иначе.

Шаг 5. Вычесть из всех непрочеркнутых элементов матрицы затрат и прибавить к дважды прочеркнутым элементам. Перейти к шагу 3.

Пример задачи с решением:

Транспортная задача и венгерский алгоритм ее решения

К оглавлению…

Далее мы рассмотрим венгерский алгоритм решения ТЗ, предложенный создателями теории потоков в транспортных сетях Фордом и Фалкерсоном, которые обобщили алгоритм Куна решения ЗН. Рассмотрим коротко теорию Форда и Фалкерсона, в частности, теорему Форда — Фалкерсона о максимальном потоке и минимальном разрезе и основанный на ней алгоритм отыскания максимального потока в транспортной сети. Венгерский алгоритм двойственен по отношению к методу потенциалов, описанному ранее. В этом алгоритме происходит последовательное улучшение решения задачи, двойственной транспортной. Одновременно с оптимальным решением двойственной задачи получается и оптимальное решение ТЗ. Венгерский алгоритм свободен от эффекта вырожденности; на каждой итерации целевая функция двойственной задачи увеличивается на некоторое целое положительное число.

Потоки в сетях

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

для всякой дуги данного графа.

Через обозначено множество дуг графа , выходящих из вершины , через обозначено множество дуг графа , входящих в вершину .

Условие (8.1) называют уравнением сохранения потока. Оно означает, что суммарный поток, втекающий во всякую вершину, отличную от источника и стока, равен суммарному потоку, вытекающему из этой вершины.

Условие (8.2) означает, что поток на каждой дуге ограничен ее пропускной способностью.

Пример транспортной сети с заданными потоками на дугах показан на рис. 8.1. Числа над дугами означают пропускные способности, числа в скобках — потоки.

Дуга называется насыщенной, если

и ненасыщенной — в противном случае. На рис. 8.1 насыщенными являются дуги

Остальные дуги — ненасыщенные.

Из условия сохранения потока (8.1) следует, что суммарный поток, вытекающий из источника, равен суммарному потоку, втекающему в сток.

Для доказательства формулы (8.3) достаточно просуммировать потоки на дугах транспортной сети двумя способами. Первый раз надо суммировать потоки на дугах, считая, что каждая дуга выходит из некоторой вершины. Второй раз нужно вычислить ту же сумму, полагая, что каждая дуга входит в некоторую вершину. Затем применить (8.1).

Число называется величиной потока или просто потоком в транспортной сети. На рис. 8.1 показана транспортная сеть с потоком величины = 5 + 3= 6 + 2=8.

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

Задача максимизации выражения (8.3) при условиях (8.1) — (8.2) — это задача линейного программирования. Дадим сначала содержательное описание двойственной задачи. Затем опишем алгоритм построения максимального потока. Далее построим модель двойственной задачи и применим условия дополняющей нежесткости, чтобы доказать, что поток действительно максимален. Одновременно доказывается оптимальность найденного решения двойственной задачи.

Разрезы

Разобьем множество вершин транспортной сети на два непересекающихся подмножества и :

так, чтобы

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

Будем обозначать разрез символом .

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

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

Разрез сети, имеющий наименьшую пропускную способность, называется минимальным.

Для примера рассмотрим транспортную сеть, показанную на рис. 8.2. Числа над дугами означают их пропускные способности.

Для данной сети можно построить 8 разрезов. Назовем некоторые из них.

Пусть

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

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

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

Из неравенства (8.5) следует, что если мы построим поток такой величины и разрез такой пропускной способности , что , этот поток будет максимальным, а разрез — минимальным.

Если пропускные способности дуг — целые числа, то задача о максимальном потоке, очевидно, имеет решение.

Величина максимального потока не превышает

Но тогда и задача отыскания минимального разреза имеет решение, а по первой теореме двойственности оптимальные значения целых функций совпадают. Конструктивное доказательство этой теоремы дается так называемой теоремой Форда — Фалкерсона о максимальном потоке и минимальном разрезе.

Теорема Форда — Фалкерсона о максимальном потоке и минимальном разрезе

К оглавлению…

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

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

Пусть удалось найти цепь, соединяющую вершины и , дуги которой удовлетворяют следующим условиям:

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

2) на всех дугах цепи, которые проходятся в направлении, обратном их ориентации (обратных дугах), поток больше нуля.

На рис. 8.4 приведен пример такой цепи для сети на рис. 8.3.

В рассматриваемой цепи можно переслать дополнительный поток из источника в сток. Действительно, положим

где минимум берется по всем прямым дугам цепи;

где минимум берется по всем обратным дугам цепи;

Ясно, что . Для нашего примера

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

Рис. 8.4. Пример потока, который можно увеличить

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

Если

Если

Вершины множества определяются одна за другой, начиная с источника . Некоторая вершина включается во множество , если существует увеличивающая цепь от к . Так как поток — максимальный, не существует увеличивающей цепи из к , поэтому вершина окажется во множестве , мы действительно определили разрез. Из правила (8.9) построения множества следует, что если

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

Перепишем математическую модель задачи о максимальном потоке по-другому, упростив обозначения. Пусть всего в транспортной сети вершин, включая источник и сток. Припишем источнику номер 1, стоку — номер и, остальные вершины в произвольном порядке получают номера от 2 до — 1. Дуги будем обозначать номерами вершин, которые они соединяют. Поток на дуге обозначим

Пропускные способности дуг обозначим , причем если дуга отсутствует в транспортной сети, положим, что

Имеем:

Обозначим через переменные двойственной задачи, соответствующие ограничениям (8.11). Переменные, соответствующие ограничениям (8.12), обозначим

Математическая модель двойственной задачи такова:

Положим

Иначе говоря, , если вершина помечена , если вершина не помечена. Поэтому ; так как источник помечен, а сток не помечен.

Положим

Покажем, что построено допустимое решение задач (8.14) — (8.18).

Пусть . Тогда вершина помечена, вершина не помечена. Значит, дуга принадлежит разрезу , поэтому

Пусть . Значит, вершина не помечена, тогда дуга принадлежит разрезу , следовательно,

Пусть , тогда вершина помечена, что влечет

Пусть , тогда вершина — помечена, но сток не помечен, поэтому

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

Пусть

Разберем 4 случая.

Вершина помечена, вершина помечена. Тогда

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

Вершина помечена, вершина не помечена. Тогда

Вершина не помечена, вершина не помечена. Тогда

Пусть

Источник помечен, возможны два случая.

Вершина помечена, тогда

Вершина не помечена, тогда

Пусть

Сток не помечен, возможны два случая.

Вершина помечена, тогда

Вершина не помечена, тогда

Итак,

Теорема доказана.

Алгоритм Форда — Фалкерсона решения задачи о максимальном потоке (метод расстановки пометок)

К оглавлению…

Алгоритм Форда — Фалкерсона решения задачи о максимальном потоке следует непосредственно из доказательства теоремы Форда — Фалкерсона. В нем осуществляется систематический поиск увеличивающих цепей из источника в сток по правилу (8.9). Как только не удается найти увеличивающую цепь, алгоритм прекращает работу: в сети построен максимальный поток.

Формальное описание алгоритма.

Шаг 1. Пометить вершину меткой .

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

Шаг 3. Повторять шаг 2 до тех пор, пока:

а) или окажется помеченной вершина ;

б) или все возможные метки проставлены, а вершина осталась непомеченной.

В случае а) перейти к шагу 4, а в случае б) — к шагу 6.

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

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

Шаг 5. Стереть все пометки, кроме метки источника, и возвратиться к шагу 2.

Шаг 6. В транспортной сети построен максимальный поток. Множество дуг, ведущих из помеченных вершин в непомеченные, образует минимальный разрез. Конец.

Пример задачи с решением:

Алгоритм Форда — Фалкерсона для транспортной сети, имеющей вид двудольного графа

К оглавлению…

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

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

Пример транспортной сети дан на рис. 8.11. Соответствующая ей таблица — табл. 8.1.

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

Шаг 1. Пометить каждую строку , для которой разность больше 0, Меткой , где . Если ни одной такой метки приписать нельзя, данный поток — максимальный. Конец.

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

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

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока

а) не будет помечен столбец с разностью 0 или

б) новых пометок приписать нельзя и для всех помеченных столбцов

В случае а) перейти к шагу 5, в случае б) — к шагу 6.

Шаг 5. Найдена увеличивающая цепь от в . Восстановить эту цепь, ориентируясь по меткам строк и столбцов. Увеличить потоки на всех прямых дугах этой цепи и уменьшить потоки на всех обратных дугах этой цепи на величину

Стереть все пометки и возвратиться к шагу 1.

Шаг 6. Данный поток максимален. Помеченные строки и столбцы соответствуют вершинам множества минимального разреза.

Найдем максимальный поток для транспортной сети, показанной на рис. 8Л1 (табл. 8.2).

Шаг 1. Метим первую строку меткой .

Шаг 2. Метим второй столбец меткой .

Шаг 3. От второго столбца помечаются строки 2 и 3. Метка второй строки:

Метка третьей строки:

Шаг 2. От второй строки можно пометить первый столбец меткой

Но поток на дуге равен 2, а ее пропускная способность равна 3, следовательно, найдена увеличивающая цепь (рис. 8.12), вдоль которой можно увеличить поток на 1. Определим вершины этой цепи. Сток метится от первого столбца. Первый столбец помечен от первой строки, вторая строка помечена от второго столбца, второй столбец помечен от первой строки, первая строка помечена от источника (см. табл. 8.2).

Отметим знаком «+» потоки на прямых дугах и знаком «-» потоки на обратных дугах найденной увеличивающей цепи. Прибавим к потокам, отмеченным знаком «+», и вычтем из потоков, отмеченных знаком «-», единицу (см. рис. 8.12). Величина потока в транспортной сети увеличится на 1.

Попытаемся Ьнова увеличить поток (табл. 8.3).

Шаг 1. Первая строка получает метку .

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

Дуги минимального разреза и вершины множества показаны на рис. 8.13 жирными линиями. Пропускная способность минимального разреза равна сумме

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

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

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

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

Венгерский алгоритм решения транспортной задачи

К оглавлению…

Напомним математическую модель задачи, двойственной транспортной.

Максимизировать целевую функцию

при условиях

Воспользуемся условиями дополняющей нежесткости. Допустимые решения

ТЗ и двойственной ей задачи оптимальны тогда и только тогда, когда справедливы равенства

Положим, что затраты занесены в матрицу затрат размерности .

Пусть найдено допустимое решение

задач (8.21) — (8.22). Выделим в матрицу затрат те клетки (), для которых

Будем считать эти клетки допустимыми, построим соответствующую транспортную сеть (рис. 8.14) и решим для этой сети задачу о максимальном потоке.

Правило построения сети: источник s соединен с каждой вершиной дугой с пропускной способностью, равной , . Каждая вершина соединена со стоком дугой

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

а) все дуги, выходящие из источника (соответственно все дуги, входящие в сток), насыщены. Это значит, что все запасы вывезены (все потребности удовлетворены). Тогда неизвестные перевозки просто равны потокам на соответствующих дугах двудольного графа. При этом получено оптимальное решение транспортной задачи, потому что для имеющихся допустимых решений пары двойственных задач выполнены условия дополняющей нежесткости;

б) не все запасы вывезены (соответственно не все потребности удовлетворены).

Тогда, как следует из (8.19),

Отсюда

В этом случае решение задачи (8.21) — (8.22) можно улучшить так же, как при решении ЗН.

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

Пересчитаем значения двойственных переменных по правилу:

Допустимость нового решения очевидна. Вычислим значение целевой функции на нем:

Итак, на новом решении

целевая функция двойственной задачи увеличилась.

Снова найдем в матрице стоимостей те клетки, для которых

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

Формальное описание алгоритма

Шаг 1. Найти исходное допустимое решение двойственной задачи, положив

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

Шаг 2. Положить

Шаг 3. Решить задачу о максимальном потоке, считая допустимыми клетки с нулями в матрице . Возможны два случая:

а) все потребности удовлетворены;

б) не все потребности удовлетворены.

В случае а) перейти к шагу 6, в случае б) — к шагу 4.

Шаг 4. Прочеркнуть в матрице стоимостей непомеченные строки и помеченные столбцы (покрывающее множество рядов) и найти минимальный элемент в оставшейся части матрицы ().

Шаг 5. Пересчитать двойственные переменные по правилу . Перейти к шагу 2.

Шаг 6. Положить , если дуги нет в транспортной сети или поток на ней равен 0. В противном случае положить . Оптимальные значения перевозок найдены. Конец.

Для удобства вычислений шаг 5 формулируется по-другому.

Шаг 5. Вычесть из всех непрочеркнутых элементов матрицы стоимостей и прибавить к дважды прочеркнутым. Перейти к шагу 3.

Решим ТЗ, заданную в табл. 8.4.

Шаг 1. Определяем допустимое решение двойственной задачи.

Исходное значение целевой функции двойственной задачи таково:

Шаг 2. Вычисляем

Результаты расчетов приведены в табл. 8.5.

Шаг 3. Решим задачу о максимальном потоке, считая допустимыми клетки с нулями. Ход решения отражен в табл. 8.6.

Для сокращения числа итераций начальный поток взят ненулевым. Не вывезены запасы 4-го и 5-го поставщиков. У первого поставщика осталось 40, у второго — 30 единиц продукта. Метим четвертую и пятую строки соответственно метками и . От четвертой строки по допустимым клеткам метятся 1, 4, 5-й столбцы меткой . От пятой строки метится по допустимой клетке 6-й столбец меткой .

От первого столбца по допустимой клетке с ненулевым потоком 40 метится первая строка меткой

От четвертого столбца по допустимой клетке с ненулевым потоком 30 метится третья строка меткой

От 5-го и 6-го столбцов нельзя пометить ни одной строки. От помеченной первой строки метятся 2-й и 3-й столбцы меткой (1+, 40). Но третий потребитель недополучил 70 единиц товара. Найдена увеличивающая цепь. Восстановим ее (рис. 8.15).

Третий столбец по прямой дуге помечен от первой строки; 1-я строка по обратной дуге помечена от 1-го столбца; 1-й столбец по прямой дуге помечен от 4-й строки; 4-я строка помечена от источника. Сток метится от 3-го столбца меткой (3\ min(40, 80 — 10))=(3+, 40). В табл. 8.6 прямые дуги цепи отмечены знаком «+», обратные — знаком «-».

Увеличиваем поток на прямых дугах на 40 единиц и уменьшаем поток на обратной дуге на 40 единиц (табл. 8.7).

Пытаемся снова увеличить поток. Пятая строка получает метку , от нее 6-й столбец получает метку . Больше ничего отметить нельзя. Для данной транспортной сети найден максимальный поток, но не все запасы 5-го поставщика вывезены (соответственно 3-й потребитель недополучил 30 единиц груза). Можно улучшить решение двойственной задачи.

Шаг 4. Перечеркиваем в матрице стоимостей (см. табл. 8.5) непомеченные 1-ю, 2-ю, 3-ю, 4-ю строки и помеченный 6-й столбец. Минимальный элемент в оставшейся части таблицы равен 1.

Прибавим единицу к дважды прочеркнутым элементам и вычтем единицу из непрочеркнутых элементов (табл. 8.8).

Вычислим изменение целевой функции двойственной задачи.

На новом допустимом решении двойственной задачи значение целевой функции равно 1140 + 30 = 1170.

В табл. 8.8 указаны также новые значения двойственных переменных, определенные в соответствии с (8.14).

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

Пятая строка получает метку . От нее меткой метятся 1,2,6-й столбцы. От 2-го столбца меткой метится первая строка. От 1-й строки можно пометить меткой 3-й столбец, от которого меткой метится сток. На самом деле меток можно поставить больше, все они указаны в табл. 8.9, но мы показали только, как метятся вершины увеличивающей цепи, по которой можно увеличить поток на 30 единиц. Прямые дуги этой цепи: (s, 5 стр.), (5 стр., 2 столб.), (1 стр., 3 столб.), (3 столб., t). Обратная дуга одна — (1 стр., 2 столб.). Увеличиваем поток на прямых дугах и уменьшаем поток на обратной дуге на 30 единиц (табл. 8.10).

Все запасы вывезены, все потребности удовлетворены. Оптимальные перевозки следующие:

Остальные перевозки равны нулю.

Оптимальное решение двойственной задачи:

Оптимальность найденных решений следует из условий дополняющей нежесткости.

Оптимальное значение целевой функции ТЗ равно

Для контроля вычислим значение целевой функции двойственной задачи по значениям двойственных переменных:

Разумеется, значения целевых функций совпали.

Возможно эти страницы вам будут полезны: