Решить злп графическим методом: Математическое Бюро. Страница 404

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

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

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

Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя.

Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования.

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

при которых линейная форма принимает оптимальное значение.

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

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

F линейная форма изобразится в виде некоторой прямой. Каждую из прямых этого семейства принято называть линией уровня. На рисунке построена линия уровня (чёрного цвета, проходит через начало координат), соответствующая значению F =0.

Если исходную линию уровня передвигать вправо, то значение F при этом возрастает. Нужное направление движения исходной линии уровня можно установить следующим образом. Коэффициенты при переменных в уравнении прямой служат координатами вектора, перпендикулярного этой прямой. Таким образом, получаем градиент — вектор (на рисунке бордового цвета). Значения функции F возрастают при перемещении исходной линии уровня в направлении вектора .

Среди прямых упомянутого семейства параллельных прямых прямые mn (зелёного цвета) и MN (красного цвета), которые назовём опорными. Опорными обычно называют такие прямые, которые имеют с многоугольником

ABCDE хотя бы одну общую точку, и многоугольник ABCDE целиком лежит по одну сторону от этой прямой. Как видно из чертежа, прямая mn является опорной, так как она касается многоугольника в точке A и многоугольник целиком лежит правее (или выше) этой прямой. Прямая MN также является опорной, так как имеет с многоугольником общую точку С и многоугольник целиком лежит левее этой прямой.

Из основных теорем линейного программирования известно, что линейная форма достигает максимального и минимального значений в крайних точках многогранника решений. Это значит, что опорные прямые mn и MN характеризуют экстремальные значения линейной формы (функции цели), то есть в точках А и С линейная форма достигает оптимальных значений. В точке

А, находящейся ближе к началу координат, функция цели достигает минимального значения, а в точке С, находящейся дальше от начала координат, — максимального значения.

1. Построить многоугольник решений системы неравенств.

3. Двигать прямую (или линейку) вдоль градиента — вектора параллельно линии равных значений в сторону многоугольника решений до соприкосновения с многоугольником решений. Если первая встреча с многоугольником решений произойдёт в крайней точке с координатами , то в этой точке функция цели достигает минимального значения. Если первая встреча произойдёт со стороной многоугольника, то данная функция цели достигает минимума во всех точках этой стороны.

4. Двигаясь дальше, придём к некоторому опорному положению, когда прямая будет иметь одну общую точку с многоугольником решений. В этой точке функция цели достигает своего максимума.

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

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

Построим многоугольник решений. Для этого начертим граничные прямые. Из первого неравенства запишем уравнение . Это уравнение первой граничной прямой. Найдём точки пересечения этой прямой с осями координат. При из уравнения получим , при получим . Это значит, что первая прямая отсекает от осей координат отрезки и .

Аналогично строим остальные граничные прямые. Вторая прямая от осей координат отсекает отрезки, равные 6. Третья прямая проходит параллельно оси , отсекая на оси отрезок, равный 2. Четвёртая прямая имеет уравнение . Она совпадает с осью .

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

Следовательно, четырёхугольник ABDE является многоугольником решений системы (заштрихован вовнутрь).

Начертим линию равных значений функции цели. Приняв в равенстве F =1, получим, что эта линия отсекает отрезки 1 и 1/3 соответственно на оси и на оси . Проведём прямую через эти точки (на чертеже она чёрного цвета).

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

A. Здесь функция цели достигает минимума. Двигаясь дальше, придём к точке В. Здесь максимум. Координаты точки В: (2, 4). Подставляя в функцию цели координаты точки В, т. е. , , получим максимальное значение функции цели: .

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

где .

Правильное решение и ответ.

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

где .

Правильное решение и ответ.

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

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

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

Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

.

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

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

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

C и D. Этот пример показывает, что в некоторых случаях единственность оптимального решения нарушается.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

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

Начало темы «Линейное программирование»

Поделиться с друзьями

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

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1)   ;
(1.2)  
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

Построение области допустимых решений

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

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

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

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

Можно упростить метод. Можно не заштриховывать каждую полуплоскость, а вначале построить все прямые
(2)  
Далее выбрать произвольную точку, не принадлежащую ни одной из этих прямых. Подставить координаты этой точки в систему неравенств (1.2). Если все неравенства выполняются, то область допустимых решений ограничена построенными прямыми и включает в себя выбранную точку. Заштриховываем область допустимых решений по границам прямых так, чтобы оно включало в себя выбранную точку.

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1)   .

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

Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.

Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.

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

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

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида — 10 м, третьего вида — 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В — 300 ден. ед.

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

Решение

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
  и   .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Прямые и являются осями координат.

Область допустимых решений (ОДР) ограничена построенными прямыми и осями координат. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

Строим произвольную линию уровня целевой функции, например,
(П1.1)   .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

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

Решение задачи: ;

Ответ

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

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

Решение

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую   (ось абсцисс).

Область допустимых решений (ОДР) ограничена построенными прямыми. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

.

Пример отсутствия решения

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

Решение

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

Область допустимых решений (ОДР) ограничена построенными прямыми и осями координат. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1)   .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

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

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

Ответ

Максимального значения не существует.
Минимальное значение
.

Автор: Олег Одинцов.     Опубликовано: 08-08-2016

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

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

LOGO
Задача линейного программирования с
двумя неизвестными может быть решена
графически
Замечание:
К такой форме может быть сведена и каноническая задача (с
ограничениями в виде уравнений), когда число переменных n
больше числа уравнений m на 2
Пусть задача линейного программирования
задана в виде:
Алгоритм графического решения ЗЛП
1. Построить область допустимых решений
(ОДР) в системе координат, заданную системой
ограничений
Алгоритм графического решения ЗЛП
2. Построить градиент целевой функции
F = с1х1+с2х2
(вектор нормали к прямой с1х1+с2х2 = F)
Алгоритм графического решения ЗЛП
3. Построить опорную прямую,
перпендикулярную вектору нормали – линию
уровня целевой функции
Алгоритм графического решения ЗЛП
4. Перемещая опорную прямую в направлении вектора
нормали, определить «точку входа» и «точку выхода»
(первая встретившаяся опорной прямой точка из ОДР и
последняя встретившаяся опорной прямой точка из ОДР
соответственно)
В точке входа: F min
В точке выхода: F max
Алгоритм графического решения ЗЛП
5. Определить координаты оптимальной точки
(точки входа или точки выхода) и найти значение
целевой функции в ней
Замечание:
Оптимальная точка
является угловой точкой
выпуклой области
допустимых решений
Частные случаи
Минимальное значение целевая функция
достигает в точке В: Fmin = F(B)
Максимальное значение: Fmax =
Частные случаи
Минимальное значение целевая функция
достигает в точке E: Fmin = F(E)
Максимальное значение целевая функция
достигает во всех точках отрезка ВС :
Fmin = F(B)= F(C)
Решить графически ЗЛП
Решить графически ЗЛП
1. Построим область допустимых решений,
заданную системой неравенств
(см. презентацию Геометрический смысл линейного
неравенства)
Решить графически ЗЛП
2. Построим вектор нормали N(3;4) и
перпендикулярную ему опорную прямую
Решить графически ЗЛП
Файл 04_model_01.ggb
3. Перемещаем опорную прямую в направлении
вектора нормали и определяем «точку выхода»
В – точка выхода
Решить графически ЗЛП
4. Найдем координаты точки В, как точки
пересечения прямых (1) и (3)
Решить графически ЗЛП
4. Найдем координаты точки В, как точки
пересечения прямых (1) и (3):
Решить графически ЗЛП
5. Найдем значение целевой функции в точке В
Решить графически ЗЛП
Ответ:
Литература
1. Кремер Н.Ш., Путко Б.А. Исследование
операций в экономике. — М.: ЮНИТИ, 2003. 407 с.
2. Данко П.Е., Попов А.Г., Кожевникова Т.Я.
Высшая математика в упражнениях и задачах.
Часть 1. — М.: Высшая школа, 1986. – C.271-274

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

