rfba — аналитика, бизнес, страхование, рынок forex
   
   
 
? ?
 

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

Опубликовано: 20.08.2017

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

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

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


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

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

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

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

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

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

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

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

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

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

Банки и банковские услуги .

Вы можете перейти в конец и оставить комментарий. Уведомления сейчас отключены.

 

Новости

Тур Пешком по Украине

Кто из нас не мечтает о хорошем отдыхе после тяжелого трудового года? Да конечно же все) Однако все отдыхают по разному - в зависимости от своих предпочтений и финансовых возможностей. Кто-то предпочитает

Как купить на Алиэкспресс
Многие из нас пользуется услугами Алиэкспресс, покупаем и заказываем различные товары. Но вот нам попался интересный сайт https://alimpopo.ru/ под названием 'Алимпопо', где даются обзоры и отзывы на

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

Доступный кредит: не всё так просто
Да уж, сейчас в Интернете просто-таки огромное количество разнообразных компаний и фирмочек, которых, как говорится, хлебом не корми (хотя делает они всё это как раз-таки исключительно для собственного

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

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

Инвестируем деньги в строительство
Если говорить о вливании денег со стороны обычных граждан, то строительная отрасль является рискованным сектором для инвестиций. Ведь тут нужно знать все тонкости оборота денежных средств. А в данном

Как проверить штрафы ГИБДД
Ресурсов, предоставляющих различные услуги в сети, в том числе и государственные, существует достаточно много. Одним из самых востребованных сервисов подобного рода является онлайн-проверка штрафов

Где заказать расчетно - кассовое обслуживание
Нашла прекрасный сайт Тинькофф, где предоставляют услуги рассчетно-кассового обслуживания. Познакомилась я с этим сайтом месяц назад, https://www.tinkoff.ru/rko/search/form/uslugi-raschetno-kassovogo-obsluzhivanija/.

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

Свежее


Случайные записи


rss