Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


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

 

Задачи линейного программирования с двумя переменными может решаться группами. Однако еще в трехмерном пространстве такое решение усложняется.

 

1)область допустимых решений – выпуклый многоугольник

2)неограниченная выпуклая область многоугольная

3)одна точка

4)линия

5)луч

6)решение на отрезке

7)пустое множество

 

Пусть область допустимых решений не пустое множество , например, некий многоугольник. Выберем произвольное значение функции Z=Z0 следовательно Z0=c1x1+c2x2.

В точках N и M целевая функция сохранит постоянное значение Z. Считая Z параметром , получим уравнение семейства параллельных прямых, называемых линиями уравнения целевой функции(линиями постоянного значения).Когда направление уменьшается или увеличивается, то целевая функция находится с помощью частных производных. Частные производные показывают скорость увеличения функции вдоль заданной оси следовательно,c1 и c2 скорость увеличения функции Z вдоль Ox1 и Ox2. c – это вектор, вектор градиент показывает направление наискорейшего увеличения целевой функции.

Порядок графического решения задач:

1)с учетом системы ограничений строится область допустимых значений.

2)строим вектор с

3)проводим произвольную линию уровню Z=Z0

4)при решении задач на max перемещая линию уровня Z=Z0 в направлении вектора с так, чтобы она касалась области дополнительных решений в ее крайнем положении (А4 – максимальное значение). при решении на min –в антиградиентном направлении.(А1).

5)оптимальный план х* и экстремальное значение целевой функции Zx*, где х*это набор значений.

 

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

Б) бесконечное множество

В) Z стремится к бесконечности

Г) точка,Z как max так и min

Д) пустое множество



 

 

Пример задачи: цех выпускает 2 вида продукции, используя 2 вида полуфабрикат. Продукция используется при комплектовании изделий, при этом на каждую единицу продукции первого вида требуется не более двух единиц продукции второго вида. Нормой расхода полуфабриката каждого вида на единицу продукции, общий объем полуфабрикатов и прибыль от единицы каждой продукции представлены в таблице:

полуфабрикаты П1 П2 Объем полуфабрикат
I
II
прибыль  

Нужно найти оптимальный план max прибыли.

 

Max Z=10x1+35x2

X1+2x2<=800

6x1+2x2<=2400

X1=>0

X2=>0

2x1=>x2

 

Решение:

X1+2x2=800

6x1+2x2=2400

X1=0

X2=0

2x1=x2

 

 

 

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

Теорема: множество планов задач линейного программирования выпукло.

 

Графическим методом можно решить задачу линейного программирования с количеством n- переменных больше двух, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n-m<=2, в этом случае каноническую форму задачи преобразуем в симметричную ,которая будет содержать не более 2 переменных. Решаем задачу графически, находим 2 компонента оптимального плана , подставляя их в ограничение задачи, определяем остальные компоненты.

Пример: Двум погрузчикам разной мощности за 24часа нужно погрузить на первой площадке=230 тонн, на второй=168тонн. Первый погрузчик на первой площадке может погрузить 10тонн в час, на второй 12тонн в час. Второй погрузчик на каждой площадке по 13 тонн в час. Стоимость работ, связанных с погрузкой 1тонна первым погрузчиком на первой площадке 8 условных единиц. На второй площадке 7 условных единиц. Вторым погрузчиком на первой площадке 12 условных единиц, на второй площадке 13 условных единиц.

Решение: Необходимо составить план работы, т.е. найти какой объем работ должен выполнять каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной. Причем по техническим причинам первый погрузчик на второй площадке должен работать не более 16 часов.

 

  П1 П2 t
Iпогрузчик
IIпогрузчик
задание  

Min Z=8x11+7x12+12x21+13x22

X11+x21=230

X12+x22=168

 

X11 X12 x21 x22 >0

X21=230 – x11

X22=168 - x12

 

Min Z=8x11+7x12+12(230 – x11)+13(168 - x12)= 8x11+7x12+2760-12x11+2184-13x12=4944-x11-6x12

 

6x11+5x12<=1440

X11+x12=>86

398-x11 - x12 <=312

-x 11-x12<=86

X11+x12=>86

X11<=230

X12<=168

Min Z=4944-(9x11+6x21)

6x11+5x12=1440

X11=240-

X12=86- x11

X11=100

X12=168

X21=130

X22=0

Min Z=400+1008=1408

X11=4944-1408=3536

 

<== предыдущая лекция | следующая лекция ==>
Матричная и векторная формы | Понятие двойственности для симметричных задач линейного программирования

Дата добавления: 2014-01-07; Просмотров: 1488; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


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

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.008 сек.