Цель: научиться решать задачи линейного программирования графическим методом; уметь давать экономическую интерпретацию полученного решения.

Теоретическая часть

Задача

Найти X1 и X2 удовлетворяющие системе неравенств:

(37)

условиям неотрицательности: X1≥0, X2≥0, (38)

для которых функция: R=C1X1+C2X2 (39)

достигает максимума.

Решение.

Построим в системе прямоугольных координат Х1ОХ2 область допустимых решений задачи. Для этого, заменяя каждое из неравенств (37) равенством, строим соответствующую ему граничную прямую ai1x1+ai2x2≤bi (i=1,2,…,r) (рис.17).

рис. 17

Эта прямая делит плоскость Х1ОХ2 на две полуплоскости, для координат X1, X2 любой точки А одной полуплоскости выполняется неравенство: ai1x1+ai2x2≤bi , а для координат X1, X2 любой точки В другой полуплоскости противоположное неравенство: ai1x1+ai2x2≥bi .

Координаты любой точки граничной прямой удовлетворяют уравнению:

ai1x1+ai2x2=bi .

Для определения, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку (проще всего точку О (0,0 )). Если при подстановке ее координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже (рис.17) штриховкой.

Неравенствам X1≥0 и X2≥0 также соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.

На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.

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

Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет.

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

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

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

Рис.18

Графическое изображение целевой функции R=C1X1+C2X2 при фиксированном значении R определяет прямую, а при изменении R — семейство параллельных прямых с параметром R.

Вектор, перпендикулярный ко всем этим прямым, показывает направление возрастания R .

Для всех точек, лежащих на одной из прямых, функция R принимает одно определенное значение, поэтому указанные прямые называются линиями уровня для функции R (рис.19).

Рис.19.

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

Если область допустимых решений есть выпуклый многоугольник» то экстремум функции R достигается по крайней мере в одной из вершин этого многоугольника.

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

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

Пример.

Найти X1 и X2 , удовлетворяющие системе неравенств:

(40)

условиям неотрицательности: X1≥0, X2≥0, для которых функция R=2X1+3X2 достигает максимума.

Решение.

1. Заменим каждое из неравенств равенством и построим граничные прямые (рис.20)

рис.20

2. Определим полуплоскости, соответствующие данным неравенствам (40) путем «испытания» точки (0,0). Покажем направления полуплоскостей штриховкой (рис .21). С учетом неотрицательности X1 и Х2 получим область допустимых решений данной задачи в виде выпуклого многоугольника ОАВДЕ.

рис.21

3. В области допустимых решений находим оптимальное решение, строя вектор который показывает направление возрастания R (рис.21).

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

Х1 — Х2 = -4 ,

X1 + Х2 = 8 .

Ответ: X1=2, X2 = 6, Rmax=22.

Практическая часть

Номер варианта заданий соответствует списочному номеру студента

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

Вариант 1

Решить графически ЗЛП: Z = 4х₁ + 6х₂  min (max)

3х₁ + х₂  9

х₁ +2х₂  8

х₁ + 6х₂  12

х₁ 0, х₂ 0

Вариант 2

Решить графически ЗЛП: Z = 3х₁ + 3х₂  max (min)

х₁ + х₂  8

2х₁ – х₂  1

х₁ –2х₂  2

х₁  0, х₂  0

Вариант 3

Решить графически ЗЛП: F(x) = 2x₁ – 5x₂ → min(max)

х₁ + 2х₂10

х₁ + 2х₂2

2х₁ + х₂10

х₁0, х₂0

Вариант 4

Решить графически ЗЛП: Z = x₁ – 10x₂ → min(max)

х₁ – 0,5х₂ ≥ 0

х₁ – 5х₂ ≥ 0

х_i  0, i = 1,2.

Вариант 5

Решить графически ЗЛП: Z= — 2x₁ + 5x₂ → min(max)

7х₁ + 2х₂ ≥ 14

5х₁ +6х₂ ≤ 3

3х₁ + 8х₂ ≥ 2

х_i  0, i = 1,2

Вариант 6

Решить графически ЗЛП: Z = 3х₁ + х₂  max(min)

х₁ + х₂  8

2х₁ – х₂  1

х₁ –2х₂  2

х₁  0, х₂  0

Вариант 7

Решить графически ЗЛП: Z = 2х₁ + 3х₂  max(min)

3х₁ + 3х₂  6

х₁ + х₂  1

х₁  0, х₂  0

Вариант 8

Решить графически ЗЛП: Z = 2х₁ + 3х₂  max(min)

3х₁ + 2х₂  6

х₁ + 4х₂  4

х₁  0, х₂  0

Вариант 9

Решить графически ЗЛП: Z = х₁ + 3х₂  max(min)

х₁ + 4х₂  4

х₁ + х₂  6

х₂  2

х₁  0, х₂  0

Вариант 10

Решить графически ЗЛП: Z = 3х₁ – 4х₂  max(min)

х₁ – 2х₂  6

х₁ + 2х₂  0

х₁  6

х₁  0, х₂  0

Вариант 11

Решить графически ЗЛП: Z = — 2х₁ + 5х₂  max(min)

7х₁ + 2х₂  14

3х₁ + 8х₂  24

5х₁ + 6х₂  30

х₁  0, х₂  0

Вариант 12

Решить графически ЗЛП: Z = 3х₁ – 2х₂  max(min)

7х₁ + 2х₂  14

— х₁ + 2х₂  2

7х₁ + 10х₂  28

х₁  0, х₂  0

Вариант 13

Решить графически ЗЛП: Z = 2х₁ – 10х₂  max(min)

х₁ – х₂  0

х₁ – 5х₂  — 5

х₁  0, х₂  0

Вариант 14

Решить графически ЗЛП: Z = х₁ – 10х₂  max(min)

х₁ – х₂  0

х₁ – 5х₂  — 5

х₁  0, х₂  0

Вариант 15

Решить графически ЗЛП: Z = х₁ + х₂  max(min)

х₁ + 2х₂  10

х₁ + 2х₂  2

2х₁ + х₂  10

х₁  0, х₂  0

Задание № 2. Составить экономико-математическую модель задачи. Решить задачу геометрически. Дать экономический анализ.

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

# Первый график

x1<- (-100:500)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-10, 50),ylim = c(-10, 50),bty="n",xaxt="n",yaxt="n")
polygon(c(0,0,10,20,22),c(12,33,30,20,12), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-10,10,20,30,40))
axis(2,pos=c(0,0),las=2,at=c(-10,10,20,30,40))
arrows(-10.5,0,51,0,angle=15)
arrows(0,-10.5,0,51,angle=15)
lines(x1,(330-3*x1)/10,col="blue")
text(30,30,expression(3*х[1]+10*х[2]==330),cex=0.8,col="blue")
lines(x1,(400-16*x1)/4,col="red")
text(20,45,expression(16*х[1]+4*х[2]==400),cex=0.8,col="red")
lines(x1,(240-6*x1)/6,col="green")
text(8,40,expression(6*х[1]+6*х[2]==240),cex=0.8,col="green")
abline(h=12)
lines(x1,(-25*x1)/35,lty=3,lwd=3)
text(-5,5,expression(2500*х[1]+3500*х[2]==0),cex=0.8)
arrows(0,0,12.5,17.5)
lines(x1,(130000-2500*x1)/3500,lty=2,lwd=3)
text(35,20,expression(2500*х[1]+3500*х[2]==130000),cex=0.8)
points(10,30,cex=1.5,col="red",pch=19)

# Второй график

