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

Когда нужен графический метод?

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

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

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

Однако для выработки наглядных представлений о решениях задач
линейного программирования графический метод представляет определённый интерес. Кроме того,
он позволяет геометрически подтвердить справедливость
теорем линейного
программирования.

Теоретические основы графического метода

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

при которых линейная форма

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

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

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

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

Среди прямых упомянутого семейства параллельных прямых прямые mn
(зелёного цвета) и MN (красного цвета), которые назовём опорными. Опорными обычно
называют такие прямые, которые имеют с многоугольником ABCDE хотя бы одну общую точку,
и многоугольник ABCDE целиком лежит по одну сторону от этой прямой. Как видно из
чертежа, прямая mn является опорной, так как она касается многоугольника в точке
A и многоугольник целиком лежит правее (или выше) этой прямой. Прямая MN
также является опорной, так как имеет с многоугольником общую точку С и
многоугольник целиком лежит левее этой прямой.

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

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

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

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

Затем, откладывая на оси

, а на оси

3. Двигать прямую (или линейку) вдоль градиента — вектора

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

4. Двигаясь дальше, придём к некоторому опорному положению, когда прямая
будет иметь одну общую точку

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

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

Примеры решения задач графическим методом

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

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

.
Это уравнение первой граничной прямой. Найдём точки пересечения этой прямой с осями
координат. При

из уравнения получим

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

Аналогично строим остальные граничные прямые. Вторая прямая от осей
координат отсекает отрезки, равные 6. Третья прямая проходит параллельно оси

,
отсекая на оси

отрезок, равный 2. Четвёртая прямая имеет уравнение

.
Она совпадает с осью

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

Следовательно, четырёхугольник ABDE является многоугольником
решений системы (заштрихован вовнутрь).

Начертим линию равных значений функции цели. Приняв в равенстве F =1,
получим, что эта линия отсекает отрезки 1 и 1/3 соответственно на оси

и
на оси

Двигая эту прямую параллельно самой себе в направлении градиента — вектора

(бордового цвета),
получим опорные прямые. Первая прямая (зелёного цвета) имеет с многоугольником общую точку
A. Здесь функция цели достигает минимума. Двигаясь дальше, придём к точке В.
Здесь максимум. Координаты точки В: (2, 4). Подставляя в функцию цели координаты
точки В, т. е.

,
получим максимальное значение функции цели:

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

Решение. Многогранником решений является открытая область

Проведём линию равных значений функции цели при F =1, как в
предыдущем примере (она опять чёрного цвета).

Из рисунка видно, что прямая ближайшнее от начала координат опорное
положение займёт в точке В. Следовательно, в этой точке функция цели имеет минимум.
Координаты точки В: (2, 2). Подставляя в функцию цели

, получим
минимальное значение функции:

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

Решить задачи графическим методом самостоятельно, а затем посмотреть решения

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

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

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

Продолжаем решать задачи графическим методом вместе

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

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

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

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

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

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

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

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

(на рисунке ниже — чёрного
цвета), с тем чтобы она пересекала область решений. Как видно из рисунка, максимальное значение
достигается в точке .
При построении треугольника ABC не была использована прямая

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

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

Все точки отрезка CD дают одно
и то же значение функции цели, которое и служит её оптимальным значением:

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

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

Начало темы «Линейное программирование»

Поделиться с друзьями

Симплекс метод онлайн

Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.

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

Примеры решения ЗЛП симплекс методом

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

Р е ш е н и е. Матрица коэффициентов

системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

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

, а свободные переменные

Запишем текущий опорный план:

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

. min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x3. Сделаем исключение Гаусса для столбца x2, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x1. Определяем, какой вектор выходит из базиса. Для этого вычисляем

. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x4. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

Решение можно записать так:

Значение целевой функции в данной точке: F(X)=

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

Базисные векторы x4, x3, следовательно, все элементы в столбцах x4, x3, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x4, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x3, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x2. Определяем, какой вектор выходит из базиса. Для этого вычисляем

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

Примеры решения ЗЛП методом искусственного базиса

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

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

кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

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

соответствует строке 3. Из базиса выходит вектор

учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

соответствует строке 1. Из базиса выходит вектор x2. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x3. Определяем, какой вектор выходит из базиса. Для этого вычисляем

соответствует строке 3. Из базиса выходит вектор x5. Сделаем исключение Гаусса для столбца x3, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными

нет отрицательных элементов.

Решение исходной задачи можно записать так:

Найти оптимальный план задачи линейного программирования:

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:

Базисные векторы x4, x5, x6, следовательно, все элементы в столбцах x4, x5, x6, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x4, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x5, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x6, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

