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

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

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

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

Графический метод

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



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


Лекция 2: Задача линейного программирования. Задача о ресурсах

Графический метод решения задачи (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