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) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

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

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

 

Новости

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

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

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

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

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

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

Купить и обменять Litecoin
19 сентября 2017 года, Чарли Ли, создатель Litecoin, и Alexlyp, из проекта Decred, смогли обменять 1, 337 LTC на 2, 4066 DCR. И хотя поначалу они сталкивались с трудностями, им удалось завершить своп

Производство и оптовая продажа кожаных
Самый простой состав мыла: животный жир (привет, защитникам животных! ) и щелочь (зола) – таким мылом пользовались наши предки.   За сотни лет состав мыла претерпел значительные изменения.

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

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

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

Свежее


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


rss