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

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

Набор чисел называется допустимым решением (планом) , если он удовлетворяет системе ограничений ЗЛП.

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

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

Термины «план» и «оптимальный план» возникли из экономических приложений.

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

Рассмотрим алгоритмы перехода от одной формы к другой.

• 
  Симметричная  каноническая. Переход осуществляется путем добавления в левую часть каждого неравенства дополнительной неотрицательной переменной. Если неравенство было «≤», то балансовая переменная добавляется в левую часть неравенства со знаком «+». Если неравенство было «», то балансовая переменная добавляется в левую часть неравенства со знаком «–». Вводимые новые переменные называются балансовыми . Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) и используют, что min Z = –max (–Z).
• 
  Каноническая  симметричная. Для осуществления такого перехода находится общее решение системы уравнений – ограничений, целевая функция выражается через свободные переменные. Далее, воспользовавшись неотрицательностью базисных переменных, можно исключить их из задачи. Симметричная форма задачи будет содержать неравенства, связывающие только свободные переменные, и целевую функцию, зависящую только от свободных переменных. Значения базисных переменных находятся из общего решения исходной системы уравнений.
• 
  Общая  каноническая. Каждая переменная, на которую не было наложено условие неотрицательности, представляется в виде разности двух новых неотрицательных переменных. Неравенства преобразуются в уравнения путем введения в левую часть каждого неравенства балансовой переменной таким же образом, как это было описано при переходе от симметричной к канонической форме. Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) таким же образом, как это было описано при переходе от симметричной к канонической форме..

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

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

Пример 1

Следующие множества точек на плоскости являются выпуклыми:

Следующие множества точек на плоскости не являются выпуклыми:

Теорема 1 Пересечение любого количества выпуклых множеств является выпуклым множеством.

Теорема 2 Пусть имеются две произвольные точки и в пространстве R n . Тогда для любой точки отрезка [PQ ] должно выполняться: .где .

Гиперплоскостью в пространстве R n называется множество точек, удовлетворяющее уравнению . Заметим, что в двумерном случае гиперплоскостью является прямая.

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

Теорема 3 Полупространство является выпуклым множеством.

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

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

Пример 2

Следующие множества являются многоугольниками.

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

Неограниченное множество

Единственная точка

Пустое множество

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

Пример 3

Угловыми точками треугольника являются его вершины (их три). Угловыми точками круга являются точки окружности, которая его ограничивает (их бесконечное число).

Угловая точка многогранника называется его вершиной .

Рассмотрим ЗЛП, заданную в симметричной форме.

Теорема 4 Оптимальный план ЗЛП соответствует вершине многогранника решений, определяемого ее системой ограничений.

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

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

• если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
• если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
• если некоторая переменная x j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
  x 3 = x 3 + - x 3 - , где x 3 + , x 3 - ≥ 0 .

Пример 1 . Приведение к канонической форме задачи линейного программирования:

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x 1 = x 1 " - x 7 , где x 1 " ≥ 0, x 7 ≥ 0 .

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

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 " ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Условие оптимальности базисного плана канонической задачи ЛП. Симплекс-метод и его сходимость.

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

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

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

Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.

Опорным решением называется базисное неотрицательное решение.

Алгоритм симплексного метода

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

2. Находим исходное опорное решение и проверяем его на оптимальность.
Для этого заполняем симплексную таблицу 1.
Все строки таблицы 1-го шагазаполняем по данным системы ограничений и целевой функции.

Возможны следующие случаи при решении задач на максимум:

1. Если все коэффициенты последней строки симплекс-таблицы Dj ³ 0, то найденное

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

2 Если хотя бы один коэффициент Dj £ 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем , так как F(X) ® ¥ , т.е.целевая функция не ограничена в области допустимых решений.

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

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

5. Если хотя бы один коэффициент Dk < 0 ,то k - тый столбец принимаем за ведущий.

6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.

7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.

Заполняем симплексную таблицу 2:

· заполняем базисный столбец нулями и единицей

· переписываем ведущую строку, разделив ее на ведущий элемент

· если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы

· остальные коэффициенты находим по правилу “прямоугольника”

Получаем новое опорное решение, которое проверяем на оптимальность:

Если все коэффициенты последней строки Dj ³ 0, то найденное решение максимальное.

