21819

Условная оптимизация

Лекция

Менеджмент, консалтинг и предпринимательство

Пример постановки задачи оптимизации Линейное программирование ЛП Постановка задачи линейного программирования Основные определения и теоремы Переход от одной формы задачи ЛП к другой 3. Пример постановки задачи оптимизации Для изготовления 3х видов изделий А В и С используется токарное фрезерное сварочное и шлифовальное оборудование. Составить математическую модель задачи. Постановка задачи линейного программирования Найти оптимум наибольшее или наименьшее значение целевой функции линейной формы на области допустимых значений...

Русский

2013-08-03

169 KB

31 чел.

Тема 5. Лекция 5.

условная оптимизация.

Линейное программирование.

  1.  Пример постановки задачи оптимизации
  2.  Линейное программирование (ЛП)
    1.  Постановка задачи линейного программирования
    2.  Основные определения и теоремы
    3.  Переход от одной формы задачи ЛП к другой

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

1. Пример постановки задачи оптимизации

Для изготовления 3-х видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия приведены в таблице.

Тип оборудования

Затраты времени (станко-ч.) на обработку одного изделия вида

Общий фонд рабочего времени

А

В

С

Фрезерное

2

4

5

120

Токарное

1

8

6

280

Сварочное

7

4

5

240

Шлифовальное

4

6

7

360

Прибыль

10

14

12

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

Решение.

Пусть будет изготовлено Х1 единиц изделия А

      Х2 единиц изделия В

      Х3 единиц изделия С.

Тогда при использовании фрезерного оборудования потребуется затратить 2Х1 + 4Х2 + 5Х3 станко-часов.

Но по условию ограничения общего фонда времени

1 + 4Х2 + 5Х3  120.

Аналогично для токарного, сварочного и шлифовального оборудования:

Х1 + 8Х2 + 6Х3  280

1 + 4Х2 + 5Х3  240

1 + 6Х2 + 7Х3  360

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

Х1  0, Х2  0, Х3  0.

Далее, если будет изготовлено Х1 изделий А, Х2 изделий В и Х3 изделий С, то прибыль от их реализации составит

F = 10Х1 + 14Х2 + 12Х3

