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

В качестве напоминания, вот проблема линейного программирования, с которой мы работаем.

Максимизировать П = 40x + 30 лет    
Подлежит:     икс + 2y 16
      икс + y 9
      3x + 2y 24
      икс , y 0

Нарисуйте граничные линии

Эскиз линейных уравненийПервый шаг-нарисовать линии, соответствующие границам областей. Они находятся путем замены неравенств ≤ и ≥ знаком равенства,=.

Не помещайте целевую функцию на график.

Мы изображаем только ограничения или линейные неравенства на этом графике.

Если вы строите графики функций вручную, то, вероятно. Самым быстрым способом построения графика является приведение неравенств в стандартную форму Ax + By = C для линии. А затем нахождение перехватов x и y. Если вы хотите построить их график с помощью технологии, то решение их явно для y. Чтобы они были в форме перехвата наклона, вероятно. Является самым простым методом.

График этого показан справа.

Посмотрите флеш-видео: Как построить график линий с помощью Winplot [2,1 МБ].

Затените неравенство

Система линейных неравенствЗатенение неравенства приводит к затенению полуплоскости.

Для большинства неравенств, которые мы имеем из задач линейного программирования. Довольно легко определить. В каком направлении затенять. Просто взглянув на неравенство. Когда вы пишете в стандартной форме Ax + By ≤ C или Ax + By ≥ C. То вы будете затенять ниже или слева для меньшего или равного или выше или справа для большего или равного неравенства.

Однако эта логика не работает, если A или B отрицательны. Например, -3x + 2y ≤ -2 затеняется справа (ниже) линии. В то время как 3x — 2y ≤ 4 затеняется слева (выше) линии. Верный способ определить. В каком направлении следует затенять, — это выбрать тестовую точку. Которая не находится на линии границы. И включить это значение в неравенство.

Начало координат (0,0) обычно легко использовать до тех пор. Пока оно не является решением линейного уравнения. В приведенных выше примерах левая сторона-3x + 2y ≤ -2 становится -3(0) + 2(0) = 0, которая не меньше -2, поэтому точка (0,0) не является решением линейного неравенства. Поскольку (0,0) находится выше линии и не работает, мы затеняем ниже линии.

Решением системы линейных неравенств является область. Которая удовлетворяет всем неравенствам и называется допустимой областью.

Посмотрите флеш-видео: Как затенить неравенства с помощью Winplot [1.1 MB].

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

Этот реальный регион довольно велик. Существует бесконечное число точек в области, где могло бы быть решение. Точки (0,0), (0,1), (0,2), (1,2), (1,7), (2.16,4.92), и т. Д., все они находятся в одном регионе. К счастью, у нас есть фундаментальная теорема линейного программирования, чтобы помочь.

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

Другими словами, решение будет находиться на краю региона, а не посередине. Угловая точка-это вершина допустимой области, поэтому нам нужно выяснить. Где они находятся.