21819

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

Лекция

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

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

Русский

2013-08-03

169 KB

28 чел.

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


 

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

37215. Финансовый контроль, его цели и задачи 49 KB
  Контроль является неотъемлемым элементом процесса государственного управления. Финансовый контроль призван обеспечивать1: правильность составления бюджетов различных уровней и их исполнения; соблюдение действующего бюджетного и налогового законодательства правильность ведения бухгалтерского учета составления отчетности; эффективное и целевое использования средств государственного бюджета и внебюджетных фондов; правильность операций с бюджетными средствами на счетах в банках и других кредитных учреждениях; выявление резервов роста бюджетных...
37216. Сущность государственного и муниципального кредита, его значение. Роль государственного и муниципального кредита в финансовом обеспечении общегосударственных, региональных и муниципальных потребностей 37 KB
  Роль государственного и муниципального кредита в финансовом обеспечении общегосударственных региональных и муниципальных потребностей. Государственный кредит – одна из форм кредитных отношений имеющая следующие признаки кредита: наличие кредитора и заемщика как юридически самостоятельных субъектов кредитной сделки; аккумуляции свободных денежных средств населения предприятий и организаций на принципах возвратности срочности и платности в исключительных случаях допускается беспроцентный заем ресурсов; возможность использования...
37217. Финансы, как экономический инструмент воздействия на экономику 44.5 KB
  Роль финансов в развитии международных связей проявляется по таким направлениям как: 1 Изыскание источников и мобилизация необходимых финансовых ресурсов для финансирования различных направлений международного сотрудничества. 2 Регулирование международных интеграционных процессов. 3 Стимулирование развития каждого вида международных отношений и непосредственных участников этих отношений. Еще одним направлением воздействия финансов на развитие международных связей является мобилизация ресурсов иностранных инвесторов.
37218. Финансы 59.5 KB
  Основа финансов предприятия – реальный денежный оборот обслуживающий экономический процесс создание и движение стоимости и сопровождающийся потоком денежных платежей и расчетов. Общепринято выделять 4 признака финансовых отношений: отношения денежные; отношения распределительные; отношения по формированию и использованию финансовых ресурсов в основном в форме денежных фондов; по одностороннему движению денежной формы стоимости без встречных взаимозависимых потоков. Финансы – это экономическая категория по поводу распределения стоимости...
37220. Финансовая политика 39 KB
  Содержание финансовой политики: Разработка общей концепции финансовой политики определение ее основных направлений целей главных задач. Управление финансовой деятельностью государства и других субъектов экономики. Основа финансовой политики стратегические направления которые определяют долгосрочную и среднесрочную перспективу использования финансов и предусматривают решение главных задач вытекающих из особенностей функционирования экономики и социальной сферы страны. Задачами финансовой политики является: обеспечение условий для...
37221. Экономическое развитие общества 77.5 KB
  На процесс общественного воспроизводства с одной стороны влияет множество факторов: количество и качество материальных финансовых трудовых ресурсов предпринимательские способности субъектов хозяйствования ускорение научнотехнического прогресса степень развития рыночных отношений и другие факторы. Но с другой стороны этот процесс представляет собой конфликтное взаимодействие и противоборство различных сил природного и общественного характера которые в совокупности создают объективные условия для проявления различного рода...
37222. Структура оборотных средств предприятия 40.5 KB
  Структура оборотных средств предприятия Оборотные производственные фонды – это часть производственных фондов которые участвуют в одном производственном процессе сразу переносят свою стоимость на себестоимость продукции и требуют своего возмещения по каждому производственному циклу. Фонды обращения – это сумма денежных средств предприятия вложенная в процесс реализации продукции и необходимая для обслуживания этого процесса. Организация оборотных средств необходимая для их эффективного использования включает: определение состава и...
37223. Экономическое содержание и классификация основных средств 58 KB
  Экономическое содержание и классификация основных средств В соответствии с ПБУ 6 01 Учет основных средств утвержденным приказом Минфина РФ от 30 марта 2001 г. При этом объект основных средств должен быть предназначен для использования в производстве продукции выполнении работ оказании услуг или для управленческих нужд организации и способен приносить организации экономические выгоды доход в будущем. В составе основных средств учитываются также: капитальные вложения на коренное улучшение земель осушительные оросительные и другие...