В строке 5 элементы, соответствующие переменным x1, x2, x3, x4, x5, x6 неотрицательны, а число находящийся в пересечении данной строки и столбца x0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

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

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

Симплекс метод для задачи ЛП в основной форме − теория и алгоритм

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

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

Запишем данную задачу ЛП в матричном виде:

где ( small C-1×n- ) вектор-строка, ( small X-n×1- ) вектор-столбец, ( small A-m×n- ) матрица ранга n, ( small B-m×1- ) вектор столбец.

Пусть ( small X_0- ) допустимый план задачи ЛП (1a)-(1b) и пусть первые n неравенства в (1b) удовлетворяются как равенства и соответствующим этим неравенствам векторы строки матрицы ( small A) линейно независимы. Это означает, что ( small X_0 ) является вершиной выпуклого многогранного множества (1b). Тогда

, ( small A_Б-n×n- ) матрица ранга n, составленная из базисных векторов-строк матрицы A, ( small A_Н-m-n×n- ) матрица, составленная из небазисных векторов-строк матрицы A,

, ( small B_Б-n×1- ) вектор-столбец, соответствующий базисным векторам матрицы A, ( small B_Н-m-n×1- ) вектор-столбец, соответствующий небазисным векторам матрицы A.

Наша цель переместиться из вершины ( small X_0 ) до другой вершины выпуклого многогранного множества (1b) так, чтобы значение целевой функции в новой точке был не меньше, чем в вершине ( small X_0 ).

Из (4) следует

Запишем уравнение прямой, по которому нужно двигаться от точки ( small X_0 ) по одному из ребер выпуклого многогранного множества (1b):

При движении от точки ( small X_0 ) по ребру выпуклого многогранного множества, новая точка (вершина) должна удовлетворять системе линейных неравенств (1b). Тогда, подставляя (6 ) в (1b), получим:

Далее, учитывая, что

А исходя из (2) и (5) неравенство (7) можно записать так:

Запишем систему линейных неравенств (ЛН)(8) в развернутом виде:

Далее, возвращаяясь к выражению (12), находим t и подставляя в (6) находим новый план задачи (1a)-(1b). Отмечаем буквой q строку A, при которой t принял максимальное значение. Таким образом, в базис входит вектор-строка q, а из базиса выходит вектор-строка p матрицы A. Далее, взьяв в качестве исходного новый план, продолжаем процедуру.

Можно с легкостью найти также оптимальный план двойственной задачи. Из условия дополняющей нежесткости для задачи ЛП (1a)-(1b) имеем:

где (small Y^*-1×m — ) вектор-строка − оптимальный план задачи ЛП двойственной к (1a)-(1b), (small X^*-n×1 — ) вектор-столбец − оптимальный план задачи ЛП (1a)-(1b).

Запишем (14) так:

Из (2) и (3) следует, что для того, чтобы левая часть выражения (15) была равна нулю достаточно, чтобы ( small Y_Н^*=0. )

Чтобы ( small Y^* ) была допустимой точкой задачи ЛП двойственной к (1a)-(1b), ( small Y^* ) должна удовлетворять условиям

Учитывая, что (small Y_Н^*=0, ) получим:

Следовательно, оптимальный план двойственной к задаче ЛП(1a)-(1b) будет вектор:

0 − вектор-строка порядка ( small 1×m-n ).

В заключении отметим, что на каждом шаге решения задачи можно найти псевдоплан (small Y_0 ) :

Заметим, что хотя и псевдоплан удовлетворяет условию дополняющей нежесткости (14), но в его компонентах есть отрицательные элементы. А когда все элементы псевдоплана оказываются неотрицательными, то псевдоплан становится планом и одновременно оптимальным планом задачи двойственной к (1a)-(1b).

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

Таким образом алгоритм решения задачи ЛП в основной форме содержит следующие шаги:

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

7. Находим t из

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

7. Находим новый опорный план из равенства:

8. Строим новый базис ( small A_Б ). Для этого из базиса выводим строку p и вводим в базис строку q.

9. Переходим к пункту 2.

10. Текущий план ( small X^*=X_0 ) является оптимальным. Вычисляем значение целевой функции в оптимальной точке: ( small F=CX^*. )

Для просмотра примеров решения, введите данные на онлайн калькулятор выше, задайте начальный базис в виде номеров строк матрицы A через запятую и нажмите на кнопку «Вычислить». Калькулятор представит решение задачи ЛП подробно, по шагам. Для решения задачи линейного программирования обычным симплекс методом используйте калькулятор Симплекс метод онлайн.

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