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

Разве не было бы хорошо. Если бы мы могли просто производить и продавать бесконечно много единиц продукта и таким образом зарабатывать бесконечное количество денег? В бизнесе (и в повседневной жизни) мы знаем, что мы не можем просто выбрать что-то. Потому что это имело бы смысл. Что это (необоснованно) достигло бы нашей цели. Вместо этого мы надеемся максимизировать или минимизировать некоторую величину. Учитывая набор ограничений.

Подумайте об этом: вы путешествуете из Чандлера, штат Аризона, в Сан-Диего, штат Калифорния. Ваша надежда состоит в том. Чтобы добраться туда как можно быстрее, а значит. Свести к минимуму время в пути.

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

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

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

, и

и

.

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

  • Ограничения неравенства
  • Целевая функция, то есть функция. Значение которой мы либо хотим быть как можно большим (хотим максимизировать его). Либо как можно меньшим (хотим минимизировать его).

Пример 1

Авиакомпания предлагает билеты на автобус и первый класс. Чтобы авиакомпания была прибыльной. Она должна продать как минимум 25 билетов первого класса и как минимум 40 билетов на автобус. Компания получает прибыль в размере 225 долларов за каждый билет на автобус и 200 долларов за каждый билет первого класса. Самое большее, самолет вмещает 150 пассажиров. Сколько из каждого билета должно быть продано, чтобы максимизировать прибыль?

Решение

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

x = количество билетов на автобус

y = # билетов первого класса

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

Прибыль за билеты на автобус составляет 225 долларов. Если
билеты на автобус x проданы, общая прибыль по этим билетам составляет 225x.

Прибыль за билеты первого класса составляет 200 долларов. Аналогично, если
продаются билеты первого класса y, общая прибыль по этим билетам составляет 200 лет.

Общая прибыль, Р, равна

P = 225x + 200y

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

  • Продайте не менее 25 билетов первого класса
  • Продайте не менее 40 билетов на автобус
  • Можно продать не более 150 билетов (в самолете может поместиться не более 150 человек)

Нам нужно их количественно оценить.

  • По крайней мере, 25 билетов первого класса означают, что должно быть продано 25 или более билетов. То есть y 

    25

  • По крайней мере, 40 билетов на автобус означает, что 40 или более должны быть проданы. То есть x 

    40

  • Сумма билетов первого класса и автобуса должна быть не менее 150. То есть x + y 

    150

Таким образом, целевая функция вместе с тремя математическими ограничениями:

Целевая функция: P = 225x + 200y

Ограничения: y 

25; x

40; x + y 

150

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

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

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

x= 25

y = 40

x + y = 150

Первые два уравнения представляют собой горизонтальные и вертикальные линии соответственно. Чтобы построить график x + y= 150, предпочтительно найти горизонтальные и вертикальные перехваты.

Чтобы найти вертикальный перехват, пусть
x = 0:
y= 150

Давая нам точку (0,150)

Чтобы найти горизонтальный перехват, пусть
y = 0:
x = 150

Давая нам точку (150,0)

Построение всех трех уравнений дает:

Наша следующая задача — принять во внимание неравенство.

Сначала мы спрашиваем, когда y 

25? Так как это горизонтальная линия, проходящая через y-значение 25, что-либо выше этой линии представляет собой значение больше 25. Обозначим это затенением над линией:

Это говорит нам, что любая точка в зеленой затененной области удовлетворяет ограничению, что
y 

25.

Далее мы имеем дело с
x 

40. Мы спрашиваем, когда значение xбольше 40? Значения слева меньше 40, поэтому мы должны затенить их вправо, чтобы получить значения больше 40:

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

У нас есть еще одно ограничение для рассмотрения:
x+ y 

150. У нас есть два варианта: либо тень ниже, либо тень выше. Чтобы лучше видеть, что на самом деле нам нужно будет затениться ниже линии. Рассмотрим упорядоченную пару в обеих областях. Выбор упорядоченной пары выше линии, например (64, 130), дает:

64 + 130

 150

Что является ложным утверждением, так как 64 + 130 = 194, значение больше 150.

Согласно графику, точка (64, 65) — это точка. Которая падает ниже графика. Ввод этой пары дает следующее утверждение:

64 + 65

 150

Что является истинным утверждением, поскольку 64+65 равно 129, то есть значение меньше 150.

Поэтому мы затеняем тень ниже этой линии:

Область, в которой пересекаются зеленые, синие и фиолетовые оттенки. Удовлетворяет всем трем ограничениям. Эта область известна как выполнимые области, так как этот набор точек выполним. Учитывая все ограничения. Мы можем проверить, что точка, выбранная в этой области, удовлетворяет всем трем ограничениям. Например, выбор (64, 65) дает:

64

40 ПРАВДА

65

25 ВЕРНО

64 + 65

150 ВЕРНО

Это подводит нас к важному моменту. Но все же не дает ответа на вопрос:
какая точка максимизирует прибыль? К счастью, существует теорема, открытая математиками, которая позволяет нам ответить на этот вопрос.

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

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

Фундаментальная теорема линейного программирования

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

Это означает, что мы должны выбрать одну из трех угловых точек. Чтобы проверить “победителя”, мы должны увидеть. Какая из этих трех точек максимизирует целевую функцию. Чтобы найти угловые точки в виде упорядоченных пар. Мы должны решить три системы двух уравнений каждая:

Система 1

x = 40

x + y = 150

Система 2

x = 40

y= 25

Система 3

y = 25

x+ y = 150

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

Система 1

(40) + y = 150

y = 110

Балл:(40,110)

Система 2

Точка уже дана

Балл: (40,25)

Система 3

x + 25 = 150

x = 125

Балл: (125,25)

Мы проверяем каждую из этих трех точек в целевой функции:

Точка Прибыль
(40,110) 225(40) + 200(110) = $31,000
(40,25) 225(40) + 200(25) = $14,000
(125,25) 225(125) + 200(25) = $33,125

Третий пункт (125,25) максимизирует прибыль. Таким образом, мы приходим к выводу. Что авиакомпания должна продать 125 билетов на автобус и 25 билетов первого класса. Чтобы максимизировать прибыль.

Приведенный выше пример был довольно длинным и имел много шагов для завершения. Мы кратко изложим процедуру ниже:

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

  1. Определите переменные, которые должны быть оптимизированы. Заданный вопрос-хороший показатель того, какими они будут.
  2. Запишите целевую функцию словами, а затем преобразуйте ее в математическое уравнение
  3. Запишите ограничения словами, а затем преобразуйте их в математические неравенства
  4. Изобразите ограничения в виде уравнений
  5. Затенение выполнимых областей с учетом знака неравенства и его направления. Если,

а)Вертикальная линия

, затем тень слева

, затем тень вправо

б) Горизонтальная линия

, затем тень ниже

, затем тень выше

в) Линия с ненулевым, определенным наклоном

, тень ниже

, тень выше

6. Определите угловые точки, решая системы линейных уравнений. Пересечение которых представляет собой угловую точку.

7. Проверьте все угловые точки в целевой функции. “Выигрышная” точка-это точка. Которая оптимизирует целевую функцию (наибольшая при максимизации. Наименьшая при минимизации)

Есть один пример, в котором мы должны быть очень осторожны. Во-первых, рассмотрим (истинное) неравенство,

5 > 3

Предположим, что мы должны были разделить обе стороны на -1. Было бы все еще верно сказать следующее?

51>31

5>3

Ясно, что -5 не больше, чем -3! Чтобы сохранить это утверждение истинным. Мы должны изменить направление знака неравенства так, чтобы,

–5

Мы можем видеть по числовой строке ниже, что два набора чисел симметричны относительно 0, за исключением того, что способ. Которым мы описываем размер. Противоположен. Это оправдывает, что мы также должны использовать противоположный знак. Когда мы отражаем значения по другую сторону от 0.

Изменение знака неравенства

При умножении/делении любого неравенства на -1 направление неравенства должно измениться

Пример 2

Бизнес здорового питания хотел бы создать высококалорийную смесь сухофруктов в виде коробки из 10 фруктовых батончиков. Он решает использовать курагу, в которой содержится 407 мг калия на порцию, и сушеные финики. В которых содержится 271 мг калия на порцию (ИСТОЧНИК: www.thepotassiumrichfoods.com).

Компания может приобрести свои фрукты через
www.driedfruitbaskets.com оптом по разумной цене. Курага стоит $9,99/фунт (около 3 порций), а сушеные финики — $7,99/фунт (около 4 порций). Компания хотела бы. Чтобы в коробке батончиков было по крайней мере рекомендованное ежедневное потребление калия около 4700 мг. Но хотела бы. Чтобы оно было в два раза меньше рекомендуемого ежедневного потребления. Чтобы свести к минимуму затраты, сколько порций каждого сухофрукта должно идти в коробку батончиков?

Решение

Начнем с определения переменных. Пусть,
х = # порций кураги

y = # порций сушеных фиников

Далее мы работаем над целевой функцией.

Для абрикосов есть 3 порции в одном фунте. Это означает, что стоимость одной порции составляет $9,99/3 = $3,33. Таким образом, стоимость
x порций составит 3,33x.

