Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Геометрия задач ЛП




Геометрические построения возможны для размерности пространства задачи k £ 3. Рассмотрим задачи на плоскости (k= 2):

Исходная модель L=7x1+5x2→max, 1) 2x1+3x2£19, 2) 2x1+x2£13, 3) 3x2£12, 4) 3x1£17, 5) x1³0, 6) x2³0. Каноническая модель L=7x1+5x2→max, 2x1+3x2+x3=19, 2x1+x2+ x4=13, 3x2+x5=12, 3x1+x6=17, "xj³0.  

Надо сначала построить допустимое множество, а затем по целевой функции найти на нем точку или множество с максимальным значением критерия. Допустимое множество задачи находится как пересечение допустимых множеств, построенных по отдельным условиям задачи. Построение множества начинается с определения его границы (условия неотриц-ти). Допустимое множество задачи ЛП всегда лежит в первом квадранте. Теперь перейдем к построению допустимых множеств по функциональным условиям. Записываем уравнения границ и проводим соответствующие прямые. Находя пересечение шести построенных допустимых множеств, получаем выпуклый шестиугольник – частный случай выпуклого многогранника.

Из бесконечного множества допустимых решений, принад­лежащих этому многоугольнику, необходимо найти то, которое дает максимум критерия. Построим линии уровня критерия L=Const.. Так как критерий линейный, то линии уровня – это множество параллельных прямых с постоянным градиентом (направлением возрастания значений критерия). Поэтому для определения этого направления достаточно иметь 2 линии уровня.

L*
Критерий увеличивается в направлении, показанном стрелкой. Чтобы найти оптимальное решение, не нужно строить новые линии уровня. Предельное положение критерия соответствует прохождению линии уровня через точку С (максимальное значение). Координаты точки С – оптимальные значения переменных, можно найти как решение системы 2-х уравнений границ, образующих эту точку: 2 x*1+3 x*2=19, 2 x*1+ x*2=13.

Отсюда: х*1=5, х*2=3. Значения остальных переменных вычисляются однозначно из канонической модели после подстановки в ее уравнения х*1и х*2. В результате оптимальное решение задачи: х*1=5, х*2=3, х*3=х*4 =0, х*5 =3, х*6 =2 и , L*= 50.

Таким образом, чтобы добиться максимальной прибыли в 50 единиц, необходимо производить 5 изделий первого типа и 3 изделия второго типа. При этом будут полностью использованы ресусы 1-го и 2 -го вида (х*3=х*4=0), а по ресурсам 3-го и 4-го вида образуются остатки в количестве 3 и 2 соответственно (х*5=3, х*6=2). Задача имеет единственное оптимальное решение, так как линия уровня L= 50 соприкасается с допустимым множеством только в одной точке.

При данном допустимом множестве задача всегда будет иметь решение независимо от коэффициентов целевой функции, потому что в любом случае будет существовать предельное положение линии уровня критерия. Однако оптимальное решение может быть и не единственным. Пример: L1=4x1+6x2max.

Так как условия не изменились, то допустимое множество остается прежним. Если повторить построение линий уровня, то они будут параллельны стороне BC. Поэтому в предельном положении линия уровня критерия совпадает с границей по 1-му ограничению; Мн-во (бесконечное) оптимальных решений, лежащее на стороне BC, каждому из которых соответствует одно и то же максимальное значение критерия L1.

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

а) Значение критерия L1 улучшается в направлении неограничености множества и, критерий неограничен на допустимом множестве, он может улучшаться до ∞ – допустимые решения есть, а оптимального нет.

б) Улучшение критерия L2 ограничено на допустимом множестве, решение существует.

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

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







Дата добавления: 2015-04-19; просмотров: 390. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.002 сек.) русская версия | украинская версия