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

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

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

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

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

Графический метод решения ЗЛП: примеры онлайн

Задача 1. Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика — 4000 руб., пятитонного — 5000 руб. Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Задачу решить графическими и аналитическими методами.

Задача 2. Решить задачу графическим методом на минимум и на максимум

Задача 3. Решить задачу графическим методом на минимум и на максимум

Задача 4. Среди чисел x и y, удовлетворяющих условиям

найти такие, при которых разность этих чисел y-x принимает наибольшее значение.

Задача 5. Решить графическим методом ЗЛП, заданную указанной математической моделью.

Задача 6. Решите графически следующие задачи линейного программирования

Задача 7. Решить графическим методом

Источник

Графический метод решения ЗЛП

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

Инструкция . Выберите количество строк (количество ограничений). Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x₁ ≤ 4 , то оно разбивается на два: x₁ ≥ 1 , x₁ ≤ 4 (т.е. количество строк увеличивается на 1).
Построить область допустимого решения (ОДР) можно также с помощью этого сервиса.

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

1. На плоскости X₁0X₂ строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂ + c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.

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

Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП.
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

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

Переменную x₂ принимаем в качестве дополнительной переменной и делаем замену на знак «≥»:
f=x₁ + 6x₃+ 27
x₁ + 3x₃≥6

Далее задача решается графическом способом.

Пример №2
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

• Составить систему математических зависимостей (неравенств) и целевую функцию.
• Изобразить геометрическую интерпретацию задачи.
• Найти оптимальное решение.
• Провести аналитическую проверку.
• Определить существенные и несущественные ресурсы и их избытки.
• Определить значение целевой функции.
• Вычислить объективно обусловленные оценки.
• Составить соотношение устойчивости.

Источник

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

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

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

Рис. 4.1. Геометрическая интерпретация решения задачи

Геометрическую интерпретацию имеют ЗЛП с двумя переменными.

Исследуем целевую функцию 30х₁ + 40х₂. Данной целевой функции соответствует семейство прямых 30х₁ + 40х₂ = L, представляющих собой множество параллельных прямых, каждая из которых соответствует определенному значению параметра L. Тогда задачу линейного программирования можно сформулировать следующим образом. Найти такое максимальное значение L, при котором прямая 30х₁ + 40х₂ = L пересекает допустимое множество.

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

Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент целевой функции Ñf(`X) на плоскости Х₁ОХ₂. Этот вектор показывает направление наискорейшего изменения целевой функции, он равен

,

где и— единичные векторы по осям ОХ₁ и ОХ₂ соответственно. Таким образом, Ñf(`X) = (¶f/¶x<sub>1</sub>, (¶f/¶x<sub>2</sub>). Координатами вектора-градиента целевой функции Ñf(`X) являются коэффициенты целевой функции f(`X).

В рассматриваемом примере, если двигать прямую 30х₁ + 40х₂ = L из начала координат по направлению вектора-градиента целевой функции, то точкой, в которой достигается самая верхняя линия уровня является точка М пересечения прямых 5x₁ + 2x₂ = 1000 и x₁ + 2x₂ = 4000 с координатами x₁ = 1500 и x₂ = 1250. Таким образом, оптимальное решение достигается в точке М (1500; 1250). При этом значение целевой функции составит f(`X * ) =30 * 1500 + 40 * 1250 = 95000.

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

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

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

Лекция 5. Симплексный метод решения задачи линейного программирования

5.2.Симплексные таблицы и алгоритм решения задач.

5.3. Применение симплексного метода в экономических задачах.

5.1. Симплекс-метод

Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, заданную в каноническом виде. Идея симплекс метода была разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данцинг в 1949 г. разработал симплекс-метод, позволяющий решать любую задачу линейного программирования.

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

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

Симплексный метод состоит из трех основных элементов:

1) определения какого-либо первоначального допустимого базисного решения задачи;

2) правила перехода к лучшему решению;

3) проверки оптимальности допустимого решения.

Симплекс-метод состоит из двух вычислительных процедур:

— симплекс-метод с естественным базисом;

— симплекс-метод с искусственным базисом.

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

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

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

Источник