x1<- (-50:50)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-5, 5),ylim = c(-5, 5),bty="n",xaxt="n",yaxt="n")
polygon(c(-8,-8,8),c(9,-8,-7), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-4,-3,-2,-1,1,2,3,4))
axis(2,pos=c(0,0),las=2,at=c(-4,-3,-2,-1,1,2,3,4))
arrows(-5.5,0,5.5,angle=15)
arrows(0,-5.5,0,5.5,angle=15)
abline(1,-1)
text(-3,2,expression(х[1]+х[2]<=1),col="black")
text(5,0.5,expression(х[1]),col="black")
text(0.5,5,expression(х[2]),col="black")

# Третий график

x1<- (-50:50)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-5, 5),ylim = c(-5, 5),bty="n",xaxt="n",yaxt="n")
polygon(c(-8,8,8),c(-7,9,-8), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-4,-3,-2,-1,1,2,3,4))
axis(2,pos=c(0,0),las=2,at=c(-4,-3,-2,-1,1,2,3,4))
arrows(-5.5,0,5.5,angle=15)
arrows(0,-5.5,0,5.5,angle=15)
abline(1,1)
text(2,-3,expression(х[1]+х[2]<=1),col="black")
text(5,0.5,expression(х[1]),col="black")
text(0.5,5,expression(х[2]),col="black")

# Четвертый график
x1<- (-50:50)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-5, 5),ylim = c(-5, 5),bty="n",xaxt="n",yaxt="n")
polygon(c(-8,-8,8),c(-9,9,7), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-4,-3,-2,-1,1,2,3,4))
axis(2,pos=c(0,0),las=2,at=c(-4,-3,-2,-1,1,2,3,4))
arrows(-5.5,0,5.5,angle=15)
arrows(0,-5.5,0,5.5,angle=15)
abline(-1,1)
text(-2,1,expression(х[1]-х[2]<=1),col="black")
text(5,0.5,expression(х[1]),col="black")
text(0.5,5,expression(х[2]),col="black")

# Первый график

x1<- (-100:500)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-10, 50),ylim = c(-10, 50),bty="n",xaxt="n",yaxt="n")
polygon(c(0,0,10,20,22),c(12,33,30,20,12), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-10,10,20,30,40))
axis(2,pos=c(0,0),las=2,at=c(-10,10,20,30,40))
arrows(-10.5,0,51,0,angle=15)
arrows(0,-10.5,0,51,angle=15)
lines(x1,(330-3*x1)/10,col="blue")
text(30,30,expression(3*х[1]+10*х[2]==330),cex=0.8,col="blue")
lines(x1,(400-16*x1)/4,col="red")
text(20,45,expression(16*х[1]+4*х[2]==400),cex=0.8,col="red")
lines(x1,(240-6*x1)/6,col="green")
text(8,40,expression(6*х[1]+6*х[2]==240),cex=0.8,col="green")
abline(h=12)
lines(x1,(-25*x1)/35,lty=3,lwd=3)
text(-5,5,expression(2500*х[1]+3500*х[2]==0),cex=0.8)
arrows(0,0,12.5,17.5)
lines(x1,(130000-2500*x1)/3500,lty=2,lwd=3)
text(35,20,expression(2500*х[1]+3500*х[2]==130000),cex=0.8)
points(10,30,cex=1.5,col="red",pch=19)

# Второй график

x1<- (-50:50)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-5, 5),ylim = c(-5, 5),bty="n",xaxt="n",yaxt="n")
polygon(c(-8,-8,8),c(9,-8,-7), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-4,-3,-2,-1,1,2,3,4))
axis(2,pos=c(0,0),las=2,at=c(-4,-3,-2,-1,1,2,3,4))
arrows(-5.5,0,5.5,angle=15)
arrows(0,-5.5,0,5.5,angle=15)
abline(1,-1)
text(-3,2,expression(х[1]+х[2]<=1),col="black")
text(5,0.5,expression(х[1]),col="black")
text(0.5,5,expression(х[2]),col="black")

# Третий график

x1<- (-50:50)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-5, 5),ylim = c(-5, 5),bty="n",xaxt="n",yaxt="n")
polygon(c(-8,8,8),c(-7,9,-8), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-4,-3,-2,-1,1,2,3,4))
axis(2,pos=c(0,0),las=2,at=c(-4,-3,-2,-1,1,2,3,4))
arrows(-5.5,0,5.5,angle=15)
arrows(0,-5.5,0,5.5,angle=15)
abline(1,1)
text(2,-3,expression(х[1]+х[2]<=1),col="black")
text(5,0.5,expression(х[1]),col="black")
text(0.5,5,expression(х[2]),col="black")

# Четвертый график
x1<- (-50:50)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-5, 5),ylim = c(-5, 5),bty="n",xaxt="n",yaxt="n")
polygon(c(-8,-8,8),c(-9,9,7), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-4,-3,-2,-1,1,2,3,4))
axis(2,pos=c(0,0),las=2,at=c(-4,-3,-2,-1,1,2,3,4))
arrows(-5.5,0,5.5,angle=15)
arrows(0,-5.5,0,5.5,angle=15)
abline(-1,1)
text(-2,1,expression(х[1]-х[2]<=1),col="black")
text(5,0.5,expression(х[1]),col="black")
text(0.5,5,expression(х[2]),col="black")

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

1. Найти решение задачи линейного программирования графическим методом.
2. Провести анализ чувствительности оптимального решения задачи.
.
(1)
1. Определим область допустимых решений задачи, то есть решим графически систему неравенств (1). Штриховкой обозначены полуплоскости, являющиеся решением каждого из неравенств.
Область допустимых значений – это пересечение множеств решений, то есть выпуклый четырехугольник .
Построим линию уровня целевой функции .
Вектор-градиент, составленный из коэффициентов целевой функции , указывает направление возрастания. Двигаем линию уровня параллельно себе до выхода из области допустимых решений.
Из графика видно, что целевая функция достигает максимума, когда линия уровня проходит через точку .
Точка – это пересечение прямых и .
Решая систему

находим ее координаты: .
При этом целевая функция достигает максимума .
при .
352425000
Анализ чувствительности оптимального решения к изменению параметров.
1. Изменение коэффициентов целевой функции.
В общем виде целевую функцию задачи ЛП можно записать следующим образом:
Максимизировать или минимизировать .
Изменение значений коэффициентов  и  приводит к изменению угла наклона прямой . Существует интервалы изменения коэффициентов  и , когда текущее оптимальное решение сохраняется. Необходимо определить интервал оптимальности для отношения (или и ).
В данной задаче оптимальное решение соответствует точке – пересечение прямых и . При изменении коэффициентов и точка останется точкой оптимального решения до тех пор, пока угол наклона линии будет лежать между углами наклона этих двух прямых.
Угловой коэффициент целевой функции :
(при условии ).
Угловой коэффициент прямой .
Угловой коэффициент прямой .
Угловой коэффициент меняет знак, нужно рассмотреть 2 случая.
При получаем интервал оптимальности
или
при .
При получаем интервал оптимальности
или
при .
При целевая функция принимает вид – вертикальная прямая. Условие сохранения оптимальности решения , откуда .
При целевая функция принимает вид – горизонтальная прямая, не является оптимальным решением в точке .
Практический смысл имеет нахождение интервала оптимальности одного из коэффициентов при фиксированном другом.
Зафиксируем значение (исходное значение). Тогда границы интервала оптимальности определим из условия равенства углам наклона прямым и .
и ; ;
и ; ; .
То есть, при оптимальное решение не изменится при .
Аналогично, при фиксированном допустимые значения .
2. Анализ чувствительности решения к изменению правой части ограничений.
Перепишем условие задачи:
.

Данная работа не уникальна. Ее можно использовать, как базу для подготовки к вашему проекту.

Точка оптимального решения – пересечение прямых и , поэтому ограничения (I) и (II) являются связывающими, (III) и (IV) – несвязывающие.
Выясним, насколько можно увеличить запас ресурса М1, чтобы улучшить полученное оптимальное решение.
0-127000
Из рисунка видно, что прямую можно перемещать параллельно себе до точки Е. Треугольник становится областью допустимых решений. При дальнейшем перемещении это ограничение становится избыточным, то есть не влияющим на оптимальное решение.
Точка Е – пересечение прямых и . Найдем ее координаты, решая систему
.
Значение М1 в точке Е: .
При этом значение целевой функции .
Перемещая прямую в другую сторону, находим, что ОДР (область допустимых решений) стягивается в точку D, которая определяет нижнюю границу интервала осуществимости для ресурса М1.
Координаты точки D – решение системы
.
Значение М1 в точке В: .
При этом значение целевой функции .
В условии задачи нет требования неотрицательности целевой функции, поэтому такое решение является допустимым.
Определим влияние ограничения М2 на оптимальное решение.

Из рисунка видно, что прямую можно перемещать в направлении градиента целевой функции до точки F, при этом ОДР – четырехугольник .
F – это точка пересечения прямой с осью , ее координаты .
При этом .
Значение целевой функции .
Найдем значение М2, при котором еще существует

Решение:

.
Для М2: .
И последнее. Определим влияние несвязывающих ограничений (III) и (IV) на оптимальное решение.

Из рисунка находим, что прямую (ограничение (III)) можно перемещать вниз до точки , при этом оптимальное решение не изменится.
Тогда значение (правая часть неравенства III).
Перемещение прямой в другую сторону не влияет на оптимальное решение.
Аналогично, прямую (ограничение (IV)) можно переместить параллельным переносом до точки .
Тогда значение (правая часть неравенства IV).
3. Выводы.
1. Решение ЗЛП
при ограничениях
существует.
при .
2. Существуют интервалы оптимальности коэффициентов целевой функции (не изменяющие полученного оптимального решения)
При оптимальное решение не изменится при .
При фиксированном допустимые значения .
3. При увеличении значения ограничения (I) до М1=12,2 максимальное значение целевой функции увеличится до .
Ценность ресурса М1 выше ценности ресурса М2, то есть изменение количества ресурсов на одну единицу приводит к большему увеличению целевой функции в первом случае.
.

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

Ваулина В. А., УрГЭУ Пример решения задачи линейного программирования графическим методом Линейное программирование — это раздел математики, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями. Существуют два наиболее распространенных способа решения задач линейного программирования: графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания решения. Также этот метод позволяет практически одновременно найти решение на минимум и максимум. Основные шаги по решению ЗПЛ графическим методом следующие: построить область допустимых решений задачи (выпуклый многоугольник), который определяется как пересечение полуплоскостей, соответствующих неравенствам задачи, построить линию уровня целевой функции, и, наконец, двигать линию уровня в нужном направлении, пока не достигнем крайней точки области — оптимальной точки (или множества). В отличие от графического метода, симплексный метод практически не имеет ограничений на задачу, может быть любое количество переменных и т.п. При решении задачи симплексным методом вычисления ведутся в таблицах. Решение задачи данным методом дает не только оптимальное решение, но и решение двойственной задачи, остатки ресурсов и т.п. Рассмотрим решение задачи линейного программирования графическим методом. Для производства столов и стульев мебельная фабрика использует три вида древесины. Норма затрат для каждого вида древесины на один стол составляет 1; 2; 5; на один стул – 1; 5; 2. Запасы древесины – 150; 600; 600. Прибыль от реализации одного стола – 200р, одного стула – 100р. Составить оптимальный план производства, обеспечивающий максимальную прибыль. Решение. Составим математическую модель задачи. Пусть Х — столы, У — стулья, I,II,III – виды древесины соответственно. I II III Прибыль X 1 2 5 200 Y 1 5 2 100 150 600 600 Общий запас Составим неравенства по полученной таблице: { x 1+ x2 ≤150, 2 x 1+5 x 2 ≤600, 5 x 1 +2 x 2 ≤600, x1,2 ≥ 0. } F ( x )=200 x 1+100 x 2 → max Применим описанные выше шаги решения. Построим область допустимых решений. Рассмотрим целевую функцию задачи F = 200×1+100×2 → max и построим вектор-градиент, составленный из коэффициентов целевой функции. Так как нас интересует максимальное решение, то опорную прямую двигаем прямую до последнего касания обозначенной области. Получаем оптимальную точку D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых: x1+x2=150 5×1+2×2=600 Решив систему уравнений, получим: x1 = 100, x2 = 50 Откуда найдем максимальное значение целевой функции: F(X) = 25000. На примере данной задачи мы рассмотрели решение задачи линейного программирования графическим методом. Этот метод наглядно показывает область дополнительных решений и нахождение оптимальной точки. Руководитель: Кныш А.А.

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

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

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

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

Задача линейного программирования включает ограничения, содержащие неравенства. Неравенство
обозначается знакомыми символами <,>, [latex] \ le [/ latex] и [latex] \ ge [/ latex]. Из-за трудностей со строгими неравенствами (<и>) мы сосредоточимся только на [латексе] \ le [/ latex] и [латексе] \ ge [/ latex].

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

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

Пример 1

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

Решение

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

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

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

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

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

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

Общая прибыль, P , составляет

P = 225 x + 200 y

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

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

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

• Минимум 25 билетов первого класса означает, что нужно продать 25 и более. То есть y [латекс] \ ge [/ latex] 25
• Не менее 40 билетов на автобус означает, что нужно продать 40 или более билетов. То есть x [латекс] \ ge [/ latex] 40
• Сумма билетов первого класса и автобусов должна быть не более 150. То есть x + y [латекс] \ le [/ latex] 150

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

Цель Функция: P = 225 x + 200 y

Ограничения: y [латекс] \ ge [/ latex] 25; x [латекс] \ ge [/ латекс] 40; x + y [латекс] \ le [/ латекс] 150

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

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

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

x = 25

y = 40

x + y = 150

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

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

Ставим нам точку (0,150)

Чтобы найти точку пересечения по горизонтали, положим
y = 0:
x = 150

Ставить нам точку (150,0)

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

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

Сперва мы спрашиваем, когда же y [latex] \ ge [/ latex] 25? Поскольку это горизонтальная линия, проходящая с по , значение y , равное 25, все, что находится выше этой линии, представляет собой значение больше 25. Мы обозначаем это штриховкой над линией:

Это говорит нам о том, что любая точка в области, заштрихованной зеленым цветом, удовлетворяет ограничению
y [latex] \ ge [/ latex] 25.

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

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

У нас есть еще одно ограничение, которое следует учитывать:
x + y [latex] \ ge [/ latex] 150. У нас есть два варианта: оттенок ниже или оттенок сверху.Чтобы помочь нам лучше понять, что на самом деле нам нужно заштриховать ниже линии , давайте рассмотрим упорядоченную пару в обоих регионах. Выбор упорядоченной пары над линией, например (64, 130), дает:

64 + 130 [латекс] \ ge [/ латекс] 150

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

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

64 + 65 [латекс] \ ge [/ латекс] 150

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

Поэтому ниже линии штрихуем:

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

64 [латекс] \ ge [/ латекс] 40 ИСТИНА

65 [латекс] \ ge [/ латекс] 25 ИСТИНА

64 + 65 [латекс] \ ge [/ латекс] 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. Заштриховать возможные области с учетом знака неравенства и его направления.Если,

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

[латекс] \ le [/ latex], затем растушевываем налево

[латекс] \ ge [/ latex], затем заштрихуйте вправо

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

[латекс] \ le [/ latex], затем оттенок ниже

[латекс] \ ge [/ latex], затем оттенок выше

c) Линия с ненулевым заданным наклоном