Для фиников есть 4 порции на фунт. Это означает, что стоимость одной порции составляет $7,99/4
$2,00. Таким образом, стоимость y порций составит 2,00y.

Общая стоимость абрикосов и фиников составит

C = 3,33x + 2,00y

У нас есть два основных ограничения (в дополнение к ограничениям, что
x 

0
и y 

0, учитывая. Что отрицательные порции не могут быть использованы):

  • Продукт должен содержать не менее 4700 мг калия
  • Продукт должен содержать не более 4700 × 2 = 9400мг калия

Математически,

  • Вx порциях абрикосов содержится 407 x мг калия, ав y порциях фиников-271 y мг калия. Сумма должна быть больше или равна 4700 мг калия, или 407x + 271y 

    4700

  • Та же сумма должна быть меньше или равна 9400 мг калия, или 407х + 271у

     9400.

Таким образом, мы имеем,

Целевая функция: C = 3,33x + 2,00y

С Учетом Ограничений:

407x + 271y 

4700

407x + 271y 

9400

x 

0
y 

0

Мы изобразим ограничения в виде уравнений:

Так как первое неравенство имеет

, мы должны затенить выше и, так как второе неравенство имеет

, мы должны затенить ниже (Эта идея может быть подтверждена путем выбора точек выше и ниже каждой линии для проверки.):

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

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

Система 1

x = 0

407x + 271y =4700

Решение:

0 + 271
y = 4700

y ≈ 17.3

Точка: (0,17.3)

Система 2

x = 0

407x + 271y = 9400

Решение:

0 + 271y = 9400

y ≈ 34.7

Точка: (0,34.7)

Система 3

y = 0

407x + 271y = 4700

Решение:

407х + 0 = 4700

x ≈ 11.5

Точка: (11.5,0)

Система 4

y = 0

407x + 271y = 9400

Решение:

407х + 0 = 9400

x ≈ 23.1

Точка: (23.1,0)

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

Точка Стоимость
(0,17.3) 33.3(0) = 2.00(17.3) = $34.60
(0,34.7) 33.3(0) = 2.00(34.7) = $69.40
(11.5,0) 33.3(11.5) = 2.00(0) = $38.30
(23.1,0) 33.3(23.1) = 2.00(0) = $76.92

Самым дешевым маршрутом для компании будет создание батончиков. Не содержащих кураги и 17,3 порции сушеных фиников.

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

Почему мы видим то, что видим? Это действительно случай создания реального продукта! Конечно. Нет смысла увеличивать ежедневное потребление для коробки. Так как это означало бы увеличение количества сухофруктов. А следовательно. И увеличение стоимости. Так как стоимость сушеных фиников дешевле ($2,00 за порцию) и так как за цену одной порции абрикосов ($3,33 за порцию) мы можем заплатить:

407mg$3.33122.2

мг на доллар за абрикосы

и

271mg$2.00135.5

мг за доллар для фиников

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

Вопрос все еще остается: желательно ли требовать большее количество фиников за меньшую цену. Или более желательно требовать меньшее количество абрикосов за большую цену? Это действительно зависит от ограничений. Компания может захотеть рассмотреть объем упаковки/обработки/и т. Д., Необходимый в обоих случаях. Возможно, затраты на производство и упаковку могут добавить ограничения. Которые изменят процесс принятия решений. Аналогичная проблема будет оставлена в качестве домашнего задания для размышления читателя.

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

Есть два термина, с которыми мы должны быть знакомы. Когда имеем дело с неравенствами: ограниченный и неограниченный. Допустимая область называется ограниченной, если ограничения охватывают допустимую область.

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

Оба примера до сих пор были примерами ограниченных задач линейного программирования. Поскольку первая допустимая область имела форму треугольника. А вторая-трапеции.

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

Пример 3

Управление людских ресурсов работает над повышением начальной заработной платы для новых административных секретарей и преподавателей в местном колледже. Административный секретарь начинается с 28 000 долларов. А новые преподаватели получают 40 000 долларов. Колледж хотел бы определить процентное увеличение для каждой группы, учитывая. Что колледж будет нанимать 8 секретарей и 7 преподавателей в предстоящем учебном году. Колледж имеет самое большее 5000 долларов, чтобы положить на повышение. Каким должно быть процентное увеличение для каждой группы?

Решение

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

x = процентное увеличение для секретарей

y = процентное увеличение для профессорско-преподавательского состава

