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

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

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

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

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

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

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

Транспортная проблема: В этих задачах мы должны найти самый дешевый способ транспортировки. Выбрав самый короткий маршрут/оптимизированный путь.

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

Целевая функция: Прямая функция вида Z = ax + by, где a и b постоянны, которая уменьшается или увеличивается. Называется целевой функцией. Например, если Z = 10x + 7y. Переменные x и y называются переменными решения.

Ограничения: Ограничения, которые применяются к линейному неравенству, называются ограничениями.

Задача оптимизации: Задача, которая стремится к максимизации или минимизации переменных задачи линейного неравенства. Называется задачей оптимизации.

Допустимая область: Общая область, определяемая всеми заданными вопросами, включая неотрицательное ограничение (x ≥ 0, y ≥ 0). Называется допустимой областью (или областью решения) задачи. Область, отличная от допустимой области, называется неосуществимой областью.

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

Оптимальное(наиболее осуществимое) решение: Любая точка в формирующейся области. Обеспечивающая правильное количество (максимум или минимум) целевой функции. Называется оптимальным решением.

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

Теорема 1: Будем считать Y допустимой областью (выпуклым многоугольником) для задачи линейного программирования,то есть Y = ax + by (целевая функция). Итак, когда Y имеет оптимальное значение (максимум или минимум), где x и y подчиняются ограничениям. Описываемым линейными неравенствами,то это оптимальное значение возникает в угловых точках допустимой области, т. е.

Теорема 2: Пусть Y-допустимая область для задачи линейного программирования, т. Е. E., Y = ax + by (целевая функция). Если X ограничено, то целевая функция Y имеет как максимальное, так и минимальное значение на X. И каждое из них происходит в угловой точке X.

ЗАПИСКА:

  1. Если нам нужно найти максимальный выход. Мы должны рассмотреть самые внутренние точки пересечения всех уравнений.
  2. Если нам нужно найти минимальный выход, мы рассматриваем самые внешние точки пересечения всех уравнений.
  3. Если нет общей точки в линейном неравенстве, то нет и осуществимого решения.

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

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

  1. Угловая точка
  2. Метод Исо-затрат

Угловая точка

Чтобы решить проблему с помощью метода угловой точки необходимо выполнить следующие действия:

Шаг 1: Создайте математическую формулировку из заданной задачи. Если не дано.

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

Шаг 3: Найдите координаты допустимой области(вершин), которые мы получаем из шага 2.

Шаг 4: Теперь оцените целевую функцию в каждой угловой точке допустимой области. Предположим, что N и n обозначает наибольшее и наименьшее значения этих точек.

Шаг 5: Если допустимая область ограничена, то N и n-максимальное и минимальное значение целевой функции. Или если допустимая область неограниченна то:

  • В противном случае целевая функция не имеет решения.
  • n-минимальное значение целевой функции. Если открытый полуплан получен ax + by В противном случае целевая функция не имеет решения.

Примеры:

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

Максимизация: Z = 8x + y

и ограничения :

x + y ≤ 40,

2x + y ≤ 60,

x ≥ 0, y ≥ 0

Решение:

Шаг 1: Ограничения :

x + y ≤ 40,

2x + y ≤ 60,

x ≥ 0, y ≥ 0

Шаг 2: Нарисуйте график, используя эти ограничения.

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

Вершину допустимой области можно найти по графу или вычислить с помощью заданных ограничений:

x + y = 40 …(i)

2x + y = 60 …(ii)

Теперь умножим eq(i) на 2, а затем вычитаем оба eq(i) и (ii), мы получим

y = 20

Теперь поставим значение y в любое из уравнений, получим

x = 20

Таким образом, третья точка допустимой области-это (20, 20)

Шаг 3: Найти максимальное значение Z = 8x + y. Сравните каждую точку пересечения графика, чтобы найти максимальное значение

ОчкиZ = 8x + y
(0, 0)0
(0, 40)40
(20, 20)180
(30, 0)240

Таким образом, максимальное значение Z = 240 в точке x = 30, y = 0.

Вопрос 2. Один вид торта требует 200 г муки и 25 г жира. А другой вид торта требует 100 г муки и 50 г жира Найдите максимальное количество тортов. Которое можно приготовить из 5 кг муки и 1 кг жира при условии. Что нет недостатка в других ингредиентах. Используемых при изготовлении тортов.

Решение:

Шаг 1: Создайте такую таблицу для удобства понимания (в этом нет необходимости).

 Пол(g)Жир(г)
Торт первого сорта (x)20025
Торт второго сорта (y)10050
Доступность50001000

Шаг 2: Создайте линейное уравнение с помощью неравенства

  • 200x + 100y ≤ 5000 или 2x + y ≤ 50
  • 25x + 50y ≤ 1000 или x + 2y ≤ 40