[латекс] \ le [/ латекс], оттенок ниже

[латекс] \ ge [/ латекс], оттенок выше

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

7. Проверьте все угловые точки целевой функции. «Выигрышная» точка — это точка, которая оптимизирует целевую функцию (наибольшая, если максимизация, наименьшая, если минимизация)

Есть один случай, в котором мы должны проявлять большую осторожность. Сначала рассмотрим (истинное) неравенство,

5> 3

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

[латекс] \ displaystyle \ frac {{5}} {{- {1}}} \ gt \ frac {{3}} {{- {1}}} [/ латекс]

[латекс] \ displaystyle- {5} \ gt- {3} [/ latex]

Понятно, что –5 не больше –3! Чтобы утверждение оставалось верным, мы должны изменить направление знака неравенства так, чтобы,

–5 <–3

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

Смена знака неравенства

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

Пример 2

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

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

Решение

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

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

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

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

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

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

.

C = 3,33 x + 2,00 y

У нас есть два основных ограничения (в дополнение к ограничениям, что
x [latex] \ ge [/ latex] 0
и y [latex] \ ge [/ latex] 0, учитывая, что отрицательные порции не могут быть использованы ):

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

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

• В порциях абрикосов x содержится 407 x мг калия и 271 y мг калия в y порциях фиников.Сумма должна быть больше или равна 4700 мг калия, или 407 x + 271 y [латекс] \ ge [/ latex] 4700
• Та же сумма должна быть меньше или равна 9400 мг калия, или 407 x + 271 y [латекс] \ le [/ latex] 9400.

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

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

При соблюдении ограничений:

407 x + 271 y [латекс] \ ge [/ латекс] 4700

407 x + 271 y [латекс] \ le [/ латекс] 9400

x [латекс] \ ge [/ латекс] 0
y [латекс] \ ge [/ латекс] 0

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

Так как первое неравенство имеет [латекс] \ ge [/ latex], мы должны заштриховать вверху, а так как второе неравенство имеет [латекс] \ le [/ latex], мы должны заштриховать внизу (Эта идея может быть подтверждена выбором точек выше и ниже каждой строки для проверки.):

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

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

Система 1

х = 0

407 x + 271 y = 4700

Решение:

0 + 271
y = 4700

y ≈ 17.3

Балл: (0,17.3)

Система 2

x = 0

407 x + 271 y = 9400

Решение:

0 + 271 y = 9400

y ≈ 34,7

Балл: (0,34.7)

Система 3

y = 0

407 x + 271 y = 4700

Решение:

407 x + 0 = 4700

x ≈ 11.5

Балл: (11.5,0)

Система 4

y = 0

407 x + 271 y = 9400

Решение:

407 x + 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 доллара США за порцию) и поскольку по цене одной порции абрикосов (3,33 доллара США за порцию) мы можем заплатить:

[латекс] \ displaystyle \ frac {{{407} {m} {g}}} {{$ {3.33}}} \ приблизительно {122.2} [/ latex] мг на доллар для абрикосов

и

[латекс] \ displaystyle \ frac {{{271} {m} {g}}} {{$ {2.00}}} \ приблизительно {135,5} [/ латекс] мг на доллар для фиников

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

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

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

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

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

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

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

Пример 3

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

Решение

Наша цель — определить процентное увеличение для административных секретарей и преподавателей, поэтому пусть

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

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

Колледж хотел бы минимизировать свои общие расходы, поэтому целевая функция должна включать общую сумму оттока денег.Поскольку для новых секретарей потребуется общий бюджет в размере
долларов США × 8 = 224000 долларов США, а для преподавателей — общий бюджет в размере 40000 долларов США × 7 = 280000 долларов США, общая стоимость будет равна проценту повышения для каждой группы, умноженному на общую зарплату:

C = 224x + 280y

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

224 x + 280 y [латекс] \ le [/ латекс] 5

Конечно, в колледже не хотят снижать зарплаты, поэтому
x [латекс] \ ge [/ latex] 0 и y [latex] \ ge [/ latex] 0.

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

Горизонтальное пересечение:

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

Пересечение по вертикали

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

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

Так как знак неравенства [латекс] \ le [/ latex], заштриховываем под линией:

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

долларов США

Точка	Стоимость
(0,0)	224 (0) + 280 (0) = 0
(0, 0,018)	224 (0) + 280 (0,018) = 5,04 доллара США
(0,020,0)	224 (0,020) + 280 (0) = 4,48 долл. США

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

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

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

a) Развернуть R = 2 x + 3 y

Согласно
–2 x — y [латекс] \ ge [/ latex] –10
x + 3y [латекс] \ ge [/ латекс] 6

x [латекс] \ ge [/ латекс] 0
y [латекс] \ ge [/ латекс] 0

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

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

В соответствии с
x + 2 y [латекс] \ ge [/ латекс] 4
x + 3 y [латекс] \ ge [/ латекс] 6

x [латекс] \ ge [/ латекс] 0
y [латекс] \ ge [/ латекс] 0

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

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

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

Свернуть: C = 0,55x + 0,23y

(1/2) x≥y или {(1/2) x-y≥0}

года ≥2000

х, 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

При условии:

х + у≥15

1100x + 1600y≤50000

x≥3

года ≥3

х, 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

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

См. Другие примеры в следующем разделе.

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

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

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

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

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

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

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

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

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

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

1. Неотрицательные ограничения: x> 0, y> 0 и т. Д.
2. Общие ограничения: x + y> 40, 2x + 9y ≥ 40 и т. Д.

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

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

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

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

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

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

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

ПРИМЕЧАНИЕ:

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

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

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

1. Corner Point
2. Метод изо-стоимости

Corner Point

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

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

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

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

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

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

• N — максимальное значение целевой функции, если открытый полуплан получен с помощью ax + by> N, не имеет общей точки с допустимой областью. В противном случае целевая функция не имеет решения.
• n — минимальное значение целевой функции, если открытый полуплан, полученный посредством ax +, по

Примеры:

Вопрос 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)

Теперь умножьте уравнение (i) на 2, а затем вычтите оба уравнения (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. Создайте такую ​​таблицу для облегчения понимания (необязательно).

	Пол (г)	Жир (г)
Торт первого вида (x)	200	25
Торт второго сорта )	100	50
Доступность	5000	1000

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

• 200x + 100y ≤ 5000 или 2x + y
• 25x + 50y ≤ 1000 или x + 2y ≤ 40
• Кроме того, x> 0 и y> 0

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

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

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

Метод изо-стоимости

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

Для решения проблемы методом изо-стоимости необходимо выполнить следующие шаги:

Шаг 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)

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

, поэтому мы берем уравнение (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)

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

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

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

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

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

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

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

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

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

Аналогично, в уравнении (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:

Как вы можете видеть на графике, в точке A пересекаются линии l2 и l3, поэтому мы находим координату точки A, решая следующие уравнения:

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

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

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

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

Теперь, для решения задач линейного программирования графически, мы должны две вещи:

1. Ограничения неравенства

2. И целевая функция.

Графический метод решения задач линейного программирования основан на четко определенном наборе логических шагов. С помощью этих шагов мы можем освоить графическое решение задач линейного программирования.

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

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

Шаг 1) Сформулируйте проблему, используя цель и ограничения.

Шаг 2) Скомпонуйте график, построив линии ограничений.

Шаг 3) На этом шаге определите допустимую сторону каждой линии ограничения.

Шаг 4) Наша следующая задача — определить возможный регион.

Шаг 5) Постройте целевую функцию, чтобы определить направление улучшения.

Шаг 6) Найдите наиболее подходящую оптимальную точку.

Шаг 7) Определите оптимальное решение алгебраически, вычислив координаты оптимальной точки.

Шаг 8) Последним шагом будет определение значения целевой функции.

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

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

