Конспект лекций по предмету "Линейное программирование"

Узнать цену работы по вашей теме


ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Вспомним построение линейных зависимостей. Начнём с уравнений.
Линейное уравнение с двумя переменными может быть записано a1x1+a2x2 =b. Чтобы построить это уравнение, найдём точки пересечения с осями координат. При х1 = 0 получаем a2x2 =b, откуда х2 = b/a2. При х2 = 0 получаем a1x1 =b, откуда х1 = b/a1 (рис.2.2).
Разделим теперь левую и правую части уравнения на b и перепишем уравнение , или , или , которое называют уравнением прямой в отрезках. Такое представление уравнения удобно для построения прямой, так как величины a1 и a2 – это отрезки, отсекаемые прямой на тех осях, которые указаны в числителе. Например, 2х1+х2=2 или в форме уравнения в отрезках: , т.е. a1 =1, a2 =2 (рис.2.3).
Теперь вспомним неравенства. Если линейное уравнение с двумя переменных 2х1+х2=2 может быть представлено прямой на плоскости, то неравенство a1x1+ +a2x2 £ b изображается как полуплоскость.
Так неравенство 2х1+х2£ 2 представляет собой заштрихованную полуплоскость, координаты всех точек которой, т.е. х1 и х2 удовлетворяют заданному равенству. Значит, эти значения составляют область допустимых решений (ОДР).
Рассмотрим построение системы линейных неравенств:

или в форме, аналогичной уравнениям в отрезках:

Построим каждое неравенство в системе координат х1б х2 в виде соответствующих полуплоскостей (рис.2.4).
Решение этой системы неравенств – координаты всех точек, принадлежащих ОДР, т.е. АВСДО. Так как в ОДР бесчисленное множество точек, значит рассматриваемая задача имеет бесчисленное множество допустимых решений.
Не любая система линейных неравенств имеет ОДР, т.е. допустимые решения.
Например, построим системы (рис.2.5):

Из рис.2.5 видно, что нет таких точек, которые бы удовлетворяли всем неравенствам системы.
До сих пор рассматривали линейные уравнения и неравенства с двумя переменными. Если перейти к линейным зависимостям с тремя переменными, то тогда они будут описывать плоскость в трёхмерном пространстве; линейное неравенство характеризует полупространства, а система линейных неравенств – многогранник как ОДР в трёхмерном пространстве.
С увеличением числа переменных выше трёх, геометрическая интерпретация невозможна, но система неравенств – ОДР в k-мерном пространстве.
При этом мерность пространства определяют как: если ограничения заданы неравенствами, то k = п, где п – число переменных; если ограничения в виде уравнений, то k = n–т, где т – число уравнений.
Если мы хотим найти оптимальное решение, то должны принять ЦФ. Допустим, мы хотим, чтобы решение было оптимальным в смысле максимизации выпуска в целом. Тогда ЦФ: max L = x1+x2.
Положим L равной какому-либо числу (любому), например 2, и построим уравнение ЦФ: .
Так как нам требуется найти оптимальное решение, при котором достигается maxL, будем перемещать линию ЦФ в направлении увеличения L. Очевидно, что оптимальным решением будут координаты точки С, равные . При этом L = L*.
Отсюда можно сделать исключительно важный вывод: оптимальное решение – координаты вершины ОДР.
Из этого вывода следует метод решения задач ЛП, который заключается в следующем.
1. Найти вершины ОДР как точки пересечения ограничений.
2. Определить последовательно значения ЦФ в вершинах.
3. Вершина, в которой ЦФ приобретает оптимальное (max или min) значение, является оптимальной вершиной.
4. Координаты оптимальной вершины есть оптимальные значения искомых переменных.


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

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации