Сервис для решения задач по линейному программированию
и другие интересные типовые задачи
Пример №2. Решение задачи линейного программирования графическим методом.
Функция достигает наименьшего значения в точке
при следующих ограничениях:
 | x1 | + | 2 x2 | ≤ | 8 |
| x1 | — | x2 | ≤ | 2 | |
| x1 | + | 2 x2 | ≥ | 4 | |
| x1 | ≥ | 1 |
x1 ≥ 0 x2 ≥ 0
Точки, координаты которых удовлетворяют одновременно всем неравенствам системы ограничений, называются областью допустимых решений.
Очевидно, для нахождения области допустимых решений данной задачи, необходимо последовательно рассмотреть каждое неравенство. (см. шаг 1 — шаг 4)
Последние два шага служат непосредственно для получения ответа. (см. шаг 5 — шаг 6)
Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче.
По условию задачи: x1 ≥ 0 x2 ≥ 0.
Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке (вся первая четверть).
Рассмотрим неравенство 1 системы ограничений.
Построим прямую: x1 + 2 x2 = 8
Найдены коородинаты двух точек (0, 4) и (8 ,0). Соединяем их и получаем необходимую прямую (1).
Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.
Преобразуем неравенство, оставив в левой части только x2
Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (1).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 2 системы ограничений.
Найдены коородинаты двух точек (0, -2) и (2 ,0). Соединяем их и получаем необходимую прямую (2).
Нас интересуют точки расположенные выше или ниже построенной прямой (2) ?
Вернемся к исходному неравенству.
Преобразуем неравенство, оставив в левой части только x2
Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (2).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 3 системы ограничений.
Построим прямую: x1 + 2 x2 = 4
Найдены коородинаты двух точек (0, 2) и (4 ,0). Соединяем их и получаем необходимую прямую (3).
Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.
Преобразуем неравенство, оставив в левой части только x2
Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 4 системы ограничений.
Построим прямую: x1 = 1
Данная прямая параллельна оси OX2 и проходит через точку (1,0) (4)
Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные правее построенной прямой (4).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Строим вектор C = (2, 2), координатами которого являются коэффициенты функции F.
Будем перемещать «красную» прямую, перпендикулярно вектору C , от левого нижнего угла к правому верхнему.
В точке, в которой «красная» прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения.
В точке, в которой «красная» прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения.
Функция F достигает наименьшего значения в точке A. (см. рисунок)
Найдем координаты точки A.
Точка A одновременно принадлежит прямым (3) и (4).
| x1 | + | 2 x2 | = | 4 | => | x1 = 1 |
| x1 | = | 1 | x2 = 3/2 |
Вычислим значение функции F в точке A (1,3/2).
F (A) = 2 * 1 + 2 * 3/2 = 5
x1 = 1
x2 = 3/2
F min = 5
Замечание: если возникли сомнения, что функция F достигает своего минимума в точке А, необходимо найти значение функции в интересующей точке и сравнить с F(A).
Источник
Графический (геометрический) метод решения задач ЛП
Пример 6.1. Решить следующую задачу ли-нейного программирования геометрическим методом:
.
Решение:
Задача линейного программирования задана в стандартной форме и имеет два проектных параметра, следовательно
, воз-можно ее решение геометрическим методом.
1 этап: построение прямых, ограничивающих область допустимых решений ( ОДР).
Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):
Рассмотрим первое ограничение, заменим знак неравенства знаком равенства и выразим переменную х2 через х1:
.
Для построения прямой по данному уравнению зададим две произвольные точки, к примеру:
Аналогично определяем точки для остальных ограничений системы и строим по ним прямые, соответствующие каждому неравенству (рис. 1). Прямые пронумеруем согласно принятой ранее схеме.
2 этап: определение решения каждого из нера-венств системы ограничений.
Определим полуплоскости – решения каждого из неравенств.
Рассмотрим первое неравенство системы ограничений задачи. Возьмем какую-либо точку (контрольную точку), не принадлежащую соответствующей данному неравенству прямой, например, точку (0; 0). Подставим ее в рассматриваемое неравенство:
.
При подстановке координат контрольной точки неравенство остается справедливым. Следовательно, множество точек, принадлежащих данной прямой (т.к. неравенство не строгое), а также расположенных ниже ее, будут являться решениями рассматриваемого неравенства (пометим на графике (рис. 1) найденную полуплоскость двумя стрелками направленными вниз рядом с прямой I) .
Аналогично определяем решения других неравенств и соответственно помечаем их графике. В результате график примет следующий вид:
3 этап: определение ОДР задачи линейного про- граммирования.
Найденные полуплоскости (решения каждого из неравенств системы ограничений) при пересечении образуют многоугольник ABCDEO, который и является ОДР рассматриваемой задачи.
Рис. 1. Область допустимых решений задачи
4 этап: построение вектора-градиента.
Вектор-градиент показывает направление максимизации целевой функции . Определим его координаты: координаты начальной его точки (точки приложения) – (0; 0), координаты второй точки:
Построим данный вектор на графике (рис. 2).
5 этап: построение прямой целевой функ-ции.
Рассмотрим целевую функцию данной задачи:
.
Зададим ей какое-либо значение, к примеру, 
. Выразим переменную х2 через х1:
.
Для построения прямой по данному уравнению зададим две произвольные точки, к примеру:
Построим прямую соответствующую целевой функции (рис. 2).
Рис. 2. Построение целевой функции F(X) и вектора-градиента С
6 этап: определение максимума целевой функ-ции.
Перемещая прямую F(X) параллельно са-мой себе по направлению вектора-градиента, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 3), такой точкой является точка С – точка пересечения прямых I и II.
Рис. 3. Определение точки максимума целевой функции F(X)
Определим координаты точки С, с этой целью, решим сле-дующую систему линейных уравнений:
Подставим найденные координаты в целевую функцию и найдем ее оптимальное (максимальное) значение:
Ответ: при заданных ограничениях макси-мальное значение целевой функции F(Х)=24, которое достигается в точке С, координаты которой х1=6, х2=4.
Пример 6.2. Решить задачу линейного про- граммирования геометрическим методом:
Решение:
Этапы 1-3 аналогичны соответствующим этапам предыдущей задачи.
4 этап: построение вектора-градиента.
Построение вектора-градиента осуществляется аналогично, как и в предыдущей задаче. Построим данный вектор на графике (рис. 4). Отметим также на данном графике стрелкой направление, обратное вектору-градиенту, – направление минимизации целевой функцииF (X).
5 этап: построение прямой целевой функ-ции.
Построение прямой целевой функции F(X) осуществляется аналогично, как и в предыдущей задаче (результат построения приведен на рис. 4).
Рис. 4. Построение целевой функции F(x) и вектора-градиента С
6 этап: определение оптимума целевой функ-ции.
Перемещая прямую F(x) параллельно са-мой себе в направлении, обратном вектору-градиенту, опреде-ляем крайнюю точку (точки) ОДР. Согласно графику (рис. 5), та- кой точкой является точка О с координатами (0; 0).
Рис. 5. Определение точки минимума целевой функции
Подставляя координаты точки минимума в целевую функ-цию, определяем ее оптимальное (минимальное) значение, которое равно 0.
Ответ: при заданных ограничениях минимальное значение целевой функции F(Х)=0, которое достигается в точке О (0; 0).
Пример 6.3. Решить следующую задачу ли-нейного программирования геометрическим методом:
Решение:
Рассматриваемая задача линейного программирования задана в канонической форме, выделим в качестве базисных переменные x 1 и x2.
Составим расширенную матрицу и выделим с помощью метода Жордана- Гаусса базисные переменныеx1 и x 2.
Умножим (поэлементно) первую строку на –3 и сложим со вто-рой: 
.
Умножим вторую строку на 
:
.
Сложим вторую с первой строкой:
.
В результате система ограничений примет следующий вид:
Выразим базисные переменные через свободные:
Выразим целевую функцию также через свободные перемен-ные, для этого подставим полученные значения базисных переменных в целевую функцию:
.
Запишем полученную задачу линейного программирования:
Так как переменные x1 и x2 неотрицательные, то полученную систему ограничений можно записать в следующем виде:
Тогда исходную задачу можно записать в виде следующей эк- вивалентной ей стандартной задаче линейного программирования:
Данная задача имеет два проектных параметра, следовательно, возможно ее решение геометрическим мето-дом.
1 этап: построение прямых, ограничивающих область допустимых решений ( ОДР).
Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):
Построим прямые, соответствующие каждому неравенству (рис. 6). Прямые пронумеруем согласно принятой ранее схе-ме.
2 этап: определение решения каждого из нера-венств системы ограничений.
С помощью контрольных точек определим полуплоскости – решения каждого из неравенств, и пометим их на графике (рис. 6) с помощью стрелок.
3 этап: определение ОДР задачи линейного про- граммирования.
Найденные полуплоскости (т.е. решения каждого из неравенств системы ограничений) не имеют общего пересечения (так решения неравенства I противоречат в целом остальным неравенствам системы ограничений), следовательно, система ограничений не совместна и задача линейного программирования в силу этого не имеет решения.
Рис. 6. Фрагмент MathCAD-документа:
построение области допустимых решений задачи
Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности системы ограничений.
Если после подстановки координат контрольной точки в неравенство его смысл нарушается, то решением данного неравенства является полуплоскость не содержащая данную точку (т.е. расположенная по другую сторону прямой).
Направление, обратное вектору-градиенту, соответствует направлению минимизации целевой функции.
Источник