Если нет, то заполняем симплексную таблицу 8-го шага и так далее.

Если целевая функция F(X) требует нахождения минимального значения , то критерием оптимальности задачи является неположительность коэффициентов Dj при всех j = 1,2,...n.

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

Легко заметить, что проблемы со сходимостью симплекс-ме­тода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения от­ношения

будут достигнуты для нескольких строк таблицы Т (q) одновре­менно. Тогда на следующей итерации столбец b(β(q+1)) будет со­держать нулевые элементы.

задачи линейного программирования

2.1. Определение и формы записи

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

а) каноническая задача ЛП в координатной форме имеет вид:

,
.

Данную задачу можно записать, используя знак суммирования:

,

,

,
,
.

б) каноническая задача ЛП в векторной форме имеет вид: ,

,

где
;
;

,
;;
.

в) каноническая задача ЛП в матричной форме имеет вид:

,
,

где
,,.

2.2. Приведение общей задачи линейного

программирования к канонической форме

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

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

Неотрицательная переменная
называется дополнительной переменной. Следующая теорема даёт основание для возможности такого преобразования.

Теорема 2.2.1. Каждому решению
неравенства (2.2.1) соответствует единственное решениеуравнения (2.2.2) и неравенства
, и, наоборот, каждому решению уравнения (2.2.2)с
соответствует решение
неравенства (2.2.1).

Доказательство. Пусть
решение неравенства (2.2.1). Тогда. Возьмём число
. Ясно, что
. Подставив в уравнение (2.2.2), получим

Первая часть теоремы доказана.

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

Таким образом, доказанная теорема фактически устанавливает возможность приведения всякой задачи ЛП к каноническому виду. Для этого достаточно в каждое ограничение, имеющее вид неравенства, ввести свою дополнительную неотрицательную переменную. Причём, в неравенства вида (1.2.1) эти переменные войдут со знаком « + », а в неравенствах вида (1.2.2) – со знаком « – ». Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому на её значение не влияют.

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

3. Графический метод решения задач

линейного программирования

3.1. Общие понятия, примеры

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

(3.1.1)

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

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

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

, где
. Все линии уровня параллельны между собой. Их нормаль
.

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

Значения
возрастают в направлении вектора
. Поэтому необходимо передвигать линию уровня
в направлении этого вектора параллельно самой себе до опорной прямойL 1 в задаче на максимум и в противоположном направлении – в задаче на минимум (до опорной прямойL 2).

Приведём решение примера 1.1. Напомним, что нужно найти максимум функции
при ограничениях

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

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

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

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

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

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

Пример 3.1. Найти минимум функции
при системе ограничений

Решение. Строим область допустимых решений (см. рис.3), вектор
и одну из линий уровня
. Перемещаем линию уровня в направлении, противоположном
, так как решается задача на отыскание минимума функции. Опорная прямая проходит в этом случае через точку А (рис.3), координаты которой найдём из решения системы

Итак,
. Вычисляем.

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

Пример 3.2. Найти минимум функции
при ограничениях

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

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

;
;

,
;
,
;

;
.

Вычисляем .

Ответ:
при
,
.

Пример 3.3. Решить задачу линейного программирования

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

Задача не имеет решения вследствие неограниченности целевой функции.

Ответ:
.

Назначение сервиса . Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную x j не наложено ограничение, то она заменяется на разность дополнительных переменных, x j = x j1 - x j2 , x j1 ≥ 0, x j2 ≥ 0.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

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

Математическая модель называется канонической , если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис , определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b i ≥ 0).

Переменные, входящие в одно из уравнений системы с коэффициентом один и отсутствующие в других уравнениях называются базисными неизвестными , а все другие - свободными .

Решение системы называется базисным , если в нем свободные переменные равны 0, и оно имеет вид:
X баз = (0, 0; b 1 , …, b m), f(X баз) = c 0

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

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

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

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x 1 + 3x 2 → max при ограничениях:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x 3 , x 4 , x 5 , x 6 , которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x 3 . Во 2-ом неравенстве смысла (≤) вводим базисную переменную x 4 . В третьем неравенстве вводим базисную переменную x 5 . В 4-м неравенстве - базисную переменную x 6 . Получим каноническую форму модели:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Пример №2 . Найти два опорных решения системы
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

найти максимум функции

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