Колледж хотел бы минимизировать свои общие расходы. Поэтому целевая функция должна включать в себя общую сумму оттока денег. Поскольку новым секретарям потребуется общий бюджет в размере
$28 000 × 8 = $224 000, а профессорско-преподавательскому составу-общий бюджет в размере $40 000 × 7 = $280 000, общие расходы будут равны проценту повышения зарплаты для каждой группы. Умноженному на общую зарплату:

C = 224x + 280y

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

224x + 280y 

5

Конечно, колледж не хочет снижать зарплату, поэтому
x 

0 и y 

0.

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

Горизонтальный перехват:

224(0) + 280
y = 5
y ≈ .018

Вертикальный перехват

224x + 280(0) = 5
x ≈ .022

Затем мы строим точки и соединяем их прямой линией:

Так как знак неравенства

, мы тень ниже линии:

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

Точка Стоимость
(0,0) 224(0) + 280(0) = $0
(0,.018) 224(0) + 280(.018) = $5.04
(.020,0) 224(.020) + 280(0) = $4.48

Очевидно, что первый вариант дает наименьшую стоимость; однако эта комбинация говорит нам о том. Чтобы дать 0% — ный рейз обеим группам. Что, конечно. Непрактично. Поскольку целью компании было дать рейз каждой группе.

Почему это произошло, и что мы должны сделать, чтобы исправить это? Ну, когда мы думаем об ограничении расходов в размере 5000 долларов или меньше и надеемся сделать расходы как можно меньше. Разве не имеет смысла сказать: “ничего не тратьте!”? Этот результат будет происходить в любое время, когда мы минимизируем. Имеем ограничения с
le знак неравенства. И когда начало координат входит в допустимую область. Чтобы устранить проблему, компания должна сделать дополнительные спецификации, такие как. Какой минимальный процент повышения дать каждой группе? Желательно ли, чтобы один из рейзов был больше другого? Эти вопросы аналитик должен обсудить с персоналом и администрацией.

1) Решите каждую из следующих задач линейного программирования.

а) Максимизировать R = 2x + 3y

При условии
-2xy 

-10
x + 3y

 6

x 

0
y 

0

Решение: R=30 при (0,10)

Б) Минимизировать T = 3x + y

При условии
x + 2y

4
x + 3y 

6

x 

0
y 

0

Решение: R=2 при (0,2)

2) Местный школьный совет утверждает новую программу математического образования. Которая должна быть реализована в ряде начальных школ района. Деньги на программу будут поступать из двух разных бюджетов: бюджета государственных расходов и бюджета школьных инициатив. Правление готово выплатить не менее половины того, что поступает из бюджета инициатив. Из своего бюджета государственных расходов. Поскольку эта программа считается инициативой, правительство требует. Чтобы из бюджета местных инициатив поступило не менее 2000 долларов. Оба бюджета частично финансируются за счет федерального чрезвычайного финансирования. Для бюджета государственных расходов этот процент составляет 55%. А для бюджета инициатив начальной школы-23%. Чтобы правильно использовать чрезвычайное финансирование. Округ хотел бы свести к минимуму использование федеральных долларов. Сколько должно быть из каждого бюджета?

Решение: x=сумма от расходов publix; y=сумма от инициатив начальной школы

Минимизировать: C=0.55 x+0.23 y

y≥2000

x,y≥0

Решение: C=2660, x=4000, y=2000

3) Директор по связям с общественностью гомеопата стремится рекламировать продукцию своей компании на двух разных сайтах—один является поставщиком медицинских запчастей. А другой-фитнес-электронным журналом (веб-журналом). Веб-сайт поставщика медицинских деталей получает в среднем около 1 200 000 просмотров в день на страницу. В то время как фитнес-сайт получает около 2 000 000 просмотров в день на страницу. Ежедневная стоимость рекламы составляет 1100 долларов за рекламу и 1600 долларов за рекламу соответственно. Директор хотел бы получить не менее 15 объявлений и может выделить до 50 000 долларов на рекламу. На каждом сайте должно быть размещено не менее 3 объявлений. Сколько добавлений должно быть размещено на каждом веб-сайте. Чтобы максимизировать потенциальное количество читателей (даже если некоторые зрители видят добавление на разных страницах веб-сайта)?

x=номер на медицинском сайте; y= номер на фитнес-сайте.

Максимизация: R=1200000x+2000000y

Подлежит:

x+y≥15

1100x+1600y≤50000

x≥3

y≥3

x,y≥0

Угловые точки R=1200000x+2000000y
(3,12) 27,600,000
(12,3) 20,400,000
(3,29.2) 62,000,000
(41.1,3) 55,320,000

Оптимальное Решение

(3,29.2) 62,000,000

См. Дополнительные примеры в следующем разделе.