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

Оглавление:

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

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

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

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

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

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

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

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

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

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

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

Совокупность целевой функции (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).

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

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