21819

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

Лекция

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

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

Русский

2013-08-03

169 KB

29 чел.

Тема 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.  Случай, когда система ограничений несовместна.


 

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

68208. ТЕХНОЛОГІЯ СОУСІВ ЯГІДНИХ З ВИКОРИСТАННЯМ ПРИРОДНОЇ НЕТРАДИЦІЙНОЇ СИРОВИНИ 975.5 KB
  Слід підкреслити що останнім часом все більшого розповсюдження у ресторанному господарстві набуває креативна кухня яка характеризується додаванням до страв з м’яса риби птиці дичини солодких соусів з плодів та ягід асортимент яких обмежується вишневим чорносмородиновим сливовим соусами...
68209. ФОРМУВАННЯ ГОТОВНОСТІ МАЙБУТНЬОГО ВЧИТЕЛЯ ПОЧАТКОВИХ КЛАСІВ ДО ПЕДАГОГІЧНОГО МОДЕЛЮВАННЯ 290 KB
  Нові: знання методів моделювання та застосування моделей зокрема до процесів об’єктів і суб’єктів навчання і виховання; уміння визначати доцільність застосування методів педагогічного моделювання до розв’язування педагогічних задач; здатність до освоєння сучасних в тому числі заснованих на застосуванні...
68210. СЕРЕДНЬОШРИФТОВЕ ЧЕТВЕРОЄВАНГЕЛІЄ: ЛІНГВІСТИЧНИЙ І ПАЛЕОГРАФІЧНИЙ АНАЛІЗ 176.5 KB
  Досягнення цієї мети передбачає виконання таких завдань: проаналізувати безвихідні дофедорівські книговидання в контексті проблеми дофедорівського книгодрукування на східнослов’янських землях; окреслити місце середньошрифтового Євангелія серед безвихідних видань...
68211. Оптимізація діагностики і лікування хронічного біліарного панкреатиту у хворих з ожирінням 196 KB
  Мета дослідження: підвищити якість діагностики і ефективність лікування біліарного ХП у хворих із ожирінням. Для досягнення цієї мети були поставлені наступні завдання: Проаналізувати клінічні прояви біліарного ХП у хворих із ожирінням.
68212. ЕКСПОРТНИЙ ПОТЕНЦІАЛ ПІДПРИЄМСТВ ЛІСОПРОМИСЛОВОГО КОМПЛЕКСУ 662 KB
  Розвиток світового господарства у теперішній час вирізняється посиленням глобалізаційних процесів, які зумовили трансформацію моделей міжнародного співробітництва, зміну структури об’єктів і суб’єктів світового ринку
68213. ДЕРЖАВНА ПОЛІТИКА РОЗВИТКУ ІННОВАЦІЙНОГО ПОТЕНЦІАЛУ РЕГІОНІВ УКРАЇНИ 324.5 KB
  Курс на інноваційний розвиток в Україні визначає перехід економіки до нового якісного рівня. Він супроводжується активізацією інноваційної діяльності, яка сприяє реорганізації економіки на основі розвитку наукоємних виробництв, запровадження у виробництво прогресивних...
68214. СОЦІАЛЬНИЙ КАПІТАЛ ЯК ЧИННИК ПРОФЕСІЙНОЇ СОЦІАЛІЗАЦІЇ ПРАВООХОРОНЦІВ 225 KB
  Проте на жаль потенціал соціального капіталу в її реалізації практично не використовується. Тому в даній дисертації вперше пропонується комплексно розглянути феномен соціального капіталу правоохоронців та визначити можливості його використання для оптимізації процесу їх професійної соціалізації.
68215. СУЛЬФАТРЕДУКУЮЧІ, ТІОНОВІ, ДЕНІТРИФІКУЮЧІ БАКТЕРІЇ В ПРИБЕРЕЖНІЙ ЗОНІ ЧОРНОГО МОРЯ І ЇХНЯ РОЛЬ У ТРАНСФОРМАЦІЇ НАФТОВИХ ВУГЛЕВОДНІВ 532.5 KB
  В 80х роках минулого сторіччя у відділі морської санітарної гідробіології Інституту біології південних морів НАН України вивчали деякі групи анаеробних бактерій біля узбережжя Криму та в західній частині Чорного моря Миронов 1988.
68216. КРІОКОНСЕРВУВАННЯ ТРОМБОЦИТІВ ДОНОРСЬКОЇ КРОВІ ЛЮДИНИ У БАГАТОКОМПОНЕНТНИХ КРІОЗАХИСНИХ СЕРЕДОВИЩАХ 362.5 KB
  При розробці методів кріоконсервування та довгострокового зберігання тромбоцитів при низьких температурах головна увага дослідників була сконцентрована на виборі кріопротектора і створенні на його основі ефективного кріоконсерванта.