Итак, мы получаем систему четырех линейных неравенств с тремя неизвестными (Xj (j = 1…3):

1 + 4Х2 + 5Х3  120

Х1 + 8Х2 + 6Х3  280

1 + 6Х2 + 7Х3  360

Х1  0, Х2  0, Х3  0.

и линейную функцию F = 10Х1 + 14Х2 + 12Х3 относительно этих же переменных.

Требуется среди всех неотрицательных решений системы неравенств найти такое, при котором целевая функция F принимает максимальное значение.

2. Линейное программирование

2.1. Постановка задачи линейного программирования

Найти оптимум (наибольшее или наименьшее значение) целевой функции (линейной формы)

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

 

при наличии дополнительных условий неотрицательности переменных

хj  0, j = 1,…, n.

Если в системе ограничений l = m, т.е. она состоит только из уравнений, то соответствующая форма записи называется канонической.

2.2. основные определения и теоремы

2.2.1. Определения

  1.  Функция F(X) (1) называется целевой функцией, или линейной формой задачи, а условия (2) – (4) – ограничениями данной задачи.
  2.  Стандартной (или симметричной) задачей ЛП является задача, которая состоит в определении максимального значения функции F(X) при выполнении условий (3), (4).
  3.  Канонической или основной задачей ЛП называется задача, которая состоит в определении максимального значения функции F при выполнении условий (2), (4).
  4.  Совокупность чисел Х(х1 х2,…хn), удовлетворяющая ограничениям задачи (1) – (4) называется допустимым решением, или планом.
  5.  План Х*(х*1 х*2,…х*n), при котором целевая функция задачи принимает максимальное значение, называется оптимальным.

Свойства основной задачи ЛП тесно связаны со свойствами так называемых выпуклых множеств.

Рассмотрим (без доказательства) отражающие свойства основной задачи ЛП, теоремы, предварительно записав ряд определений.

Определение 1. Пусть х1 х2,…хn – произвольные точки евклидова пространства. Выпуклой линейной комбинацией этих точек называется сумма

1х1 + 2 х2 +... n  хn,

где - произвольные неотрицательные числа, сумма которых равна 1.

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

Определение 3. Непустое  множество планов основной задачи ЛП называется многогранником решений, а всякая угловая точка многогранника – вершиной.

Совокупность вершин многогранников решений называется опорным планом.

2.2.2. Теоремы

Теперь сформулируем теоремы о свойствах основной задачи ЛП.

Теорема 1.

Множество планов  основной задачи ЛП является выпуклым (если оно непусто).

Теорема 2.

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

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

2.3.Переход от одной формы задачи ЛП к другой

Как уже было сказано выше, существуют стандартная форма задачи линейного программирования и каноническая форма. В любом случае ищется экстремум целевой функции, т.е. либо максимум, либо минимум. Таким образом, можно выделить задачи на максимум и задачи на минимум. Существуют правила перехода от одной формы задачи ЛП к другой, т.е. переход от задачи на поиск максимума целевой функции к задаче поиска минимума целевой функции целевой функции (Fmax Fmin), а также переход от стандартной задачи ЛП к канонической и наоборот (стандартная каноническая). Рассмотрим эти правила.

2.3.1. Сведение задачи минимизации к задаче максимизации:

F = c1x1 + c2x2 + … cnxn  min  сводится к

F = -F = - c1x1 - c2x2 - … cnxn  max;

2.3.2. Переход от стандартной задачи к канонической.

Ограничение – неравенство () исходной задачи можно преобразовать в ограничение – равенство добавлением к его левой части дополнительной неотрицательной переменной, т.е.

i1х1 + i2 х2 + i3x3 + … in  хn  () bi преобразуется в

i1х1 + i2 х2 + i3x3 +  in хn + xn+1 = bi

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений – неравенств в ограничение – равенства равно числу преобразуемых неравенств.

2.3.3.  Переход от канонической задачи к стандартной:

i1х1 + i2 х2 + in хn  = bi

можно записать в виде неравенств

i1х1 + i2 х2 + … in хn   bi

 i1х1  i2 х2 in хn    bi

3. Методы решения задач нелинейного программирования.

   Геометрическая интерпретация

 

3.1. Геометрический способ

3.1.1. Пример геометрической интерпретации задачи ЛП

3.1.2. Этапы решения задачи

Существуют два основных метода решения задачи линейного программирования: решение на основе геометрической интерпретации (геометрический способ) и так называемый симплекс-метод.

3.1. Геометрический способ.

Геометрический способ может быть применен только для двумерных задач, т.е. при n = 2. В этом случае область допустимых значений – выпуклый многоугольник на плоскости (х1 , х2 ), являющийся результатом пересечения полуплоскостей, каждая из которых – решение соответствующего неравенства системы ограничений.

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

Таким образом,  решением задачи будет та угловая точка ОДР, которая является крайней в направлении линии уровня.

Непустое множество задачи ЛП образует выпуклый многогранник. Каждая вершина многогранника представляет собой опорный план. В одной из вершин многоугольника (т.е. для одного из опорных планов значения целевой функции является максимальным (при условии, что функция ограничивает сверху на множестве планов.

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

Нахождение минимального значения F отличается от нахождения максимального ее значения при тех же ограничениях лишь тем, что ЛУ передвигается не в направлении С, а в противоположном.

Отметим свойства целевой функции и ограничений

  1.  Целевую функцию можно умножать на любую положительную const.
  2.  К целевой функции можно добавлять любую const.
  3.  С ограничениями можно как с системой равенств или неравенств проводить эквивалентные алгебраические преобразования.

Пример: Найти решение задачи ЛП при следующих данных:

F = 2X1+ 3X2 ® max          при

4X1+ 3X2  12                       (1)

 X1 -    X2  1   (2)

- X1 + 6X2  12   (3)

X1, X2  0    (4)

Область допустимых решений задачи (ОДР), или множество планов задачи представляет собой многоугольник, ограниченный прямыми – геометрическим выражением уравнений, преобразованных из неравенств (1)-(3). Поочередно приравнивая в уравнениях (1)-(3) Х1  и  Х2  к нулю, а также используя условие (4), строим прямые, определяем полуплоскости, соответствующие каждому ограничению задачи и получаем многоугольник ABCD (см. рис.1). Каждая вершина многоугольника представляет собой опорный план.

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

В одной из вершин многоугольника (т.е. в одном из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов).  Пункты 1-3 выполнены. Строим направляющий вектор. Начало его совпадает с началом координат, а конец имеет координаты (С1; С2), соответствующие коэффициентам в целевой функции. В нашем случае (2; 3).

Рис. 1

Вектор (2; 3) показывает направление роста целевой функции.  Для определения вершины многоугольника построим линию уровня F =2X1+ 3X2 = h, проходящую через многоугольник решений. Вначале положим h = 6. Нетрудно видеть, что линия уровня перпендикулярна направляющему вектору. Задав новое значение h , больше предыдущего, мы передвигаем линию уровня по направлению вектора . Точка, в которой линия уровня покидает ОДР ( в нашем случае это точка С) и будет решением задачи, т.е. оптимальным планом. Однако, определив точку на чертеже, необходимо определить точное значение ее координат, т.е. переменных X1 и  X2. Поскольку точка С находится на пересечении прямых, соответствующих уравнениям (1) и (3), решая совместно эти уравнения, получим значения X1 = 1,33 и  X2 = 2,22.

Решение записывается в виде X(1,33; 2,22).

Подставив найденные значения переменных в выражение для целевой функции, вычисляем ее максимальное значение: F = 9,33.

3.1.2. Этапы решения задачи ЛП на основе ее геометрической

         интерпретации

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

  1.  строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств;
    1.  находят полуплоскости, определяемые каждым из ограничений задачи;
    2.  находят многоугольник решений;
    3.  строят вектор С = (С1, С2);
    4.  строят прямую С1Х1 + С2Х2 = h, проходящую через многоугольник решений;
    5.  передвигают прямую С1Х1 + С2Х2 = h в направлении вектора С, в результате чего находят либо точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов;

определяют координаты точки максимума функции и вычисляют  значение целевой функции в этой точке.

Возможные случаи нахождения решения геометрической интерпретации ЛП

  1.  Целевая функция не ограничена сверху на множестве допустимых решений;
  2.  Случай, когда система ограничений несовместна.


 

А также другие работы, которые могут Вас заинтересовать

74519. ТЕХНІЧНА ПІДГОТОВКА СПОРТСМЕНІВ 126 KB
  Характеристика спортивної техніки. Основні методики вдосконалення техніки спортсменів високої кваліфікації. На розвиток спортивної техніки особливий вплив зробили результати наукових досліджень в області управління рухами технічної підготовки спортсменів що спеціалізуються в різних видах спорту. Котикової було представлено біомеханічне обґрунтування техніки найбільш раціонального положення тіла стрибуна у висоту у момент переходу через планку.
74520. ТАКТИЧНА ПІДГОТОВКА СПОРТСМЕНІВ 128 KB
  Мета завдання та зміст тактичної підготовки. Методика тактичної підготовки спортсменів. Контроль тактичної підготовки спортсменів. Спортивна тактика тактична підготовленість і напрями тактичної підготовки Під спортивною тактикою слід розуміти способи обєднання і реалізації рухових дій що забезпечують ефективну діяльність змагання що приводить до досягнення поставленої мети в конкретному старті серії стартів змаганні.
74521. Конституционно-правовой статус личности 40.65 KB
  Защита Отечества является долгом и обязанностью гражданина Российской Федерации. Гражданин Российской Федерации в случае если его убеждениям или вероисповеданию противоречит несение военной службы а также в иных установленных федеральным законом случаях имеет право на замену ее альтернативной гражданской службой...
74522. Федеративное устройство 58.89 KB
  Принципы национально-государственного устройства в РФ Добровольность объединения наций и народностей Равноправие наций Федерализм в сочетании с унитаризмом и автономией Национально-территориальный принцип в сочетании с территориальным принципом Государственная целостность РФ Равноправие субъектов РФ Разграничение полномочий РФ и субъектов РФ
74523. Конституционная система органов государственной власти в РФ 23.26 KB
  Признаки государственного органа Часть государственного аппарата Образуется в установленном порядке Наделен властными полномочиями Реализует функции государственного управления в пределах своей компетенции Бюджетное финансирование Наличие ресурсов
74524. Федеральное Собрание РФ 30.26 KB
  1994 N 3ФЗ О статусе члена Совета Федерации и статусе депутата Государственной Думы Федерального Собрания Российской Федерации Федеральный закон от 18.2005 N 51ФЗ О выборах депутатов Государственной Думы Федерального Собрания Российской Федерации Федеральный закон от 03.1998 N 137ФЗ О материальном обеспечении членов семьи умершего члена Совета Федерации или депутата Государственной Думы Федерального Собрания Российской Федерации Социальные гарантии депутатам ГД членам СФ По объему социальных гарантий они приравниваются к федеральному...
74525. Правительство РФ 20.9 KB
  Взаимодействие с законодательной судебной властью Президент назначает и смещает Председателя и членов Правительства РФ федеральных министров Президент РФ вправе председательствовать на заседаниях Правительства РФ Перед вновь избранным Президентом Российской РФ Российской Федерации слагает свои полномочия...
74526. Конституционное право как отрасль российского права. Виды, принципы и свойства Конституции РФ 30.63 KB
  Виды принципы и свойства Конституции РФ Отличия отраслей права.Основы конституционного строя России суверенитет народа разделение власти верховенство Конституции. Отношения основанные на системе запретов прямой запрет определенных действий Задание Найдите примеры норм Конституции которые основаны на указанных выше методах
74527. Суверенитет народа и формы его осуществления 35.9 KB
  Запрет принуждения ко вступлению в общественные объединения и пребыванию в них. Запрет создания и деятельности общественных объединений направленных на изменение конституционного строя нарушение целостности РФ подрыв безопасности государства создание вооруженных формирований разжигание расовой социальной национальной религиозной вражды ФЗ РФ Об общественных объединениях. Признаки общественного объединения формирование граждан добровольное самоуправляемое некоммерческое общность интересов общность целей цели закреплены в...