Пример 1) Давайте рассмотрим производителя мебели, который производит деревянные столы и стулья. Единичная прибыль для столов составляет \ [\ $ \] 6, тогда как для стульев \ [\ $ \] 8, и единственные два ресурса, которые компания использует для производства столов и стульев, — это древесина (ножки для досок) и рабочая сила ( часы).По приблизительным оценкам, для завершения стола требуется 30 фунтов и 5 часов, а для изготовления стула — 20 фунтов и 10 часов. В распоряжении компании 300 бф древесины и 110 часов рабочего времени. Целевая функция компании — максимизация прибыли, а переменные решения — это ресурсы, которые представляют собой лес и рабочие. Набором ограничений могут быть ограничения на доступность ресурсов, которая составляет 300 баррелей древесины и 110 часов труда. Используя графические методы задачи LP, руководство может принять решение о том, как распределить ограниченные ресурсы для максимизации прибыли.

Информация о задаче линейного программирования деревянных столов и стульев

Ресурс	Стол (X₁)	03	03
	Дерево (bf)	30	20	300
Трудозатраты (час)	5	10	110
Прибыль единицы \ [\ $ \] 6 \ [\ $ \] 8

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

Шаг 1) Вышеупомянутая таблица может помочь нам сформулировать проблему. Нижняя строка будет служить целевой функцией. Целевая функция компании — максимизация удельной прибыли. Лес и рабочие — набор ограничений. Также указаны условия неотрицательности.

Максимизировать Z = \ [6x_ {2} + 8x_ {2} \] (целевая функция)

При условии: \ [30x_ {1} + 20x_ {2} \] ≤ 300 (доступно 300 бф)

\ [5x_ {1} + 10x_ {2} \] ≤ 110 (доступно 110 часов)

\ [x_ {1} + x_ {2} \] ≥ 0 (неотрицательные условия)

Две переменные ( дерево и труд) в данной задаче можно решить графически.

Шаг 2) это шаг построения графика. Используя ось X как количество столов и ось Y как количество стульев, мы можем найти две линии ограничений. Это можно найти, если мы найдем пересечения по осям x и y для двух уравнений связи. Но перед этим мы должны переписать неравенства ограничений как равенства.

Wood Labor

\ [30x_ {1} + 20x_ {2} \] = 300 \ [50x_ {1} + 10x_ {2} \] = 110

Установка x₂ = 0 для решения x₁ Установка x₂ = 0 для решить x₁

30x₁ = 300 5x₁ = 110

x₁ = \ [\ frac {300} {30} \] x₁ = 110/5

= 10 таблиц = 22 таблицы

(Дерево, из которого делали столы) (труды используется для создания таблиц)

Далее:

Установка x₁ = 0 для решения x₂ Установка x₁ = 0 для решения x₂

20x₂ = 300 10x₂ = 110

x₂ = \ [\ frac {300} {20} \] x₂ = 110/10

= 15 стульев = 11 стульев

(Дерево, из которого изготавливают стулья) (труд, используемый для изготовления стульев)

Теперь нарисуйте график линия ограничения древесины \ [(x_ {1} \] = 10 и \ [x_ {2} = 15) \] и линия ограничения рабочей силы \ [(x_ {1} = 22 \] и \ [x_ {2} = 11 ) \]

(изображение будет загружено в ближайшее время)

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

30 (0) + 20 (0) <300 - допустимая сторона линии ограничения древесины. Таким же образом 5 (0) + 10 (0) <110 также является допустимой стороной линии ограничения рабочей силы. теперь нарисуйте стрелки, указывающие допустимую сторону каждой линии ограничения.

(изображение будет загружено в ближайшее время)

Шаг 4) Определите возможную область, которая является областью на допустимой стороне обеих линий ограничения.

Шаг 5) Найдите \ [x_ {1} \] и \ [x_ {2} \], используя Z = 48 и 72.

В первом случае значения будут \ [x_ {1} \] = 8 и \ [x_ {2} \] = 12

Во втором случае значения будут \ [x_ {1} \] = 6 и \ [x_ {2} \] = 9

Постройте целевую функцию линии, когда Z = 48 и Z = 72.

Две линии целевой функции удаляются от начала координат (0,0), Z увеличивается.

(изображение скоро будет загружено)

Шаг 6) Найдите самый привлекательный уголок.

(изображение будет загружено в ближайшее время)

Шаг 7) Вычислите координаты и найдите значения x и y.

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

Шаг 8) наконец, определите значение целевой функции для оптимального решения, подставив количество столов и стульев, и решите для Z:

Z = \ [\ $ \] 6 (4) + \ [\ $ \] 8 (9) = \ [\ $ \] 96

Таким образом, производя четыре стола и девять стульев, мы можем достичь максимальной прибыли в \ [\ $ \] 96.

Графический метод решения L.P.P

Прочитав эту статью, вы узнаете о графическом методе решения L.P.P на примерах.

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

Этот метод состоит из следующих шагов:

(1) Сформулируйте задачу в терминах ряда математических ограничений и целевой функции.

(2) Постройте каждое из ограничений следующим образом:

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

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

(3) Определите возможную область [r пространство решений]:

, то есть область, которая одновременно удовлетворяет ограничениям. Для ограничений больше (>) допустимой областью будет область, которая находится над линиями ограничений.Для ограничений меньше (≤) ’эта область обычно находится под этими зубцами.

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

(4) Метод угловой точки:

Этим методом находим графическое решение.

Этот метод включает следующий этап:

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

(b) Завершите значение целевой функции в каждой угловой точке, подставив координаты точки.

(c) Определите оптимальное решение в той угловой точке, которое показывает наибольшую прибыль (в задаче максимизации) и наименьшую стоимость (в задаче минимизации).

Решение графическим методом :

Пример 1:

Решите следующую задачу LP графически.

Развернуть z = 3x ₁ + 5x ₂

С учетом ограничений x ₁ + 2x ₂ ≤ 2000

x ₁ + x ₂ ≤ 1500

x ₂ ≤ 600

x ₁ ≥ 0; х ₂ ≥ 0

Решение:

Шаг 1:

(Изобразите ограничения неравенства) Рассмотрим две взаимно перпендикулярные линии 0x ₁ и 0x ₂ как оси координат.Очевидно, что любая точка (x ₁ , x ₂ ) в положительном квадранте обязательно будет удовлетворять ограничениям неотрицательности: x ₁ ≥ 0; х ₂ ≥ 0

(a) Чтобы построить линию x ₁ + 2x ₂ = 2000

положим x ₁ = 0, тогда x ₂ = 1000

и положим x ₂ = 0, тогда x ₁ = 2000

Отметить точку L так, чтобы OL = 2000, принимая подходящие масштабы, скажем, 100 единиц = 2 см

Аналогичным образом отметьте другую точку M так, чтобы OM = 1000

Теперь соедините точки L и M.Эта линия будет представлять уравнение x ₁ + 2x ₂ = 2000, как показано на следующем рисунке.

Очевидно, что любая точка P, лежащая на линии x ₁ + 2x ₂ = 2000, будет удовлетворять неравенству x ₁ + 2x ₂ ≤ 2000 [если x ₁ = 500, x ₂ = 500, затем 500 + 2 x 500 <2000, что верно]

(b) Аналогичная процедура применяется для построения двух других линий.

x ₁ + x ₂ <1500 и x ₂ = 600, как показано на рис.(2) и рис (3) соответственно.

Любая точка на линиях x ₁ + x ₂ = 1500 и x ₂ = 600 также будет удовлетворять двум другим неравенствам.

x ₁ + x ₂ <1500 и x ₂ ≤ 600 соответственно.

Шаг 2:

Найдите допустимую область или пространство решений и объедините рис. (1), (2) и (3) вместе, получится общая заштрихованная область OABCD (см. Рис.4), который представляет собой набор точек, удовлетворяющих ограничениям-неравенствам.