Шаг 3: Создайте график, используя неравенство (помните только, чтобы взять положительные оси x и y)

Шаг 4: Найти максимальное количество тортов (Z) = x + y. Сравните каждую точку пересечения графика, чтобы найти максимальное количество пирожных, которые можно испечь.

иксyZ(x+y)
02020
201030
25025

Ясно, что Z максимален в координате (20, 10). Таким образом, максимальное количество тортов. Которые можно испечь, равно Z = 20 + 10 = 30.

Метод Iso-cost

Термин метод iso-cost или iso-profit представляет собой комбинацию точек. Которая производит те же затраты/прибыль. Что и любая другая комбинация на той же линии. Это делается путем построения линий, параллельных наклону уравнения.

Чтобы решить проблему с помощью метода Iso-cost, вам необходимо выполнить следующие действия:

Шаг 1: Создайте математическую формулировку из данной задачи. Если не дано.

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

Шаг 3: Теперь найдите координаты допустимой области, которые мы получаем из шага 2.

Шаг 4: Найдите удобное значение Z(целевая функция) и нарисуйте линию этой целевой функции.

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

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

Примеры:

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

Максимизация: Z = 50x + 15y

и ограничения :

5x + y ≤ 100,

x + y ≤ 50,

x ≥ 0, y ≥ 0

Решение:

Дано:

5x + y ≤ 100,

x + y ≤ 50,

x ≥ 0, y ≥ 0

Шаг 1: Поиск точек

Мы также можем написать так

5x + y = 100 …. (i)

x + y = 50 …. (ii)

Теперь мы находим точки

итак, мы берем eq(i), теперь в этом уравнении

Когда x = 0, y = 100

а когда y = 0, x = 20

Итак, точки равны (0, 100) и (20, 0)

Аналогично, в уравнении(ii)

Когда x = 0, y = 50

Когда y = 0, x = 50

Итак, точки равны (0, 50) и (50, 0)

Шаг 2: Теперь нанесите эти точки на график и найдите допустимую область.

Шаг 3: Теперь мы находим удобное значение Z(целевая функция)

Итак, чтобы найти удобное значение Z, мы должны взять lcm коэффициента 50x + 15y, то есть 150. Таким образом, значение Z кратно 150, то есть 300. Следовательно,

50x + 15y = 300

Теперь мы находим точки

Положим x = 0, y = 20

Положим y = 0, x = 6

нарисуйте линию этой целевой функции на графике:

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

Шаг 5: У нас есть общая точка (12.5, 37.5) с допустимой областью. Итак, теперь мы находим оптимальное решение целевой функции:

Z = 50x + 15y

Z = 50(12,5) + 15(37,5)

Z = 625 + 562,5

Z = 1187

Вопрос 2. Графически решить поставленные задачи линейного программирования:

Минимизировать: Z = 20x + 10y

и ограничения :

x + 2y ≤ 40,

3x + y ≥ 30,

4x + 3y ≥ 60,

x ≥ 0, y ≥ 0

Решение:

Дано:

x + 2y ≤ 40,

3x + y ≥ 30,

4x + 3y ≥ 60,

x ≥ 0, y ≥ 0

Шаг 1: Поиск точек

Мы также можем написать так

l1 = x + 2y = 40 …. (i)

l2 = 3x + y = 30 …. (ii)

l3 = 4x + 3y = 60 …. (iii)

Теперь мы находим точки

Итак, возьмем eq(i), теперь в этом уравнении

Когда x = 0, y = 20

и когда y = 0, x = 40

Итак, точки (0, 20) и (40, 0)

Аналогично, в eq(ii)

Когда x = 0, y = 30

Когда y = 0, x = 10

Итак, точки (0, 30) и (10, 0)

Аналогично, в eq(iii)

Когда x = 0, y = 20

Когда y = 0, x = 15

Итак, точки (0, 20) и (15, 0)

Шаг 2: Теперь постройте эти точки на графике и найдите подходящую область.

Шаг 3: Теперь мы находим удобное значение Z(целевая функция)

Итак, предположим, что z = 0

20x + 10y = 0

x = -1/2y

нарисуйте линию этой целевой функции на графике:

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

Эта параллельная линия касается допустимой области в точке A. Таким образом. Теперь мы находим координаты точки A:

Как видно из графика в точке А линии l2 и l3 пересекаются, поэтому мы находим координату точки А. Решая эти уравнения:

l2 = 3x + y = 30 …. (iv)

l3 = 4x + 3y = 60 …. (v)

Теперь умножим eq(iv) на 4 и eq(v) на 3, получим

12x + 4y = 120

12x + 9y = 180

Теперь вычитаем оба уравнения, получим координаты (6, 12)

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

Z = 20x + 10y

Z = 20(6) + 10(12)

Z = 120 + 120

Z = 240