x ₁ + 2x ₂ ≤ 2000; x ₁ + x ₂ ≤ 1500; х ₂ <600

и ограничение неотрицательности как x ₁ ≥ 0, x ₂ ≥ 0

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

Шаг 3:

Найдите координату угловой точки допустимой области O, A, B, C и D

Шаг 4:

Составьте следующую таблицу:

Отсюда макс.значение z = 5500, потому что максимальное значение z достигается в угловой точке B (1000,500)

Пример 2:

Решите графически следующую задачу:

Развернуть z = 8x ₁ , + 10x ₂ =

Итак, по этим условиям мы можем сказать, что решение будет в первом квадранте, поскольку оба x и y положительны.

Шаг 4:

Найдите координату угловой точки допустимой области OABC и составьте следующую таблицу:

Отсюда макс.значение z = 82

Z _макс = 82

Требуемое решение: x ₁ = 4, x ₂ = 5, поскольку максимальное значение z достигается в угловой точке B (4, 5)

Пример 3:

Развернуть z = 5x ₁ + 4x ₂

С учетом x ₁ — 2x ₂ ≤ 1

x ₁ + 2x ₂ ≥ 3

x ₁ , x ₂ ≥ 0

Решение:

Пространство решений, удовлетворяющее ограничениям

x ₁ — 2x ₂ ≤ 1

x ₁ + 2x ₂ ≥ 3 и

Неотрицательное условие x ₁ ≥ 0; x ₂ > 0 закрашено на рис. (1).Эта заштрихованная выпуклая область неограничена.

Целевая функция, Когда z = 0 дает уравнение 5x ₁ + 4x ₂ = 0, что показано пунктирной линией, проходящей через начало координат 0. При увеличении z от нуля эта пунктирная линия перемещается в точку правильно, параллельно самому себе.

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

Пример 4:

Увеличить z = 3x + 2y

при условии — 2x + 3y ≤ 9

3x -2 года ≤ -20

х, у ≥ 0

Решение:

На следующем рисунке показаны две заштрихованные области, одна из которых удовлетворяет ограничениям -2x + 3y ≤, 9, а другая — ограничениям 3x-2y ≤ -20. Эти две заштрихованные области в первом квадранте не перекрываются, в результате чего нет точки (x, y), общей для двух заштрихованных областей.Проблема не может быть решена графически или каким-либо другим способом решения проблем L.P, т.е. решения проблемы не существует.

Пример 5:

Мелкая промышленность производит электрические регуляторы, сборка которых выполняется небольшой группой квалифицированных рабочих, как мужчин, так и женщин. Из-за ограниченного пространства и финансовых возможностей, количество нанятых работников не может превышать, а их счет заработной платы — не более рупий. 60 000 в месяц.

Мужчинам-членам квалифицированных рабочих платят рупий. 6000 в месяц, в то время как работница, выполняющая ту же работу, что и мужчина, получает рупий. 5000. Собранные данные об эффективности этих работников показывают, что член-мужчина вносит 10 000 рупий в месяц в общий доход отрасли, а женщина-работник вносит 8 500 рупий в месяц. Определите, какие мужчины и женщины будут трудоустроены, чтобы максимизировать ежемесячный общий доход.

Решение:

Шаг 1:

Сформулируйте линейное программирование — Задача.

Данная задача имеет надлежащую математическую форму, так как модель LP выглядит следующим образом:

Максимум (общая ежемесячная доходность) z = 10.000x ₁ + 8500 x ₂

С учетом ограничений,

х ₁ + х ₂ ≤ 11

6000x ₁ , + 5000x ₂ ≤ 60,000 или 6x ₁ + 5x ₂ ≤ 60

x ₁ ≥ _{0; х 2 ≥ 0}

Где x ₁ = нет.трудоустроенных мужчин

x ₂ = нет. трудоустроенных женщин

Шаг 2:

Построить график:

Затем мы строим график, рисуя горизонтальную и вертикальную оси, которые представлены осью x ₁ и осью x ₂ в определенной плоскости X _x OX ₂ , поскольку любая точка, которая удовлетворяет условия x ₁ ≥0 и x ₂ ≥0 лежат только в первом квадранте, поэтому наш поиск нужной пары (x ₁ , x ₂ ) ограничен только точками первого квадранта. .

Теперь неравенства изображаются на графике, принимая их как равенства, например, первое ограничение x ₁ + x ₂ ≤ 11 будет отображено как x ₁ + x ₂ = 11, а второе ограничение 6x ₁ + 5x ₂ ≤ 60, так как 6x ₁ + 5x ₂ = 60 и третье ограничение x ₁ , x ₂ ≥ 0, просто ограничивает решение неотрицательными значениями.

Кроме того, поскольку функция, которую нужно построить, является линейной, нам нужно построить только две точки на каждое ограничение.Таким образом, для построения графика каждого ограничения мы произвольно присваиваем значение x ₁ и определяем соответствующее значение x ₂ . Затем процедура повторяется для другой пары значений для тех же ограничений, затем для первого ограничения у нас есть две такие точки A (0,11) и B (11,0), которые при объединении представляют x ₁ + x ₂ = 11.

Аналогичным образом, рассматривая набор точек, удовлетворяющих x ₁ ≥ 0, x ₂ ≥ 0 и вторым ограничениям 6x ₁ + 5x ₂ ≤ 60, мы получаем заштрихованную область на рис.

Шаг 3:

Определите возможный регион:

Возможная область, т.е. пространство решений — это область графа, которая содержит все пары значений, удовлетворяющие всем ограничениям. Другими словами, допустимая область будет ограничена двумя осями и двумя линиями x ₁ , x ₂ = 11, 6x ₁ , + 5x ₂ = 60 и будет общей областью, которая попадает в слева от этих уравнений ограничений, так как оба ограничения имеют тип, меньший, чем равный.

Шаг 4:

Найдите крайние (или угловые) точки 2

Для этого мы должны объединить Рис. (1) и (2)

Заштрихованная область OAPD представляет собой набор всех возможных решений.

Координаты крайних точек возможного района:

0 = (0,0), A = (0,11), P = (5,6), D = (10,0)

Шаг 5:

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

Значение целевой функции в каждой из этих крайних точек следующее:

Шаг 6:

Определите оптимальное значение целевой функции.Максимальное значение целевой функции z = 101000 приходится на крайнюю точку P (5,6). Следовательно, оптимальное решение данной проблемы LP: x ₁ = 5, x ₂ — 6

Макс. Z = 101000

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

Bigg Boss

Оцените это один раз.

Bigg Boss

Линейное программирование (LP) — это математический метод для определение способа достижения наилучшего результата (например, максимальной прибыли или минимальной стоимость) в данной математической модели для некоторого списка требований, представленных как линейные уравнения.

Формально линейное программирование — это метод оптимизация линейной целевой функции при условии линейного равенства и ограничения линейного неравенства. Для многогранника и действительного аффинного функция, определенная на этом многограннике, метод линейного программирования найдет точка на многограннике, где эта функция имеет наименьшее (или наибольшее) значение если такая точка существует, перебором вершин многогранника.

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

(Этот алгоритм применим только для задач с двумя переменные).

Шаг — I:

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

Шаг — II:

Рассмотрим данный неравенство. Предположим, это в форме

a1x1 + a2x2 <= b (или a1x1 + a2x2> = b). потом рассмотрим соотношение a1x1 + a2x2 = b. Найдите две различные точки (k, l), (c, d) лежащие на прямой a1x1 + a2x2 = b. Это легко найти: если x1 = 0, то x2 = b / a2.

Если x2 = 0, то x1 = b / a1. Следовательно, (k, l) = (0, b / a2) и (c, d) = (b / a1, 0) — две точки на прямой a1x1 + a2x2 = b.

Шаг — III:

Изобразите эти две точки (k, l), (c, d) на графике. который обозначает плоскость оси X – Y. Присоединяйтесь к этим две точки и продлите эту линию, чтобы получить прямую, которая представляет a1x1 + а2х2 = б.

Шаг — IV:

a1x1 + a2x2 = b делит всю плоскость на две полуплоскости: a1x1 + a2x2 <= b (одна сторона) и a1x1 + a2x2> = b (другая сторона).Найдите полуплоскость, которая связанных с данным неравенством.

Шаг — V:

Выполните шаги с II по IV для всех неравенств, указанных в проблема.

Пересечение полуплоскостей, относящихся ко всем неравенства и x1> = 0,

x2> = 0, называется допустимой областью (или допустимой пространство решений). Теперь найдите этот возможный регион.

Шаг — VI:

Возможное регион — многогранная фигура с угловыми точками A, B,

C,… (скажем).Найдите координаты для всех этих углов точки. Эти угловые точки называются крайними точками.

Шаг — VII:

Найдите значения целевая функция во всех этих угловых / крайних точках.

Шаг — VIII:

Если проблема в задача максимизации (минимизации), то максимальное (минимальное) значение z среди значений z в угловых / крайних точках допустимой области есть оптимальное значение z. Если оптимальное значение существует на углу / крайнем точку, скажем A (u, v), тогда мы говорим, что решение x1 = u и x2 = v является оптимальное возможное решение.

Шаг — IX:

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

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

Мы ранее обсуждали текстовые задачи, переведенные в математические задачи в форме линейных программ. Графический метод применим для решения LPP с двумя переменными решения x ₁ и x ₂ , однако большее количество переменных используется трудно оптимизировать с помощью графического представления.Решение представляет собой набор значений для каждой переменной:

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

Однако не все проблемы LP имеют решение. Есть еще две возможности:

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

Если возникает первая из этих проблем, необходимо ослабить одно или несколько ограничений. Если проблема неограниченна, то проблема, вероятно, не была хорошо сформулирована, поскольку немногие, если вообще есть, реальные проблемы действительно неограниченны. Графическое представление и решение проблемы LP помогает более интуитивно понять, что такое LP и как это решено.

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

Нарисуйте график квадрантов ^st : плоскость x-y, поскольку две решающие переменные x и y неотрицательны

Постройте ограничивающие линии и плоскости модели в наборе координат на плоскости.Первое неравенство ограничений делит первый квадрант на две области, скажем, ₁ рандов и ₂ рандов, предположим, что (x ₁ , 0) — это точка в ₁ рандов. Если эта точка удовлетворяет уравнению ax + на ≤ c или (≥ c), заштрихуйте область R ₁ . Если точка (x ₁ , 0) не удовлетворяет неравенству, заштрихуйте область R ₂ .

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

Постройте целевую функцию, чтобы найти точку на границе этого пространства, которая максимизирует (или минимизирует) значение целевой функции

Вычислите оптимальное решение, найдя угловую точку.

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

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

Рассмотрим задачу минимизации:

Свернуть Z = 6 x ₁ + 3 x ₂

при условии

2 x ₁ + 4 x ₂ 16 фунтов азота

4 x ₁ + 3 x ₂ 24 фунта фосфата

x ₁ , x ₂ 0

Линейное программирование: пример графического метода

Пример (часть 2): Графический метод

Решите графическим методом следующую задачу:

Развернуть	Z = f (x, y) = 3x + 2y
при условии:	2x + y ≤ 18
	2x + 3y ≤ 42
	3x + y ≤ 24
	х ≥ 0, у ≥ 0

1. Сначала рисуется система координат, и каждая переменная связана с осью (обычно «x» связан с горизонтальной осью, а «y» — с вертикальной), как показано на рисунке 1.
2. На оси нанесена числовая шкала, соответствующая значениям, которые переменные могут принимать в соответствии с ограничениями задачи. Для этого для каждой переменной, соответствующей оси, все переменные устанавливаются в ноль, кроме переменной, связанной с исследуемой осью в каждом ограничении.
3. Следующий шаг представляет ограничения. Начиная с первого, проводится линия, полученная при рассмотрении ограничения как равенства. В примере эта линия представляет собой сегмент, соединяющий точки A и B, а область, ограничивающая это ограничение, обозначена ЖЕЛТЫМ цветом.Этот процесс повторяется с другими ограничениями, СИНИЙ и КРАСНЫЙ области соответствуют второму и третьему ограничению соответственно.
4. Возможная область — это пересечение областей, определенных набором ограничений и координатной осью (условия неотрицательности переменных). Эта возможная область представлена ​​многоугольником O-F-H-G-C ПУРПУРНОГО цвета.
   
5. Поскольку существует допустимая область, вычисляются экстремальные значения (или вершины многоугольника).Эти вершины являются точками-кандидатами в качестве оптимальных решений. В примере это точки O, F, H, G и C, как показано на рисунке.
6. Наконец, целевая функция (3x + 2y) оценивается в каждой из этих точек (результаты показаны в таблице ниже). Поскольку G-точка обеспечивает наибольшее значение Z-функции, а цель — максимизировать, эта точка является оптимальным решением: Z = 33 с x = 3 и y = 12.

Крайняя точка	Координаты (x, y)	Объективное значение (Z)
O	(0,0)	0
С	(0,14)	28
G	(3,12)	33
H	(6,6)	30
Ф.	(8,0)	24

Сравнение графического и симплексного методов

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

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

Таблица I. 1-я итерация.
			3	2	0	0	0
База	Cb	P0	П1	P2	П3	П4	П5
P3	0	18	2	1	1	0	0
P4	0	42	2	3	0	1	0
P5	0	24	3	1	0	0	1
Z		0	-3	-2	0	0	0

Входная базовая переменная в симплексном методе определяет, в сторону какой новой вершины выполняется смещение.В этом примере, когда входит P1 (соответствующий ‘x’), смещение выполняется OF-ребром, чтобы достичь F-вершины, где вычисляется значение Z-функции. Этот шаг происходит во второй итерации симплекс-метода, как показано в таблице II. В нем вычисляется соответствующее значение F-вершине, а Z = 24 — это полученное значение для функции.

Таблица II. 2-я итерация.
			3	2	0	0	0
База	Cb	P0	П1	P2	П3	П4	П5
P3	0	2	0	1/3	1	0	-2/3
P4	0	26	0	7/3	0	1	-2/3
Л1	3	8	1	1/3	0	0	1/3
Z		24	0	–1	0	0	1

Произведено новое смещение FH-ребром до H-вершины (данные в Таблице III).На третьей итерации значение функции в H-вершине вычисляется, чтобы получить Z = 30.

Таблица III. 3-я итерация.
			3	2	0	0	0
База	Cb	P0	П1	P2	П3	П4	П5
P2	2	6	0	1	3	0	-2
P4	0	12	0	0	-7	1	4
Л1	3	6	1	0	–1	0	1
Z		30	0	0	3	0	–1

Процесс идет от HG-ребра до G-вершины, полученные данные представлены в таблице IV.На этом процесс заканчивается, когда можно проверить, не улучшает ли решение, продвигаясь по GC-ребру до C-вершины (текущее значение Z-функции не увеличивается).

Таблица IV. 4-я итерация.
			3	2	0	0	0
База	Cb	P0	П1	P2	П3	П4	П5
P2	2	12	0	1	-1/2	1/2	0
P5	0	3	0	0	-7/4	1/4	1
Л1	3	3	1	0	3/4	-1/4	0
Z		33	0	0	5/4	1/4	0

Максимальное значение целевой функции составляет 33, и оно соответствует значениям x = 3 и y = 12 (координаты G-вершины).

No related posts.