Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего профессионального образования
«Нижегородский государственный университет им. Н.И. Лобачевского»
Экономический факультет
Кафедра экономической информатики
В.С. Громницкий
Методы оптимизации
Курс лекций
Рекомендован методической комиссией экономического факультета для студентов высших учебных заведений, обучающихся по специальности 080801 «Прикладная информатика (в экономике)»
Нижний Новгород
2010
УДК 65.012.122 (075.8)
ББК Ув6я73
Г 87
Г87 Громницкий В.С. Методы оптимизации. Курс лекций: Учебное пособие – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010. – 104 с.
В пособии представлен материал по разделам прикладной математики, освоение которых необходимо для первоначального ознакомления с математическими методами принятия решений в экономико-управленческой сфере.
Приводится классификация задач принятия решений, дается понятие математического моделирования. Подробно излагаются методы линейного программирования, включая теорию двойственности и послеоптимизационный анализ. Даются основы нелинейного программирования.
Пособие предназначено для студентов экономического факультета университета, обучающихся по специальности «Прикладная информатика в экономике», может быть полезно для научных и практических работников, занимающихся вопросами моделирования и оптимизации экономических процессов.
Рецензент: доцент, к.э.н. Пчелинцев Александр Дмитриевич
ББК Ув6я73
© Громницкий В.С., 2010
© Нижегородский государственный
университет им. Н.И. Лобачевского, 2010
Содержание
|
[1] [2] Задачи принятия решений [3] Математическое моделирование
[4] [5] Глава 1. Линейные математические модели в экономических исследованиях [6] 1.1. Экономические задачи [7] 1.2. Общий вид математической модели задачи линейного программирования [8] 1.3. Различные формы задач линейного программирования [9] 1.4. Графическое решение задач [10] Глава 2. Математические свойства задачи линейного программирования [11] 2.1. Свойства области допустимых решений [12] 2.2. Базисные и опорные решения [13] Глава 3. Симплекс-метод решения задачи линейного программирования [14] 3.1. Идея симплекс-метода [15] 3.2. Векторное представление симплексных преобразований [16] 3.3. Симплекс-метод в уравнениях [17] 3.4. Симплекс-метод в таблицах [18] 3.5. Варианты разрешимости задачи линейного программирования [19] 3.6. Предупреждение зацикливания симплекс-метода [20] Глава 4. Метод искусственного базиса [21] 4.1. Построение начального опорного плана [22] 4.2. Решение задачи линейного программирования методом искусственного базиса [23] Глава 5. Теория двойственности в задачах линейного программирования [24] 5.1. Построение двойственной задачи и ее экономическая интерпретация [25] 5.2. Математические свойства пары взаимно двойственных задач [26] 5.3. Анализ чувствительности оптимального решения к изменению свободных членов ограничений [27] 5.4. Определение оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой [28] 5.5. Двойственный симплексный метод [29] Глава 6. Послеоптимизационный анализ задачи линейного программирования [30] 6.1. Добавление нового ограничения [31] 6.2. Добавление новой переменной [32] 6.3. Изменение коэффициентов критерия [33] 6.4. Изменение технологических коэффициентов
[34] [35] Глава 7. Классическая теория оптимизации [36] 7.1. Необходимые условия оптимальности [37] 7.2. Достаточные условия оптимальности [38] Глава 8. Нелинейное программирование [39] 8.1. Задачи на условный экстремум. Метод множителей Лагранжа. [40] 8.2. Задачи выпуклого программирования [41] Задания к лабораторным работам [42] Литература |
Предлагаемый к изучению предмет является частью прикладной математики. Структуру изучаемой и смежных областей знаний можно представить в виде следующей схемы.
Общая теория систем сформировалась в последние десятилетия двадцатого века как дисциплина, изучающая общие свойства сложных систем различной природы.
Системный анализ – методология анализа сложных систем различной природы (экономических, технических, биологических, социальных). Он предполагает структуризацию системы, формулировку целей и анализ полученных подсистем с помощью математических методов.
Система – совокупность взаимосвязанных элементов. Она описывается некоторыми параметрами, среди которых выделяют исходные (), управляемые
(A, B, C…) и выходные (). Задача анализа системы ставится как задача принятия решений, то есть задача выбора таких управляемых параметров, которые обеспечивают наилучшие показатели деятельности системы. Цели функционирования системы могут быть разные и обычно формулируются постановщиком задачи, лицом принимающим решения.
Исследование операций занимается изучением количественных методов анализа результатов целенаправленной человеческой деятельности с помощью экономико-математических методов.
Системы, не являющиеся результатом человеческой деятельности, изучаются в рамках общей теории систем другими специализированными дисциплинами. Примером такой дисциплины является математическая физика.
Математическая физика – наука, которая изучает поведение сплошных сред. К математической физике, в частности, относится механика жидкости, газа и твердых тел.
Исследование операций включает в себя целый ряд научных дисциплин, отличающихся целями и методами принимаемых решений:
где
Задача (1–2) относится к классу экстремальных задач. Если область допустимых решений D совпадает с пространством вещественных чисел R, то есть отсутствуют ограничения (2),то данная экстремальная задача является классической задачей оптимизации.
Моделирование – замена одного объекта другим с целью изучения их общих свойств.
По средствам моделирования методы моделирования можно разбить на две группы: методы материального моделирования и методы идеального моделирования.
Материальным моделирование называется в том случае, когда копия объекта – модель имеет материальный характер.
В материальном моделировании можно выделить три группы методов: пространственное, физическое и аналоговое
Пространственное моделирование изучает геометрические свойства объекта (макеты, карты, глобус).
Физическое моделирование служит для воспроизведения и изучения динамических свойств объектов (летательных аппаратов, технических сооружений).
В аналоговом моделировании изучаемый объект заменяется объектом другой физической природы, поведение которого описывается теми же математическими соотношениями, что и изучаемого объекта. Например, механические колебания изучают с помощью электрической системы, более простой и дешевой, чем её механический аналог. Так поступают при изучении колебаний мостов.
Идеальное моделирование основывается не на материальной аналогии модели и изучаемого объекта, а на идеальной, мыслимой связи между ними. Материальной копии не создается.
Методы идеального моделирования можно разбить на две группы: формализованное (знаковое) и неформализованное (интуитивное) моделирование.
В формализованном моделировании реальный объект заменяется системой знаков (схемы, графики, чертежи, формулы).
Важнейшим видом знакового моделирования является математическое моделирование. В этом случае копия моделируемого объекта (модель) представляет собой некоторые математические соотношения (уравнения, зависимости) между параметрами системы. Задавая значения одних параметров и находя из этих соотношений другие, интересующие исследователя параметры, можно тем самым проводить эксперименты с математической моделью.
Математическое моделирование с получением количественных результатов при помощи ЭВМ получило название вычислительного эксперимента. Возможности вычислительного эксперимента часто превышают возможности материального, натурного моделирования. В некоторых случаях удается провести вычислительный эксперимент тогда, когда натурный в принципе невозможен (ядерная физика, астрофизические исследования, поведение экономических систем).
Интуитивное моделирование – основано на построении мысленной копии объекта. Каждая наука стремится заменить интуитивное представление об изучаемых объектах формализованным, знаковым представлением. На этом пути перспективным является сочетание использования экспертных знаний специалистов и математических методов принятия решений.
Предприятие выпускает несколько видов продукции, при этом расходуется несколько типов ресурсов. Известны запасы ресурсов каждого типа, даны нормы расхода каждого ресурса на единицу каждой продукции и доход от единицы каждой продукции. Определить план производства, обеспечивающий наибольший суммарный доход.
2.1. Исходные параметры
– количество видов продукции
– количество типов ресурсов
– запасы ресурсов каждого вида
– нормы расхода i-го ресурса на единицу j-ой продукции
– доход от единицы j-ой продукции
2.2.Управляемые параметры (варьируемые параметры)
– объемы производства каждого вида продукции
– вектор управляемых параметров (решение, допустимое решение – план)
2.3. Ограничения модели
Чаще всего ограничения в экономических задачах отражают соотношения материального баланса (расход ресурса не может превосходить его запасов).
Пусть – расход i-го ресурса на произвольном плане .
Сформулируем критерий оптимальности. Пусть – суммарный доход на произвольном плане . Требуется найти его наибольшее значение
Таким образом, задача объемного планирования ставится как задача определения такого набора управляемых параметров
,
на котором достигается наибольшее значение критерия
при условии
Имеется несколько видов продуктов. Определить рацион питания (количество каждого вида продукта) так, чтобы были обеспечены нижние границы норм потребления некоторых питательных веществ, а стоимость рациона была наименьшая. Цены за единицу каждого продукта известны.
2.1. Исходные параметры
– количество видов продукта
– количество контролируемых питательных веществ
– нормы потребления каждого питательного вещества (нижние границы)
– содержание i-го питательного вещества в единице j-го продукта
– цена каждого продукта
2.2. Управляемые параметры (варьируемые параметры)
– объем закупок каждого продукта
– вектор управляемых параметров (решение, план закупок или рацион)
2.3. Ограничения модели
Потребление каждого питательного вещества не должно быть ниже нормы.
Пусть– содержание i-го питательного вещества в произвольном рационе .
Нужно выбрать наилучшее решение.
Сформулируем критерий оптимальности. Пусть – стоимость произвольного рациона . Требуется найти рацион наименьшей стоимости
Таким образом, задача о диете ставится как задача определения такого набора управляемых параметров
,
на котором достигается наименьшее значение критерия
при условии
В общем виде задача линейного программирования ставится следующим образом:
Найти набор управляемых параметров
,
на котором достигается наибольшее (наименьшее) значение показателя эффективности
при выполнении ограничений
и на некоторые переменные накладываются условия неотрицательности
Функция (7) называется целевой функцией или критерием оптимальности, или линейной формой.
Вектор управляемых параметров называется решением. Решение называется допустимым, если оно удовлетворяет ограничениям (8–11). Допустимое решение называется планом.
Решение называется оптимальным, если на нем достигается наибольшее значение критерия оптимальности :
– оптимальное решение, если
– оптимальное решение, если для любого
Задача линейного программирования называется разрешимой, если она имеет хотя бы одно оптимальное решение. У неразрешимой задачи или пуста область допустимых решений, или целевая функция не ограничена.
В зависимости от вида ограничений различают следующие формы задач:
Задача в канонической форме – задача ЛП, в которой все ограничения (8) – (10) есть равенства (p = q = 0) и все переменные неотрицательные (r = n).
Общий метод решения задачи ЛП разработан именно для задачи в каноническом виде.
Матричный вид задачи в канонической форме:
() = (*) →
=
= – вектор коэффициентов критерия
=
= – матрица условий (технологических коэффициентов)
= ( )
= – вектор условий
= – вектор ограничений
() = (*)
+ + …+ =
,
Для неё разработан метод решения, который называется симплексным.
Задача в симметричной форме – задача ЛП, в которой все ограничения (8) - (10) есть неравенства (p = q = m) и все переменные неотрицательные (r = n).
Матричный вид задачи в симметричной форме:
Симметричная форма допускает графическое решение (иллюстрацию).
Задача в общей (смешанной) форме – задача ЛП, в которой присутствуют все виды ограничений и не все переменные неотрицательные.
Приведение задачи линейного программирования от одной
эквивалентной формы к другой.
Преобразование сводится к смене знака критерия.
() ~ (())
() = (())
+ =
Переменные - дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.
- =
= -
= +
то оно заменяется на два неравенства:
А также:
Пусть ранг (количество линейно-независимых уравнений) системы ограничений равен , тогда переменных можно выразить через остальные:
Под решением систем уравнений (29) понимается зависимость одних переменных через другие. Эта зависимость (31) называется общим решением, независимые переменные – свободными (их можно произвольно менять), а – базисными переменными.
Задавая произвольные значения свободным переменным, получаем частные решения, но не все они удовлетворяют условиям неотрицательности:
Тогда для свободных переменных получаем ограничения в виде неравенств:
Если () = 2, то задача допускает иллюстрацию в пространстве двух переменных.
Для задачи в канонической форме, если все уравнения независимы и переменных на две больше, чем уравнений (т.е. () = 2), то свободных переменных в общем решении будет две и задача допускает графическое решение.
Примеры решения задач
Задача ЛП в симметричной форме (17) – (19) может быть решена графически, если пространство управляемых параметров содержит две или три переменные.
Пусть = 2, тогда задача ЛП в симметричной форме выглядит так:
Изобразим область допустимых решений в пространстве управляемых параметров. Для этого рассмотрим множество точек, удовлетворяющих неравенству (35). Это будет полуплоскость, ограниченная прямой.
Построим прямую .
Эта прямая делит все пространство на две полуплоскости. Для определения допустимой полуплоскости выбираем произвольную точку пространства, не лежащую на прямой (37) (лучше всего точку (0,0)), и подставляем её координаты в ограничение (35). Если ограничение выполняется, то полуплоскость, содержащая эту точку, допустимая.
Пересечение плоскостей образует область допустимых решений .
Поведение функции можно изобразить в пространстве управляемых параметров. Для этого достаточно построить семейство линий уровня функции. Линия уровня – это множество точек, в которых функция принимает постоянные значения.
(38)
Для задачи линейного программирования это прямые с разными константами в правой части уравнения (38).
Для построения линий уровня используем понятие градиента функции.
Градиент – это вектор частных производных функции.
= = ()
Его можно вычислить в любой конкретной точке пространства переменных.
Свойства градиента функции
Пример
=
Линии уровня для нелинейных функций хорошо иллюстрируются линиями постоянной высоты над уровнем моря на географических картах. В задачах линейного программирования линии уровня – это параллельные прямые вида (38), а градиент функции – это вектор коэффициентов целевой функции. Он одинаков для всех точек пространства управляемых параметров.
Для построения линий уровня в задаче линейного программирования можно выбрать произвольную точку области, построить в этой точке вектор градиента функции и перпендикулярно ему провести через выбранную точку линию уровня функции.
Для получения оптимального решения нужно перемещать линию уровня в направлении градиента до тех пор, пока она имеет общие точки с областью. Крайнее положение линии уровня называется опорной прямой (здесь вся область находится по одну сторону прямой и касается прямой в точке или отрезке). Общие точки опорной прямой с областью и являются оптимальными решениями.
Координаты оптимального решения находятся точно. Для этого нужно записать активные ограничения в виде равенств и решить совместно систему уравнений
Пример
Решим графически задачу 2 из примеров раздела 1.3.
– оптимальное решение двумерной задачи, в пространстве x2,x4.
Остальные компоненты решения можно найти из общего решения исходной системы уравнений.
– полное оптимальное решение пятимерной задачи.
Графическое решение наглядно иллюстрирует свойства области допустимых решений задачи линейного программирования.
Свойства области допустимых решений
Пусть дана задача в канонической форме:
Пусть все уравнения линейно-независимые.
ø
И пусть есть несколько - мерных векторов .
Выпуклая оболочка - мерных векторов – множество точек вида:
, ,
Выпуклая линейная комбинация двух векторов называется отрезком.
,
|
Двумерное пространство |
Трехмерное пространство |
Область называется выпуклой, если вместе с любыми двумя своими точками она содержит отрезок, соединяющий их.
Теорема 1: Область допустимых решений задачи ЛП выпуклая.
Доказательство:
Пусть , т.е. для них выполняются (2) и (3).
таким образом, условие (3) выполняется.
таким образом и условие (2) выполняется, произвольная точка отрезка принадлежит области D, то есть эта область выпукла.
Теорема доказана.
Точка называется угловой (крайней), если не существует двух других точек области, на отрезке между которыми лежит эта точка.
не , , , , таких, что ,
Лемма 1: Область допустимых решений задачи ЛП является выпуклой линейной комбинацией своих угловых точек.
Таким образом, если найти все угловые точки, то любая точка внутри области записывается через уравнение (4).
Теорема 2: Оптимальное решение задачи ЛП достигается в одной из угловых точек области допустимых решений .
Покажем, что оптимальное решение не может быть внутри области.
Пусть – внутренняя точка области. Тогда функция дифференцируема в этой точке:
Так как в этой точке достигается максимум, то и производная здесь обратится в ноль.
Но это противоречит условию, которое мы накладывали ранее, а именно . Значит точка, в которой достигается оптимальное решение, лежит на границе области. Можно показать [8], что хотя бы одно оптимальное решение достигается в угловой точке.
Напомним, что допустимое решение задачи линейного программирования называется планом (). В силу условия (3) компоненты плана неотрицательны. Выделим отдельно положительные и отрицательные компоненты. Пусть первые k компонент положительны. Будем рассматривать вектора условий при положительных и отрицательных компонентах плана.
Допустимое решение называется опорным, если вектора условий при его положительных компонентах решения линейно-независимы.
Вектора линейно-зависимые, если (для трех векторов) такие, что выполняется равенство ; либо если определитель из этих векторов равен нулю.
Пример:
|
8 |
10 |
5 |
12 |
|
|
10 |
18 |
7 |
15 |
|
|
19 |
22 |
9 |
23 |
Проверим, опорное это решение или нет:
– опорное решение (невырожденное).
В трехмерном пространстве максимум только 3 вектора могут быть независимыми.
– не является опорным решением, так как векторы линейно-зависимые. Значит, эта точка будет внутренней точкой области.
– опорное решение (вырожденное).
Так как определитель равен нулю, вектора линейно-зависимые.
– не является опорным решением.
Положительные компоненты опорного решения называются базисными.
Вектора условий линейных компонентов могут быть базисом в пространстве.
Базис - мерного пространства – совокупность любых линейно-независимых векторов .
Опорное решение называется невырожденным, если количество положительных компонент равно числу линейно-независимых ограничений (k=m).
Опорное решение называется вырожденным, если количество положительных компонент меньше числа линейно-независимых ограничений (k<m).
Нулевые переменные невырожденного опорного решения называются свободными.
Матрица, состоящая из векторов при положительных компонентах невырожденного опорного плана, называется базисной.
Базисное решение – решение системы уравнений (2) , если вектора условий при его ненулевых компонентах линейно-независимые.
Базисная матрица – матрица из линейно-независимых векторов условий, содержащая все вектора условий при ненулевых компонентах. Она всегда квадратная.
Базисная матрица невырожденного решения определяется однозначно, а базисная матрица вырожденного – неоднозначно.
Для определения базисного решения нужно выбрать произвольные переменных , вычислить определитель B из векторов условий этих переменных. Если , то занулить остальные переменные. Тогда для базисных переменных получим систему уравнений:
Максимальное количество базисных решений равно .
Опорное решение – допустимое базисное решение. Для поиска опорных решений можно перебрать все базисные решения и выбрать из них допустимые (с неотрицательными компонентами).
Теорема 3: опорные решения задачи ЛП совпадают с угловыми точками области допустимых решений.
Доказательство теоремы смотри в [8].
Симплекс в - мерном пространстве – простейший многогранник.
гранник
–треугольник
– тетраедр
Так как оптимальное решение достигается в угловой точке области допустимых решений, то искать оптимальное решение нужно среди опорных решений. Сначала найти произвольное опорное решение. Это вершина многогранника решений. Вместе с соседними с ней вершинами она образует симплекс в пространстве свободных переменных. Перейти к соседней вершине симплекса с лучшим значением критерия, двигаясь по одному из ребер симплекса (лучше по ребру, более близкому к вектору градиента функции).
Этапы симплекс-метода:
Пусть имеется опорный план и он невырожденный.
- базисная матрица.
- небазисная матрица.
Рассмотрим произвольное допустимое решение (это не угловая точка):
, подставим в условие (2).
Выразим базисные переменные через свободные и найдем общее решение системы уравнений:
Рассмотрим критерий на произвольном решении :
,
где
На опорном плане свободные переменные равны нулю, поэтому
,
а критерий в произвольной точке области выразится через свободные переменные в виде
Теорема 4: Опорный план задачи ЛП является оптимальным, если все оценки свободных переменных неотрицательны, т.е. .
Доказательство:
Для
т.к. , то и .
Значит решение оптимальное, так как во всех точках области значение критерия меньше (), чем критерий в точке .
Теорема доказана.
Рассмотрим симплексные преобразования на конкретном примере
Приведенная математическая модель может быть моделью следующей экономической задачи:
Определить объемы производства двух видов продукции, обеспечивающий наибольший доход, если в производстве используется 3 типа ресурсов, запасы которых соответственно 160, 40, 200. Доход от единицы продукции 10 и 7 соответственно. Нормы расхода ресурсов заданы матрицей . Оставшийся неиспользованным второй ресурс можно реализовать по цене 2.
Обозначая объемы производства продукции , получим ограничения
Сначала найдем опорный план. Возьмем за базисные переменные , занулим свободные переменные, тогда опорный план будет .
Для анализа этого опорного плана получим общее решение:
Проанализируем опорный план на оптимальность:
Решение не оптимальное, так как увеличение приводит к увеличению критерия, и увеличение также увеличивает критерий.
Будем увеличивать переменную , т.е. вводим ее в список базисных переменных.
При росте x1 уменьшаются базисные переменные x3 и x4. Определим, какая из них первая обратится в 0.
Первая обратится в 0 x4 при θ =20.
Следующее опорное решение будет . Это и есть новая угловая точка.
Проверим ее на оптимальность. Для этого получим новое общее решение, взяв за базисные переменные . Переменную выразим из второго уравнения и исключим её из двух других уравнений и из критерия:
При росте все базисные переменные уменьшаются. Будем увеличивать до тех пор, пока одна из базисных переменных не обратится в ноль.
Минимальное значение из . Получим новое опорное решение .
Для анализа на оптимальность получим новое общее решение. Растущая переменная входит в список базисных, замещая переменную .
Увеличением улучшить критерий нельзя, любое их увеличение уменьшает критерий.
Значит, найденное нами решение является оптимальным. Значение критерия на этом решении равно 240.
Приведенные выше преобразования удобно выполнять в специальных таблицах, называемых симплекс-таблицами.
В симплекс-таблице выделяются следующие блоки:
|
Показатели критерия оптимальности (коэффициенты сj целевой функции) |
|||
|
Св |
Бп |
Шапка матрицы (наименование неизвестных) |
b |
|
коэффициенты целевой функции при базисных неизвестных |
наименование базисных переменых |
Текущая матрица технологических переменных |
итоговый столбец (значение базисных переменнных bi) |
|
Оценочная строка ( оценки ) |
Значение целевой функции |
Запишем решение задачи примера из раздела 3.3 в симплекс-таблицах:
|
F |
10 |
7 |
0 |
2 |
0 |
||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
b |
|
0 |
x3 |
4 |
6 |
1 |
0 |
0 |
160 |
|
2 |
x4 |
2 |
1 |
0 |
1 |
0 |
40 |
|
0 |
x5 |
0 |
8 |
0 |
0 |
1 |
200 |
|
F |
-6 |
-5 |
0 |
0 |
0 |
80 |
|
|
0 |
x3 |
0 |
4 |
1 |
-2 |
0 |
80 |
|
10 |
x1 |
1 |
0.5 |
0 |
0.5 |
0 |
20 |
|
0 |
x5 |
0 |
8 |
0 |
0 |
1 |
200 |
|
F |
0 |
-2 |
0 |
3 |
0 |
200 |
|
|
7 |
x2 |
0 |
1 |
0.25 |
-0.5 |
0 |
20 |
|
10 |
x1 |
1 |
0 |
-0.125 |
0.75 |
0 |
10 |
|
0 |
x5 |
0 |
0 |
-2 |
4 |
1 |
40 |
|
F |
0 |
0 |
0.5 |
2 |
0 |
240 |
Все исходные данные, содержащиеся в математическом условии задачи, переносятся в первую симплексную таблицу. Зануляя свободные переменные, получаем опорный план
В последнюю строку первой симплекс-таблицы заносим критерий в неявной форме
Исключаем из этого критерия базисную переменную x4 , приводя критерий к виду
Для оптимальности решения все оценки должны быть неотрицательны
– решение не оптимальное, т.к. есть отрицательные оценки. (-6 и -5)
Оценки могут быть вычислены по формулам (12). Произведение
представляет из себя текущий вектор матрицы условий, тогда оценку свободной переменной можно вычислить как скалярное произведение вектора коэффициентов при базисных переменных на текущий вектор матрицы условий минус коэффициент целевой функции при этой переменной. Так, для получаем значение
=
Разрешающим столбцом выбираем тот, где наименьшая по величине оценка (если задача на максимум). А для выбора разрешающей строки нужно среди всех строк найти, выраженная из которой переменная, уменьшаясь, которая быстрее обращается в ноль.
В итоге, мы получаем, что разрешающий столбец – , а разрешающая строка - . Значит из списка базисных выходит переменная и входит переменная .
– решение не оптимальное, т.к. есть отрицательная оценка -2.
- решение оптимальное, т.к. все оценки больше нуля. Очевидно, что увеличить нельзя.
Решим задачу графически.
Правила построения симплекс-таблиц
Симплекс-таблица строится для какого-либо опорного решения.
Пусть опорное решение . Симплекс-таблица для этого решения имеет вид
|
F |
c1 |
c2 |
…. |
ck |
… |
cm |
cm+1 |
… |
cs |
… |
cj |
… |
cn |
||
|
Св |
Б.п |
x1 |
x2 |
…. |
xk |
… |
xm |
xm+1 |
… |
xs |
… |
xj |
… |
xn |
b |
|
c1 |
x1 |
1 |
0 |
… |
0 |
… |
0 |
a1 m+1 |
… |
a1 s |
… |
a1 j |
… |
a1 n |
|
|
c2 |
x2 |
0 |
1 |
… |
0 |
… |
0 |
a2 m+1 |
… |
a2 s |
… |
a2 j |
… |
a2 n |
|
|
… |
… |
… |
… |
… |
… |
… |
… |
…… |
… |
… |
… |
… |
… |
… |
… |
|
ck |
xk |
0 |
0 |
… |
1 |
… |
0 |
ak m+1 |
… |
ak s |
… |
ak j |
… |
ak n |
|
|
… |
… |
… |
… |
… |
… |
… |
… |
…… |
… |
… |
… |
… |
… |
… |
… |
|
ci |
xi |
0 |
0 |
… |
0 |
… |
0 |
ai m+1 |
… |
ai s |
… |
ai j |
… |
ai n |
|
|
cm |
xm |
0 |
0 |
… |
0 |
… |
1 |
am m+1 |
… |
am s |
… |
am j |
… |
am n |
|
|
F |
0 |
0 |
… |
0 |
… |
0 |
… |
… |
… |
Базисная матрица B = (A1, A2, … Am)
det B 0 B-1
Этапы симплекс-метода
Мысленно строится четырехугольник на диагонали, соединяющей искомый элемент с разрешающим. Тогда новое значение элемента равно прежнему значению минус произведение элементов на противоположной диагонали, деленное на разрешающий элемент.
Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.
Замечание: Если в разрешающей строке был нулевой элемент, значит этот столбец не меняется; если в разрешающем столбце есть нулевой элемент, то соответствующая строка не меняется.
Теорема 5: “О возможности увеличения критерия”.
Пусть – невырожденный опорный план, существует оценка свободной переменной меньше нуля . Тогда план не оптимальный и существует решение с лучшим значением критерия.
Для построения такого плана положим , тогда
(15)
Существует такое малое , что все базисные компоненты неотрицательны, то есть решение допустимое.
Теорема 6: “О возможности построения нового опорного плана”.
Если – невырожденный опорный план, существует , среди коэффициентов текущей матрицы условий существуют , то решение не оптимальное и существует новый опорный план с лучшим значением критерия.
,
Действительно, построив план вида (15) и увеличивая , заметим, что по крайней мере одна базисная переменная уменьшается. Когда одна из уменьшающихся базисных переменных обратится в 0, получим новый опорный план с лучшим значением критерия.
Теорема 7: “Условие неограниченности критерия”.
Если – невырожденный опорный план, существует , среди коэффициентов текущей матрицы условий нет положительных ,, то задача неразрешима из-за неограниченности критерия ().
Действительно, решение вида (15) остается допустимым при любом :
, а критерий неограниченно растет
Теорема 8: “Признак альтернативного оптимального решения”.
Пусть – невырожденный оптимальный план (выполняется признак оптимальности ,), и существует оценка свободной переменной . Тогда оптимальный план не единственный и существует другой план с таким же значением критерия , .
Действительно, на планах вида (15) критерий не изменяется, значит, все эти планы оптимальны.
В таком случае оптимальные решения находятся на отрезке , .
Зацикливание происходит тогда, когда в одной точке пересекаются границы гиперпространств, больших, чем количество свободных переменных.
Способы предупреждения:
Это приращение нужно следует настолько малым, чтобы это было несущественно для заказчика и различимо для вычислительных средств.
Если минимум отношения свободных членов к положительным коэффициентам разрешающего столбца достигается в нескольких строках
надо скорректировать правило выбора разрешающей строки.
Для выбора разрешающей строки, если минимальное отношение свободных членов к положительным коэффициентам разрешающего столбца определяется неоднозначно, достаточно из этих строк выбрать ту, в которой достигается минимальное отношение элементов другого столбца к элементам разрешающего столбца. Порядок выбора этих столбцов должен быть единым в ходе решения задачи, например в порядке нумерации переменных.
|
Б.п. |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
||||
|
x1 |
1 |
3 |
2 |
-2 |
0 |
0 |
6 |
2 |
1/3 |
||
|
x5 |
0 |
2 |
-6 |
4 |
1 |
0 |
4 |
2 |
0/2=0 |
-6/2=-3 |
4/2=2 |
|
x6 |
0 |
5 |
-15 |
5 |
0 |
1 |
10 |
2 |
0/5=0 |
-15/5=-3 |
5/5=1 |
|
F |
0 |
-7 |
-2 |
3 |
0 |
0 |
50 |
В приведенном примере в качестве разрешающей следует выбрать третью строку.
Пусть задача линейного программирования дана в каноническом виде и правые части ограничений неотрицательны
Если матраца условий содержит единичную подматрицу, опорный план очевиден.
В случае, когда матрица условий не содержит единичной подматрицы, для поиска опорного плана строится вспомогательная задача.
Опорный план этой задачи очевиден .
Область содержит все решения исходной задачи.
Теорема 9: Пусть оптимальное решение расширенной задачи (4)-(6). Если все искусственные переменные , то это решение является опорным для исходной задачи. Если хотя бы одна искусственная переменная больше 0, тогда область допустимых решений исходной задачи пуста.
Вспомогательная задача всегда имеет оптимальное решение, так как функция ограничена снизу нулем и, значит, она достигает своего минимального значения.
Пример построения начального опорного плана
Предприятие работает по трем технологиям. Найти время работы в сменах по каждой из технологий, если в производстве используется три продукта – A, B, C. Первый и третий продукт производится, а второй расходуется. По первой технологии за одну смену производится 1 тонна продукта А, расходуется 5 тонн продукта В, производится 2 тонны продукта С. По второй технологии за смену производится 2 тонны продукта А, расходуется 5 тонн продукта В, производится 3 тонны продукта С. По третьей технологии за смену производится 1 тонна продукта А, расходуется 2 тонны продукта В, производится 1 тонна продукта С. Расход продукта В не должен превосходить 500 тонн, производство продукта А должно составить ровно 160 тонн, а производство продукта С – не менее 190 тонн. Также известен доход за смену работы по каждой технологии – 6, 7 и 2 тыс. руб. соответственно.
Математическая модель задачи после приведения её к кононическому виду запишется в следующем виде
Для нахождения начального опорного плана строим вспомогательную задачу.
Построим симплекс-таблицу для этого опорного плана.
|
1 |
1 |
|||||||||
|
Св |
Б.п |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
b |
|
|
1 |
x6 |
1 |
2 |
1 |
0 |
0 |
1 |
0 |
160 |
80 |
|
0 |
x4 |
5 |
5 |
2 |
1 |
0 |
0 |
0 |
500 |
100 |
|
1 |
x7 |
2 |
3 |
1 |
0 |
-1 |
0 |
1 |
190 |
63.333 |
|
3 |
5 |
2 |
0 |
-1 |
0 |
0 |
350 |
|||
|
1 |
x6 |
-1/3 |
0 |
1/3 |
0 |
2/3 |
1 |
-2/3 |
100/3 |
50 |
|
0 |
x4 |
5/3 |
0 |
1/3 |
1 |
5/3 |
0 |
-5/3 |
550/3 |
110 |
|
0 |
x2 |
2/3 |
1 |
1/3 |
0 |
-1/3 |
0 |
1/3 |
190/3 |
|
|
-1/3 |
0 |
1/3 |
0 |
2/3 |
0 |
-5/3 |
100/3 |
|||
|
0 |
x5 |
-1/2 |
0 |
1/2 |
0 |
1 |
3/2 |
-1 |
50 |
|
|
0 |
x4 |
5/2 |
0 |
-1/2 |
1 |
0 |
-5/2 |
0 |
100 |
|
|
0 |
x2 |
1/2 |
1 |
1/2 |
0 |
0 |
1/2 |
0 |
80 |
|
|
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
0 |
Решение является оптимальным решением вспомогательной задачи, так как в строке оценок симплекс-таблицы нет положительных оценок.
Замечание: если оптимальное решение вспомогательной задачи вырожденное, искусственные переменные равны нулю и при этом искусственная переменная является базисной, то необходимо заменить нулевую искусственную переменную любой свободной переменной так, чтобы разрешающий элемент был ненулевым.
Эти операции не реализованы в диалоговой системе решения и анализа задач линейного программирования IBLP, поэтому при использовании метода искусственного базиса в IBLP следует посмотреть на опорный план и выяснить, нет ли нулевой искусственной переменной в базисе. Если есть, то вывести её из списка базисных через блок “Базисные решения”.
Для получения оптимального решения исходной задачи следует исключить переменные x6, x7, сменить критерий на исходный и решать полученную задачу симплекс-методом.
|
6 |
7 |
2 |
||||||
|
Св |
Б.п |
x1 |
x2 |
x3 |
x4 |
x5 |
b |
|
|
0 |
x5 |
-1/2 |
0 |
1/2 |
0 |
1 |
50 |
|
|
0 |
x4 |
5/2 |
0 |
-1/2 |
1 |
0 |
100 |
40 |
|
7 |
x2 |
1/2 |
1 |
1/2 |
0 |
0 |
80 |
160 |
|
F |
-5/2 |
0 |
3/2 |
0 |
0 |
560 |
||
|
0 |
x5 |
0 |
0 |
2/5 |
1/5 |
1 |
70 |
|
|
6 |
x1 |
1 |
0 |
-1/5 |
2/5 |
0 |
40 |
|
|
7 |
x2 |
0 |
1 |
3/5 |
-1/5 |
0 |
60 |
|
|
F |
0 |
0 |
1 |
1 |
0 |
660 |
– оптимальное решение.
Таким образом, если работать 40 смен по первой технологии, 60 смен по второй технологии и не использовать третью технологию, то мы получим максимальный доход. При этом весь продукт В будет использован, а продукта С будет производиться на 70 тонн больше, чем запланировано.
Пусть имеется исходная задача (1)-(3). Тогда построим расширенную задачу:
– сколь угодно большое число (множитель).
– штраф за нарушение ограничений.
Теорема 10: пусть – оптимальное решение расширенной задачи, тогда:
Замечание: если исходная задача является задачей минимизации, критерий расширенной задачи должен иметь вид .
Пример решения задачи методом искусственного базиса
Суточная потребность человека в витаминах и минеральных веществах удовлетворяется за счет потребления двух продуктов: апельсинов и черной икры. Содержание питательных веществ в продуктах (мг/100г), суточные нормы их потребления (мг) и цена продуктов (руб/кг) задаются таблицей:
|
Витамины |
Мин. вещества |
Цена |
|
|
Апельсины |
2 |
1 |
100 |
|
Черная икра |
1 |
3 |
200 |
|
Норма потребления |
24 |
27 |
При этом в рационе питания черной икры должно быть не более 800 грамм. Найти суточный рацион минимальной стоимости.
x1[100г] – количество апельсинов в рационе
x2[100г] – количество икры в рационе
g1() – содержание витаминов в рационе
g2() – содержание икры в рационе
– стоимость рациона.
Приведем задачу к каноническому виду:
|
10 |
20 |
0 |
0 |
0 |
M |
M |
||||
|
Св |
Б.п |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
b |
|
|
M |
x6 |
2 |
1 |
-1 |
0 |
0 |
1 |
0 |
24 |
24 |
|
M |
x7 |
1 |
3 |
0 |
-1 |
0 |
0 |
1 |
27 |
9 |
|
0 |
x5 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
8 |
|
F |
3M-10 |
4M-20 |
-M |
-M |
0 |
0 |
0 |
51M |
||
|
M |
x6 |
2 |
0 |
-1 |
0 |
-1 |
1 |
0 |
16 |
8 |
|
M |
x7 |
1 |
0 |
0 |
-1 |
-3 |
0 |
1 |
3 |
3 |
|
20 |
x2 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
|
|
F |
3M-10 |
0 |
-M |
-M |
-4M+20 |
0 |
0 |
19M+160 |
||
|
M |
x6 |
0 |
0 |
-1 |
2 |
5 |
1 |
-2 |
10 |
2 |
|
10 |
x1 |
1 |
0 |
0 |
-1 |
-3 |
0 |
1 |
3 |
|
|
20 |
x2 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
8 |
|
F |
0 |
0 |
-M |
2M-10 |
5M-10 |
0 |
-3M+10 |
10M+190 |
||
|
0 |
x5 |
0 |
0 |
-1/5 |
2/5 |
1 |
1/5 |
-2/5 |
2 |
|
|
10 |
x1 |
1 |
0 |
-3/5 |
1/5 |
0 |
3/5 |
-1/5 |
6 |
|
|
20 |
x2 |
0 |
1 |
1/5 |
-2/5 |
0 |
-1/5 |
2/5 |
9 |
|
|
F |
0 |
0 |
-2 |
-6 |
0 |
2-M |
6-M |
210 |
Таким образом, рацион должен содержать 900 г. апельсинов и 600 г. черной икры. Тогда он будет удовлетворять суточной потребности человека в минеральных веществах и витаминах, а также будет иметь наименьшую стоимость в 210руб.
Каждой задаче ЛП можно поставить в соответствие другую задачу, называемую двойственной. Совместное изучение свойств этих задач позволяет получить дополнительную информацию об изменении оптимального решения при изменении условий планирования. Также это позволяет разработать новые методы решения задач.
Решение двойственных задач полезно для экономического анализа.
Рассмотрим задачу объемного планирования. Пусть исходная задача такова:
Требуется определить объемы производства n видов продукции , обеспечивающие наибольший суммарный доход, при условии, что расход ресурсов не превосходит их запасов.
bi, – запасы ресурсов каждого вида
aij, – нормы расхода i-го ресурса на единицу j-ой продукции
cj, – доход от единицы j-ой продукции
Введем оценку полезности единицы i-го ресурса .
Добавим в систему одну тонну ресурса. На сколько при этом увеличится максимальный доход?
Сравним затраты ресурсов на единицу j-ой продукции с доходом, полученным от единицы j-ой продукции:
Исходя из закона сохранения материальных потоков, необходимо потребовать, чтобы суммарная оценка затрат была не меньше дохода, иначе доход буден получен из ничего. Будем искать такое решение, при котором суммарная оценка запасов ресурса минимальна:
Тогда задача (4)-(6) является двойственной к исходной задаче.
Математическая формулировка двойственной задачи к произвольной задаче линейного программирования
Пусть исходная задача имеет вид:
Тогда двойственной к задаче (7-10) называется задача вида:
Правила построения двойственной задачи
Для применения правил, необходимо в задаче на максимум записать все ограничения – неравенства со знаком . В задаче же на минимум – со знаком .
Пример:
Пусть исходная задача имеет вид:
Построить двойственную задачу.
Покажем, что эти задачи взаимно двойственные. Для этого построим двойственную задачу к двойственной:
Действительно, полученная задача совпадает с исходной.
Исходная (прямая) задача
Исходная в матричном виде
Двойственная задача
Двойственная задача в матричном виде
Лемма 1: двойственная задача к двойственной является исходной задачей.
Лемма 2 (основное неравенство теории двойственности): для любого допустимого решения прямой задачи и любого допустимого решения двойственной задачи критерий задачи максимизации не превосходит критерия задачи минимизации.
(7)
Доказательство:
, для него выполняются (2) и (3).
, для него выполняются (5) и (6).
Покажем, что выполняется (7). Заменяя бóльшим значением из (5), затем бóльшим значением из (2), получим
Теорема доказана.
Экономическая интерпретация основного неравенства теории двойственности: Суммарный доход на любом плане не может превзойти суммарной оценки используемых ресурсов при любых допустимых оценках.
Лемма 3 (достаточное условие оптимальности решений двух взаимно двойственных задач): решения и являются оптимальными для своих задач, если выполняется условие
Доказательство:
Покажем, что в условиях леммы – оптимальное решение (). Выберем произвольное. По основному неравенству теории двойственности , по условию леммы , значит .
А это означает, что – оптимальное решение прямой задачи.
Аналогичным образом доказывается, что – оптимальное решение двойственной задачи.
Теорема 1 (первая теорема двойственности): если прямая задача разрешима, то разрешима и двойственная задача, при этом критерии на оптимальных решениях равны
Доказательство приведем для прямой задачи в канонической форме:
Двойственная задача
– его базисная матрица, тогда
,
и его базисные компоненты можно записать в виде
, (11)
Подставим (12) в (11), получим
Неравенство (13) означает, что вектор – допустимое решение двойственной задачи
Тогда по лемме 3, если на двух допустимых решениях и критерии равны , то и – оптимальные решения своих задач.
Тем самым доказано, что – оптимальное решение двойственной задачи.
Теорема 1*: если исходная задача неразрешима из-за неограниченности критерия, то область допустимых решений двойственной задачи пуста.
Доказательство:
Предположим, что (область допустимых решений двойственной задачи не пуста). Тогда по лемме 2 для любого . Но по условию теоремы критерий исходной задачи не ограничен. Значит наше предположение не верно.
Тогда можно сделать вывод, что .
Теорема доказана.
Экономическая интерпретация первой теоремы двойственности: если существует оптимальный план производства, то существуют такие оценки ресурсов (производственных факторов), на которых достигается минимальная оценка затрат ресурсов и затраты полностью переходят в доход, то есть производство эффективно – без потерь.
Варианты разрешимости задач двойственной пары
Вариант 1: Обе задачи разрешимы.
Построим двойственную задачу:
Вариант 2: Критерий одной задачи не ограничен, область допустимых решений другой задачи пуста.
.
Построим двойственную задачу:
Вариант 3: Области допустимых решений обеих задач пусты.
, .
Построим двойственную задачу:
Таким образом, можно выделить следующие варианты разрешимости:
Следствие из первой теоремы двойственности: для разрешимости пары двойственных задач необходимо и достаточно, чтобы множество планов каждой из задач было не пустым.
Вторая теорема двойственности
Пусть взаимно двойственные задачи представлены в симметричной форме
Рассматриваемая ниже теорема позволяет утверждать, что на оптимальных решениях прямой и двойственной задач выполняется условие: для каждой пары понятий: (переменная одной задачи – соответствующее ограничение другой) или переменная обращается в ноль, или ограничение выполняется как равенство.
Теорема 2: для того, чтобы допустимое решение прямой задачи и допустимое решение двойственной задачи были оптимальными, необходимо и достаточно, чтобы выполнялись условия дополняющей нежесткости:
Условия (7)-(8) не означают ничего другого, как только то, что или переменная обращается в ноль, или ограничение выполняется как равенство.
Доказательство:
Пусть имеются , и для них выполняются условия (7)-(8). Покажем, что это оптимальные решения своих задач.
Для этого просуммируем (7) и (8) по j и по i соответственно:
Левые части соотношений (9) и (10) равны, значит, равны и правые, а это критерии целевых функций
, – оптимальные решения.
Пусть , – оптимальные решения. Покажем, что для них выполняются условия (7)-(8). С учетом соотношений (5) и (2) запишем
Продолжая неравенство (11) с учетом (12), получим
Так как , то каждое неравенство в (13) выполняется как равенство. Рассмотрим первое из них
Преобразуем
В левой части (14) – сумма неотрицательных слагаемых. Такая сумма равна нулю только тогда, когда каждое слагаемое равно нулю
А это и есть соотношения (7).
Аналогично доказываются и соотношения (8).
Теорема доказана.
Экономическая интерпретация второй теоремы двойственности:
Соотношения (7) и (8) позволяют по оптимальному решению одной задачи найти оптимальное решение другой.
Вторая теорема двойственности позволяет сформулировать признак оптимальности допустимого решения. Мы уже знаем один признак оптимального решения (теорема 4 главы 3), но он справедлив только для опорного решения (угловой точки области допустимых решений) и фактически требует построения симплекс-таблицы.
Следствие теоремы 2 (двойственный признак оптимальности): для того, чтобы допустимое решение задачи линейного программирования было оптимальным, необходимо и достаточно, чтобы среди решений системы уравнений
существовало хотя бы одно допустимое решение двойственной задачи .
Решение системы уравнений (15) и удовлетворяют соотношениям (7) и (8). И если среди решений (15) есть допустимое решение двойственной задачи, то тогда выполняются все условия второй теоремы двойственности и оба эти решения будут оптимальные.
Пример:
Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии – 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй – 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим.
[час] – время работы по каждой технологии
Для этого запишем соотношения дополняющей нежесткости (7-). Подставим в эти соотношения компоненты решения
Решая данную систему уравнений, получим . Подставим в ограничения двойственной задачи. Первое ограничение не выполняется:
Мы получили, что найденное нами решение не является допустимым для двойственной задачи. Поэтому можно сделать вывод, что решение не является оптимальным решением исходной задачи.
Таким образом, мы получили оптимальное решение двойственной задачи .
Пусть исходная задача дана в канонической форме:
Тогда двойственная к ней будет иметь вид:
Конечно, оптимальное решение зависит от исходных параметров, поэтому его можно рассматривать как неявно заданную функцию исходных параметров
.
Изучим влияние пока только одного параметра – ветора на оптимальное решение .
Пусть правые части ограничений (ресурсы) меняются, получая малые приращения:
– возмущенный вектор правых частей ограничений.
– (малые) приращения ресурсов.
Тогда задача с новым вектором правых частей ограничений (возмущенная задача) I’ и двойственная к ней II’ запишутся в виде
I’. (6)
II’.
Как найти оптимальное решение задачи I’, зная оптимальное решение задачи I?
Лемма: пусть – невырожденное оптимальное решение задачи I и – базисная матрица этого плана .
Если выполняется условие
,
то:
.
Доказательство:
Пусть – оптимальное решение, – его базисная матрица. Значит, существует и обратная матрица , базисные компоненты оптимального плана –, выполняется признак оптимальности .
Покажем, что вектор (10) – оптимальное решение возмущенной задачи.
Сначала покажем, что это допустимое решение, то есть для него должны выполняться ограничения (7) и (8).
Подставляя в левую часть (7), получим
,
то есть ограничение (7) выполняется.
Условие (8) выполняется из условия (9) леммы.
Итак, – допустимое решение задачи I’.
Покажем, что это оптимальное решение. Проверим признак оптимальности. Оценки свободных переменных возмущенной задачи совпадают с оценками свободных переменных исходной задачи , так как в формулах их расчета не участвуют свободные члены ограничений, а остальные параметры обеих задач совпадают
Значит, признак оптимальности выполняется и это есть оптимальное решение возмущенной задачи.
Первая часть леммы доказана.
Справедливость второй части (11) следует из того, что формулы расчета оптимальных решений задач, двойственных к I и I’ задач также совпадают.
Лемма доказана.
Область устойчивости двойственных оценок по отношению к изменению свободных членов ограничений – множество правых частей ограничений, при которых решение двойственной задачи не меняется. В силу доказанной леммы область устойчивости задается условием (9).
Теорема 3 (теорема об оценках, теорема о чувствительности): компоненты оптимального решения двойственной задачи являются оценками влияния свободных членов ограничений на оптимальное значение целевой функции.
Доказательство:
Рассмотрим оптимальное значение критерия как функцию от правых частей ограничений
По первой теореме двойственности критерии на оптимальных решениях прямой и двойственной задач равны
Будем рассматривать малые приращения правых частей ограничений, лежащие в области устойчивости двойственных оценок , тогда по доказанной выше лемме решение двойственной задачи не меняется и в правой части ( ) bi – переменные, а yi – константы.
Возьмем производную по bi от левой и правой части ( ), получим
Это и есть соотношение (15).
Теорема доказана.
Экономическая интерпретация третьей теоремы двойственности
Если соотношение (15) выполняется, то .
То есть если ресурс изменился на 1 , то .
Из соотношения (17) следует, что компонента оптимального решения двойственной задачи показывает, на сколько изменится оптимальное значение критерия при увеличении ресурса на 1.
Двойственные переменные называют также двойственными оценками, модельными ценами, теневыми ценами.
Разлагая функцию оптимального значения критерия в ряд по формуле Тейлора в окрестности , получим
В области устойчивости двойственных оценок приращение критерия может быть получено по формуле (18)
Пример:
Для задачи из раздела 5.2 о работе предприятия по двум технологиям, определим, как изменится оптимальное решение при изменении объемов используемых ресурсов
Математическая модель задачи:
Найдем оптимальное решение этой задачи методом искусственного базиса.
Для этого строим расширенную задачу:
Решение в симплекс-таблицах:
|
F |
8 |
3 |
-M |
||||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
b |
|
0 |
x3 |
2 |
1 |
1 |
0 |
0 |
12 |
|
0 |
x4 |
1 |
0 |
0 |
1 |
0 |
4 |
|
-M |
x5 |
1 |
1 |
0 |
0 |
1 |
6 |
|
F |
-8-M |
-3-M |
0 |
0 |
0 |
-6M |
|
|
0 |
x3 |
0 |
1 |
1 |
-2 |
0 |
4 |
|
8 |
x1 |
1 |
0 |
0 |
1 |
0 |
4 |
|
-M |
x5 |
0 |
1 |
0 |
-1 |
1 |
2 |
|
F |
0 |
-3-M |
0 |
8+M |
0 |
-2M+32 |
|
|
0 |
x3 |
0 |
0 |
1 |
-1 |
-1 |
2 |
|
8 |
x1 |
1 |
0 |
0 |
1 |
0 |
4 |
|
3 |
x2 |
0 |
1 |
0 |
-1 |
1 |
2 |
|
F |
0 |
0 |
0 |
5 |
3+M |
38 |
Ранее было найдено оптимальное решение двойственной задачи:
Найти оптимальное решение данной задачи, если вектор ресурсов изменился:
,
Базисная матрица оптимального плана
Обратную к ней возьмем из оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
|
0 |
x3 |
0 |
0 |
1 |
2 |
|||
|
8 |
x1 |
1 |
0 |
0 |
4 |
|||
|
3 |
x2 |
0 |
1 |
0 |
2 |
|||
|
F |
0 |
0 |
0 |
Проверим, что эти матрицы взаимно обратные:
Базисные компоненты решения измененной задачи
неотрицательны, значит по лемме 3 это базисные компоненты оптимального плана измененной задачи
В новых условиях по первой технологии следует работать 5 часов, по второй – 3 часа. Останется неиспользованной одна тонна первого ресурса.
Приращение оптимального значения критерия
Доход на новом оптимальном плане
Построение областей устойчивости двойственных оценок
Интервал устойчивости двойственных оценок к изменению компоненты вектора ограничений – такой интервал изменения этой компоненты, внутри которого решение двойственной задачи не меняется.
Для рассмотренной задачи найдем интервал устойчивости двойственных оценок к изменению запаса второго ресурса:
Получили интервал устойчивости в приращениях
,
А непосредственно интервал устойчивости
Это означает, что при уменьшении запасов второго ресурса до нуля или увеличении до 6 оценки всех ресурсов сохранят свои значения , а приращение критерия можно найти по формуле
Построим область устойчивости двойственных оценок к изменению всех ресурсов.
Напомним, что область устойчивости двойственных оценок к изменению правых частей ограничений – множество значений правых частей ограничений, при которых двойственные оценки не меняются.
Область устойчивости определяется условиями
Подставляем сюда
Для приращений ресурсов получаем систему неравенств
Неравенства (1) и определяют область устойчивости в трехмерном пространстве приращений ресурсов.
Если меняется только один ресурс, область устойчивости обращается в интервал устойчивости двойственных оценок к изменению этого ресурса.
Пусть меняется только второй ресурс:
– интервал устойчивости двойственных оценок к изменению второго ресурса.
Пусть меняется только третий ресурс:
– интервал устойчивости двойственных оценок к изменению третьего ресурса.
Построим область устойчивости двойственных оценок к одновременному изменению второго и третьего ресурсов:
Из графика видно, что область устойчивости (в приращениях ресурсов) высекает на осях координат интервалы устойчивости. При изменении приращений ресурсов внутри этой области сохраняется неизменным (устойчивым) решение двойственной задачи , сохраняется базис оптимального плана , а компоненты (базисные) оптимального плана меняются по формулам .
Найдем новое оптимальное решение при конкретных изменениях ресурсов внутри области устойчивости.
Пусть
Тогда приращение оптимального значения критерия
Базисные компоненты оптимального решения
,
а полный вектор нового оптимального решения
Экономическая интерпретация полученного решения:
При уменьшении запасов второго ресурса (катализатора) на 2 литра и одновременном увеличении длительности рабочей смены на 3 часа, по первой технологии следует работать 2 часа, по второй – 7 часов, при этом максимально возможный доход составит 37 тысяч рублей. Тонна первого ресурса останется неиспользованной.
Пусть исходная задача дана в канонической форме
Оптимальное решение получено симплекс-методом, – базисная матрица оптимального решения.
Оптимальное решение двойственной задачи (по первой теореме двойственности)
,
элементы строки оценок в оптимальной симплекс-таблице прямой задачи вычисляются по формулам
Подставляя (4) в (5) получим
Памятуя о том, что ограничение двойственной задачи, соответствующее переменной прямой задачи, имеет вид
, или ,
выводим из (6) важное свойство оценок :
Оценка переменной в симплекс-таблице равна разнице левой и правой части соответствующего ограничения двойственной задачи.
Из соотношения (6) легко найти компоненты оптимального решения двойственной задачи.
Действительно, пусть – единичный вектор с единицей в i-ой строке. В исходной симплекс-таблице всегда есть такие вектора.
Оценка переменной согласно (6) запишется
,
откуда
Таким образом, для определения компоненты оптимального решения двойственной задачи следует в исходной симплекс-таблице выбрать единичный столбец с единицей в i-ой строке. Тогда компонента равна оценке переменной из оптимальной симплекс-таблицы плюс коэффициент критерия этой переменной
Пример:
Найдем оптимальное решение двойственной задачи к задаче раздела 5.2 о работе предприятия по двум технологиям.
Воспроизведем для наглядности решение симплекс-методом
|
F |
8 |
3 |
0 |
0 |
-M |
||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
b |
|
0 |
x3 |
2 |
1 |
1 |
0 |
0 |
12 |
|
0 |
x4 |
1 |
0 |
0 |
1 |
0 |
4 |
|
-M |
x5 |
1 |
1 |
0 |
0 |
1 |
6 |
|
F |
-8-M |
-3-M |
0 |
0 |
0 |
-6M |
|
|
0 |
x3 |
0 |
1 |
1 |
-2 |
0 |
4 |
|
8 |
x1 |
1 |
0 |
0 |
1 |
0 |
4 |
|
-M |
x5 |
0 |
1 |
0 |
-1 |
1 |
2 |
|
F |
0 |
-3-M |
0 |
8+M |
0 |
-2M+32 |
|
|
0 |
x3 |
0 |
0 |
1 |
-1 |
-1 |
2 |
|
8 |
x1 |
1 |
0 |
0 |
1 |
0 |
4 |
|
3 |
x2 |
0 |
1 |
0 |
-1 |
1 |
2 |
|
F |
0 |
0 |
0 |
5 |
3+M |
38 |
|
Единичная матрица в исходной симплекс таблице расположена в столбцах
3, 4, 5.
Оптимальное решение двойственной задачи будет находиться в строке оценок оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы:
Рассмотрим базисное недопустимое решение .
Пусть все оценки на этом решении неотрицательные . Такое базисное решение называется псевдо-планом или псевдо-оптимальным решением. У него значение критерия лучше, чем у оптимального, но оно является недопустимым.
Для этого решения
, . А это означает, что псевдо-план исходной задачи соответствует опорному плану двойственной задачи: . При этом каждому псевдо-плану исходной задачи соответствует угловая точка двойственной.
Двойственная задача может быть решена симплекс-методом.
Двойственный симплекс-метод решения прямой задачи использует соответствующее решение двойственной задачи, но операции выполняются в симплекс-таблице исходной задачи. Перемещение происходит от одного псевдо-плана к другому с приближением к области. Когда очередное базисное решение станет допустимым, будет получено оптимальное решение.
Если симплексный метод – метод последовательного улучшения плана (улучшаются планы ), то двойственный симплекс-метод – метод последовательного улучшения оценок (улучшаются решения двойственной задачи – двойственные оценки ).
Условия применимости двойственного симплекс-метода:
Итерации в двойственном симплекс-методе выполняются по следующим правилам:
Это правило гарантирует, что новое базисное решение будет псевдо-планом.
Замечание: если в разрешающей строке нет отрицательных элементов, то область допустимых решений пуста.
Пример:
Целлюлозно-бумажный комбинат (ЦБК) на берегу озера Байкал может работать по двум технологическим режимам. По первому режиму в течение смены расходуется 100 м3 древесины, производится 50 тонн целлюлозы, 60 центнеров лигнитов (вещества, используемые в химической промышленности) и сбрасывается в озеро 10 кг отравляющих веществ. По второму режиму в течение смены расходуется 120 м3 древесины, производится 75 тонн целлюлозы, 30 центнеров лигнитов, сбрасывается в озеро 25 кг отравляющих веществ. Годовой план производства составляет 15000 тонн целлюлозы, 1200 тонн лигнитов. Предельные годовые нормы выброса отравляющих веществ составляют 5 тонн. Определить годовой план работы ЦБК, требующий минимального расхода древесины.
[см] – время работы (в сменах) по первой технологии;
[см] – время работы (в сменах) по второй технологии;
– годовой план работы.
2.2 Ограничения.
– годовое производство целлюлозы в тоннах должно быть не меньше плана;
– годовое производство лигнитов в центнерах должно быть не меньше плана;
– годовой выброс отравляющих веществ в килограммах не должен превосходить предельно-допустимых норм выброса.
– время работы по каждой из технологий неотрицательно
– годовой расход древесины должен быть минимален.
Получили следующую задачу линейного программирования
(1)
Приведем её к каноническому виду
– очевидное базисное решение, но оно не является допустимым.
Обеспечим условия применения двойственного симплекс-метода. Сменим знаки левых и правых частей первых двух уравнений
Занесем данные в симплекс-таблицу. Видим, что оценки переменных в последней строке первой симплекс-таблицы не положительны, то есть базисное решение является псевдо-планом, условия применимости двойственного симплекс-метода выполняются.
|
100 |
120 |
0 |
0 |
0 |
|||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
b |
|
0 |
x3 |
-50 |
-75 |
1 |
0 |
0 |
-15000 |
|
0 |
x4 |
-60 |
-30 |
0 |
1 |
0 |
-12000 |
|
0 |
x5 |
10 |
25 |
0 |
0 |
1 |
5000 |
|
F |
-100 |
-120 |
0 |
0 |
0 |
0 |
|
|
120 |
x2 |
2/3 |
1 |
-1/75 |
0 |
0 |
200 |
|
0 |
x4 |
-40 |
0 |
-2/5 |
1 |
0 |
-6000 |
|
0 |
x5 |
-20/3 |
0 |
1/3 |
0 |
1 |
0 |
|
F |
-20 |
0 |
-8/5 |
0 |
0 |
24000 |
|
|
120 |
x2 |
0 |
1 |
-1/50 |
1/60 |
0 |
100 |
|
100 |
x1 |
1 |
0 |
1/100 |
-1/40 |
0 |
150 |
|
0 |
x5 |
0 |
0 |
2/5 |
-1/6 |
1 |
1000 |
|
F |
0 |
0 |
-7/5 |
-1/2 |
0 |
27000 |
– псевдо-план.
На первой итерации выбирается первая разрешающая строка (-15000<0) и второй разрешающий столбец (120/75<100/50). Выполняются операции однократного замещения. Получаем следующее приближение к области.
На второй итерации разрешающая строка вторая (-6000,0), разрешающий столбец первый (20/40=0.5< 8/5:2/5=4).
Следующее решение
– допустимое базисное, значит оптимальное.
Экономическая интерпретация полученного решения: для обеспечения минимального расхода древесины нужно работать 150 смен по первой технологии, 100 смен по второй технологии, при этом расход древесины будет составлять 27000 м3. Производство целлюлозы и лигнитов совпадает с плановым (так как x3=x4=0), выброс отравляющих веществ на 1000 кг меньше предельно-допустимых норм выброса.
Построим двойственную задачу. Для применения правил построения двойственных задач необходимо согласовать знаки неравенств с типом критерия:
(3)
Введем переменные двойственной задачи:
– оценка полезности 1 тонны целлюлозы;
– оценка полезности 1 центнера лигнитов;
– оценка «полезности» 1 кг отравляющих веществ. Значение у3 на оптимальном плане будет показывать, на сколько изменится критерий при увеличении b3 на единицу (с -5000 до -4999). В терминах исходной задачи – это приращение расхода древесины от ужесточения (уменьшения) предельно допустимых норм выброса отравляющих веществ на один килограмм.
Тогда двойственная задача запишется в виде
(4)
Найдем оптимальное решение двойственной задачи из оптимальной симплекс-таблицы прямой задачи:
(5)
Казалось бы, полученное решение опровергает теорию получения оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой. Полученное решение даже недопустимое – нарушаются условия неотрицательности в (4).
Действительно, (5) – это не оптимальное решение задачи (4), двойственной к задаче (3). Вектор – это оптимальное решение задачи, двойственной к задаче (2). Именно эта задача представлена в исходной симплекс-таблице.
Хотя задачи (2) и (3) эквивалентны, имеют совпадающие области допустимых решений, но формы представления задач разные и двойственные к ним задачи будут отличаться не только формой, но и значением оптимальных решений. Однако оптимальные решения этих задач легко могут быть получены друг из друга.
Построим двойственную задачу к задаче (2):
(6)
После замены переменных
задача (6) обращается в задачу (4).
Таким образом, если из симплекс-таблицы получено оптимальное решение
задачи, двойственной к задаче (2), то решение двойственной к задаче (3) может быть получено сменой знаков компонент решения:
Экономический смысл двойственных переменных:
показывает, что при увеличении плана выпуска целлюлозы на 1 тонну расход древесины возрастет на 1.4 м3.
показывает, что при увеличении плана выпуска лигнитов на 1 центнер расход древесины возрастет на 0.5 м3.
показывает, что при уменьшении годовых предельно допустимых норм выброса отравляющих веществ на 1 килограмм расход древесины не изменится. Действительно, на оптимальном решении ограничение по выбросу отравляющих веществ не активное, выброс (4000) не достигает предельной нормы (5000), поэтому уменьшение нормы не только на 1, но и на величину в пределах 1000 килограммов не повлияет на оптимальный план работы комбината.
Полученные оценки влияния рассмотренных параметров на оптимальное значение критерия справедливы в области устойчивости двойственных оценок.
Пусть исходная задача решена, получено её оптимальное решение и оптимальное решение двойственной к ней задачи:
Представляет интерес то, как меняются характеристики оптимального решения при изменении условий планирования. Исследованием этих вопросов и занимается послеоптимизационный (постоптимизационный) анализ.
Послеоптимизационный анализ предполагает решение следующих задач:
Пусть исходная задача дана в канонической форме
I.
Двойственная к ней будет иметь вид
II.
Первый вид анализа – анализ чувствительности оптимального решения к изменению правых частей ограничений уже рассмотрен в разделе 5.3. Он является основой для понимания смысла двойственных переменных.
Рассмотрим другие виды анализа.
Пусть в математической модели задачи (1-3) появилось новое ограничение
Возможны две ситуации:
Для этого требуется новое ограничение привести к виду уравнения.
Включим новое ограничение в оптимальную симплекс-таблицу. Но прежде исключим из этого уравнения базисные переменные, чтобы в симплекс-таблице столбцы при базисных переменных были единичными.
Пример:
В задаче о работе ЦБК учтем ограничения на кислотные выбросы в атмосферу. Известно, что по первой технологии за 1 смену выбрасывается 1 кг кислотных выбросов, по второй – 3 кг. При этом предельно допустимые годовые нормы выброса составляют 360 кг.
В математической модели появится новое ограничение
,
а вся система ограничений примет вид
Проверим, удовлетворяет ли прежнее оптимальное решение новому ограничению:
Ограничение не выполняется.
Преобразуем его к виду уравнения, введя балансовую переменную x6
Заменим в этом уравнении базисные переменные x1, x2 их значениями через свободные из оптимальной симплекс-таблицы
Уравнение примет вид
Включаем его в оптимальную симплекс-таблицу и решаем далее двойственным симплекс-методом
|
100 |
120 |
|||||||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
|
120 |
x2 |
0 |
1 |
-1/50 |
1/60 |
0 |
0 |
100 |
|
100 |
x1 |
1 |
0 |
1/100 |
-1/40 |
0 |
0 |
150 |
|
0 |
x5 |
0 |
0 |
2/5 |
-1/6 |
1 |
0 |
1000 |
|
0 |
x6 |
0 |
0 |
1/20 |
-1/40 |
0 |
1 |
-90 |
|
F |
0 |
0 |
-7/5 |
-1/2 |
0 |
0 |
27000 |
|
|
120 |
x2 |
0 |
1 |
1/75 |
0 |
0 |
2/3 |
40 |
|
100 |
x1 |
1 |
0 |
1/25 |
0 |
0 |
-1 |
240 |
|
0 |
x5 |
0 |
0 |
1/15 |
0 |
1 |
-20/3 |
1600 |
|
0 |
x4 |
0 |
0 |
-2 |
1 |
0 |
-40 |
3600 |
|
F |
0 |
0 |
-12/5 |
0 |
0 |
-20 |
28800 |
На следующей итерации получаем новое оптимальное решение
В новых условиях комбинат должен работать 240 смен по первой технологии, 40 смен по второй. Расход древесины возрастет до 28800 м3.
Пусть в математической модели (1-3) появилась новая переменная
В задаче объемного планирования это означает возможность производить новый вид продукции с известными затратами ресурсов и известным доходом от единицы продукции. Сохранится ли прежнее оптимальное решение? Если нет, то как найти новое оптимальное решение?
Если в исходной задаче появляется новая переменная, то в двойственной задаче появляется новое ограничение
(6)
или
Вектор – прежнее оптимальное решение с нулевой n+1-ой компонентой является допустимым решением новой задачи (1’-3’). Если выполняется условие (6), то вектор – прежний вектор оптимальных двойственных оценок – допустимое решение двойственной к (1’-3’) задачи. Соотношения дополняющей нежесткости для этих двух решений пополнились условием
и выполняются за счет . Значит, решение – оптимальное для новой задачи.
Этому выводу можно дать экономическое обоснование. Выполнение условия (6) означает, что затраты на единицу новой продукции превышают доход. Значит, такую продукцию производить не выгодно, , прежнее оптимальное решение не меняется.
Если ограничение (6) не выполняется, затраты на единицу новой продукции меньше дохода, , то такую продукцию следует производить, объем производства нужно увеличивать.
Для получения нового оптимального решения следует дополнить прежнюю оптимальную симплекс-таблицу новым столбцом
,
а оценку переменной найти как разность левой и провой части ограничения (6) двойственной задачи
В полученной симплекс-таблице признак оптимальности не выполняется (), переменную нужно вводить в список базисных и далее решать задачу симплекс-методом.
Пример:
Предположим, что у ЦБК появилась возможность работать по третьей технологии с расходом за смену 103 кубометра древесины, производительностью в смену 60 тонн целлюлозы, 40 центнеров лигнитов и 20 килограммов отравляющих веществ.
, .
Обозначив – время работы по третьей технологии, ищем решение в виде для новой математической модели
(7)
Новая переменная порождает в двойственной задаче новое ограничение
(8)
Проверим, удовлетворяет ли этому ограничению вектор оптимальных двойственных оценок исходной задачи:
Ограничение (8) не выполняется, суммарная оценка полезности произведенной за смену продукции (104 м3) превышает затраты (103м3), значит прежнее решение не является оптимальным.
Для определения нового оптимального решения включим в прежнюю оптимальную симплекс таблицу столбец с переменной .
В исходную симплекс-таблицу новый вектор условий войдет в виде
, так как менялись знаки в первых двух уравнениях (см. раздел 5.5). В оптимальной симплекс-таблице он преобразуется к виду
Оценка переменной определится как разность левой и правой части ограничения двойственной задачи (8)
Оценка положительна, что нарушает условие оптимальности опорного плана. Решаем далее симплекс-методом
Исходная симплекс-таблица
|
100 |
120 |
0 |
0 |
0 |
103 |
|||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x3d |
b |
|
0 |
x3 |
-50 |
-75 |
1 |
0 |
0 |
-60 |
-15000 |
|
0 |
x4 |
-60 |
-30 |
0 |
1 |
0 |
-40 |
-12000 |
|
0 |
x5 |
10 |
25 |
0 |
0 |
1 |
20 |
5000 |
|
F |
-100 |
-120 |
0 |
0 |
0 |
-103 |
0 |
|
|
Оптимальная симплекс-таблица |
||||||||
|
120 |
x2 |
0 |
1 |
-1/50 |
1/60 |
0 |
8/15 |
100 |
|
100 |
x1 |
1 |
0 |
1/100 |
-1/40 |
0 |
2/5 |
150 |
|
0 |
x5 |
0 |
0 |
2/5 |
-1/6 |
1 |
8/3 |
1000 |
|
F |
0 |
0 |
-7/5 |
-1/2 |
0 |
1 |
27000 |
|
|
103 |
x3d |
0 |
15/8 |
-3/80 |
1/32 |
0 |
1 |
375/2 |
|
100 |
x1 |
1 |
-3/4 |
1/40 |
-3/80 |
0 |
0 |
75 |
|
0 |
x5 |
0 |
-5 |
1/2 |
-1/4 |
1 |
0 |
500 |
|
F |
0 |
-15/8 |
-109/80 |
-17/32 |
0 |
0 |
26812.5 |
На следующей итерации получим оптимальное решение новой задачи
Комбинат должен работать 75 смен по первой технологии, 187.5 смен по третьей дополнительной технологии. При этом расход древесины будет наименьшим и составит 26812.5 кубометров.
Влияние изменения коэффициентов критерия на оптимальное решение задачи хорошо видно на графике в пространстве двух управляемых параметров. Оптимальное решение не меняется, если вектор коэффициентов критерия (градиент функции) меняется в конусе градиентов активных ограничений.
Если меняется только коэффициент (пусть это цена второго вида продукции), то
– при оптимальное решение переходит в другую угловую точку области допустимых решений.
– при оптимальное решение также меняется.
– при оптимальное решение остается неизменным.
Как найти оптимальное решение задачи с измененными коэффициентами критерия, используя оптимальную симплекс-таблицу исходной задачи?
Пусть, для простоты, меняется только один коэффициент критерия. Будем отдельно рассматривать два случая:
– Меняется коэффициент критерия при свободной переменной оптимального плана
– Меняется коэффициент критерия при базисной переменной оптимального плана:
Симплекс-таблица оптимального плана . Имеет вид
|
c1 |
c2 |
--- |
cm |
cm+1 |
--- |
cj |
--- |
cn |
|||
|
Св |
Бп |
x1 |
x2 |
--- |
xm |
xm+1 |
--- |
xj |
--- |
xn |
b |
|
с1 |
x1 |
1 |
0 |
--- |
0 |
--- |
--- |
||||
|
--- |
--- |
--- |
--- |
--- |
--- |
||||||
|
сm |
xm |
0 |
0 |
--- |
1 |
||||||
|
F |
0 |
0 |
--- |
0 |
--- |
--- |
F(x*) |
Изменение коэффициента критерия при свободной переменной
Пусть меняется коэффициент критерия при свободной переменной :
Оценки в симплекс-таблице вычисляются по известной формуле
Если меняется коэффициент при свободной переменной, то вектор коэффициентов при базисных переменных не меняется. Поэтому в симплекс-таблице меняется только одна оценка – при переменной
Для оптимальности решения она должна оставаться неотрицательной (в задаче максимизации).
Поэтому прежнее решение остается оптимальным, если .
Если , то тогда , прежнее решение не оптимальное и нужно выполнить несколько итераций симплекс-метода для получения нового оптимального решения.
Пример:
В плане работы ЦБК, работающем по трем технологиям с затратами древесины по третьей технологии 110 м3 в смену, определить в каких пределах может меняться расход древесины по третьей технологии, чтобы при этом прежнее решение оставалось оптимальным.
Симплекс-таблица для оптимального решения этой задачи имеет вид
|
100 |
120 |
110 |
||||||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
|
120 |
x2 |
0 |
1 |
8/15 |
-1/50 |
1/60 |
0 |
100 |
|
100 |
x1 |
1 |
0 |
2/5 |
1/100 |
-1/40 |
0 |
150 |
|
0 |
x6 |
0 |
0 |
8/3 |
2/5 |
-1/6 |
1 |
1000 |
|
F |
0 |
0 |
-6 |
-7/5 |
-1/2 |
0 |
27000 |
Таким образом, мы пришли к выводу, что оптимальное решение сохраняется, если расход древесины не менее 104 м3.
Найдем оптимальное решение, лежащее вне этого интервала.
Пусть расход древесины удалось уменьшить до
Выполняя одну итерацию симплекс-метода,
|
100 |
120 |
110 |
||||||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
|
120 |
x3 |
0 |
15/8 |
1 |
-3/80 |
1/32 |
0 |
375/2 |
|
100 |
x1 |
1 |
-3/4 |
0 |
1/40 |
-3/80 |
0 |
75 |
|
0 |
x6 |
0 |
-5 |
0 |
1/2 |
-1/4 |
1 |
500 |
|
F |
0 |
-15/8 |
0 |
-109/80 |
-17/38 |
0 |
26812.5 |
получим новое оптимальное решение
Изменение коэффициента критерия при базисной переменной
Пусть меняется коэффициент критерия при базисной переменной :
Так как переменная – базисная переменная, то меняется вектор коэффициентов при базисных переменных , в симплекс-таблице меняется крайний левый столбец. Это повлечет изменение большинства оценок свободных переменных. Новые оценки вычисляются следующим образом:
Из этой системы неравенств находим интервал – интервал неизменности (устойчивости) оптимального решения.
Пример:
Пусть в плане работы ЦБК по двум технологиям меняется расход древесины во время работы по второй технологии. В каких пределах можно изменять расход, чтобы прежнее решение оставалось оптимальным?
Внесем изменения в оптимальную симплекс-таблицу
|
100 |
120+ |
|||||||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
|
120 |
x2 |
0 |
1 |
-1/50 |
1/60 |
0 |
100 |
|
|
100 |
x1 |
1 |
0 |
1/100 |
-1/40 |
0 |
150 |
|
|
0 |
x6 |
0 |
0 |
2/5 |
-1/6 |
1 |
1000 |
|
|
F |
0 |
0 |
-7/5 |
-1/2 |
0 |
27000 |
Получили, что прежнее решение остается оптимальным, если расход древесины по второй технологии меняется в пределах от 50 до 150 кубометров в смену.
Рассмотрим влияние на оптимальное решение изменения матрицы технологических коэффициентов
Пусть меняется один технологический коэффициент
Так же, как в предыдущем разделе следует рассмотреть два случая
Изменение технологических коэффициентов при базисной переменной
Изменение коэффициента при базисной переменной меняет базисную матрицу оптимального плана. Меняется и матрица, обратная к базисной, которая используется в расчете основных характеристик оптимального решения как прямой, так и двойственной задач.
Вычислительные затраты на пересчет матрицы, обратной к базисной, сопоставимы с затратами на повторное решение задачи симплекс-методом, поэтому не существует более эффективного способа получения оптимального решения измененной задачи.
Изменение технологических коэффициентов при свободной переменной
Пусть меняются технологический коэффициент при свободной переменной .
Такое изменение технологического коэффициента не меняет базисную матрицу.
В оптимальной симплекс-таблице изменится только один столбец при переменной . Его следует вычислить по формуле
Посмотрим, как изменится оценка свободной переменной :
Полученное неравенство является условием сохранения прежнего оптимального решения для задачи максимизации.
Пример:
Пусть в плане работы ЦБК по трем технологиям c затратами древесины 100, 120, 110 м3 меняются объемы производства целлюлозы за смену работы по третьей технологии.
В первой симплекс-таблице .
Оптимальная симплекс-таблица до изменения :
|
100 |
120 |
110 |
||||||
|
Св |
Бп |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
|
120 |
X2 |
0 |
1 |
8/15 |
-1/50 |
1/60 |
0 |
100 |
|
100 |
X1 |
1 |
0 |
2/5 |
1/100 |
-1/40 |
0 |
150 |
|
0 |
X6 |
0 |
0 |
8/3 |
2/5 |
-1/6 |
1 |
1000 |
|
F |
0 |
0 |
-6 |
-7/5 |
-1/2 |
0 |
27000 |
|
|
y1 |
y2 |
y3 |
В этой таблице следует пересчитать оценку :
Таким образом, если производство целлюлозы за смену по третьей технологии будет уменьшаться до нуля или увеличиваться до 64.286 м3, оптимальный план останется прежним , третья технология не будет использоваться.
Если производительность третьей технологии превысит 64.286 м3, она будет использоваться, оптимальное решение изменится. Новое оптимальное решение можно будет найти, изменив в оптимальной симплекс-таблице столбец 3 и продолжив решение симплекс-методом.
Задача математического программирования
называется задачей нелинейного программирования, если функция цели или хотя бы одна из функций ограничений не линейна.
Точка называется точкой локального экстремума, если существует – окрестность этой точки , для которой ,.
Точка называется точкой глобального экстремума, если для любого .
Функция называется унимодальной (одноэкстремальной), если у этой функции имеется только один локальный экстремум. В противном случае она называется многоэкстремальной.
В классической теории оптимизации рассматриваются экстремальные задачи без ограничений, то есть область D совпадает со всем n-мерным пространством вещественных чисел .
Рассмотрим задачу безусловной оптимизации
В случае достаточной дифференцируемости функции можно сформулировать необходимые и достаточные условия локального экстремума.
Для функции одной переменной справедлива следующая теорема.
Теорема 1: для того, чтобы функция одной переменной имела в точке локальный экстремум, необходимо, чтобы производная функции в этой точке была равна нулю.
Аналогичная теорема справедлива для функции многих переменных.
Теорема 2: для того, чтобы функция имела в точке локальный экстремум, необходимо, чтобы все ее частные производные в этой точке обращались в ноль
Другими словами, вектор градиента функции в этой точке должен быть нулевым.
Такие точки называются стационарными точками функции.
Для функции одной переменной достаточные условия задаются следующей теоремой.
Теорема 3: если в точке первая производная функции равна нулю, а вторая производная , то функция в точке имеет локальный минимум, если , то функция в точке имеет локальный максимум.
Если вторая производная функции в точке равна нулю, то необходимо исследовать производные высших порядков в соответствии со следующей теоремой.
Теорема 4: если функция одной переменной имеет в точке производные до порядка равными нулю и производная , то тогда,
если четно, то точка является точкой минимума, если ,
точкой максимума – если .
Если нечетно, то точка – точка перегиба.
Для обобщения теоремы 3 на случай функции многих переменных рассмотрим матрицу вторых производных функции и её свойства.
Матрицей Гессе (Гессианом) называется матрица вторых производных функции:
Для анализа поведения функции в точке потребуются некоторые свойства квадратичных функций.
Рассмотрим квадратичную функцию (форму):
Числовая матрица называется матрицей квадратичной формы. Можно считать, что эта матрица симметрична.
Квадратичная форма (6) называется положительно определенной, если для и отрицательно определенной, если для .
Симметричная матрица A называется положительно определенной, если построенная по ней квадратичная форма (6) положительно определена.
Симметричная матрица называется отрицательно определенной, если построенная по ней квадратичная форма (6) отрицательно определена.
Проверить положительную или отрицательную определенность числовой матрицы можно по следующим признакам.
Признаки:
Матрица является отрицательно определенной, если знаки угловых миноров чередуются.
Или: если все угловые миноры удовлетворяют неравенству .
Собственные числа – корни многочлена . Этот определитель есть многочлен относительно .
.
Для того чтобы матрица была отрицательно определенной, необходимо, чтобы все ее собственные числа были меньше нуля.
Достаточное условие оптимальности задается следующей теоремой.
Теорема 5: если в стационарной точке (т.е. ) матрица Гессе положительно определена, то эта точка – точка локального минимума, если матрица Гессе отрицательно определена, то эта точка – точка локального максимума.
Доказательство:
Пусть – стационарная точка, , возьмем окрестность точки . Тогда по теореме Тейлора
По условию теоремы , а матрица Гессе в точке положительно определена, то есть квадратичная форма >0 в точке , а в силу непрерывности вторых частных производных и в точке .
Значит точка – точка локального минимума.
Пример: Продукция трех видов производится в объеме и реализуется по цене соответственно. Определить объемы производства, обеспечивающие наибольший доход.
Определим стационарные точки функции
:
Решением этой системы линейных алгебраических уравнений является вектор
Проверим достаточное условие оптимальности. Вычислим матрицу Гессе в полученной стационарной точке.
Угловые миноры матрицы имеют чередующиеся знаки
,
значит, матрица Гессе отрицательно определена и точка – точка локального максимума. При полученных объемах производства будет достигнут наибольший доход .
Проверим отрицательную определенность матрицы вторым способом. Найдем собственные числа матрицы Гессе
Так как все собственные числа матрицы , то матрица отрицательно определена и – локальный максимум.
Задача на условный экстремум ставится как задача определения управляемых параметров , на которых достигается экстремум (максимум или минимум) при ограничениях, заданных уравнениями.
Задачу на условный экстремум можно свести к задаче на безусловный экстремум для специальным образом построенной функции.
Каждому ограничению поставим в соответствие переменную .
Построим функцию Лагранжа:
Если ограничения выполняются, то функция Лагранжа превращается в исходную функцию.
Точки локальных экстремумов задачи (8), (9) будут точками локальных экстремумов функции Лагранжа.
Теорема 6 (необходимое условие экстремума): если – точка локального экстремума и в окрестности этой точки функции непрерывно дифференцируемы, то в этой точке выполняются условия
Условия (10) означают, что градиент функции Лагранжа равен нулю
Для формулировки достаточных условий оптимальности рассмотрим
окаймляющую матрицу Гессе:
Теорема 7 (достаточное условие экстремума):
Достаточное условие оптимальности можно сформулировать также в другой форме: если рассмотреть определитель, построенный из окаймляющей матрицы Гессе
,
то стационарная точка функции Лагранжа является точкой максимума, если все действительных корней многочлена (11) меньше ноля. Если же корни больше нуля, стационарная точка функции Лагранжа является точкой минимума.
Пример: Предприятие выпускает два вида продукции в объемах . Они реализуются по ценам соответственно. По плану предприятие должно выпустить ровно 50 единиц продукции. Определить план производства, обеспечивающий наибольший доход.
Здесь функция ограничений
Построим функцию Лагранжа
Вычитая из второго уравнения первое, получим
Проверим достаточное условие оптимальности:
Угловые миноры матрицы, начиная с порядка 2m+1=3 должны иметь чередующиеся знаки, знак первого из них (положителен). Все эти условия выполняются:
Полученное решение – точка локального максимума.
Экономическая интерпретация множителей Лагранжа
Множитель Лагранжа – это двойственная переменная. Как и в линейном программировании, она показывает, на сколько изменится критерий при изменении правой части ограничений на единицу.
В рассмотренном примере . Следует ожидать, что при увеличении суммарного объема производимой продукции с 50 до 51 доход уменьшится на 6.66.
Проверим этот вывод. Пусть в нашей задаче критерий остался прежним, поменялась правая часть ограничения
.
Тогда условия стационарности выглядят следующим образом:
Стационарная точка
Приращение критерия
Для проверки достаточного условия оптимальности найдем корни многочлена, построенного из окаймляющей матрицы Гессе:
Корень отрицательный, значит это точка максимума функции.
Приращение функции -7.33 оказалось больше по модулю, чем ожидаемое приращение -6.66. Это объясняется нелинейностью целевой функции и тем, что производная отражает приращение функции только при бесконечно малом приращении аргумента.
Пусть исходная задача имеет вид:
Задача (11-13) называется задачей выпуклого программирования, если выполняются следующие условия:
Можно построить функцию Лагранжа:
Теорема 8: точка является оптимальным решением задачи выпуклого программирования тогда и только тогда, когда существует вектор такой, что для функции Лагранжа выполняются условия:
Условия (14) называются условиями Куна – Таккера.
В общем случае система уравнений и неравенств (14) слишком сложна для аналитического решения. Однако в задачах квадратичного программирования есть способы решения этой системы условий, сводящиеся к нахождению опорных решений систем линейных алгебраических уравнений.
Геометрический смысл условий Куна-Таккера:
Если все , , то условия дополняющей нежесткости запишутся в виде
(15)
то есть градиент функции в оптимальной точке является линейной комбинацией с положительными коэффициентами градиентов и активным ограничениям. Иными словами, градиент критерия лежит в геометрическом конусе градиентов ограничений.
Лабораторная работа 1. Изучение свойств области допустимых решений задачи линейного программирования.
1.1 По содержательному описанию экономической задачи построить математическую модель задачи линейного программирования. Привести задачу к канонической форме. В канонической форме модель должна содержать 4 ограничения и 6 переменных.
1.2 Найти все базисные решения с помощью диалоговой системы решения и анализа задач линейного программирования IBLP.
1.3 Решить задачу графически в пространстве двух произвольно выбранных свободных переменных. Произвести вручную необходимые для этого преобразования задачи к симметричной форме. Отобразить на графике все базисные решения, выделить среди них опорные.
1.4 Повторить все геометрические построения в пространстве двух других свободных переменных.
1.5 Пользуясь полученными графиками, сформулировать свойства области допустимых решений задачи линейного программирования. Объяснить, в каких случаях число базисных решений будет меньше теоретически возможного.
Лабораторная работа 2. Решение задачи линейного программирования симплекс-методом. Варианты разрешимости задачи.
2.1 По содержательному описанию экономической задачи построить математическую модель задачи линейного программирования.
2.2 Найти начальный опорный план методом вспомогательной задачи и оптимальное решение симплекс-методом вручную и в обучающем режиме работы диалоговой системы решения и анализа задач линейного программирования IBLP. Объяснить правила перехода от одной симплекс-таблицы к другой ( признак оптимальности, возможность улучшения плана, выбор переменных, вводимой и выводи-
мой из базиса).
2.3 Изменить условия задачи так, чтобы:
- задача имела единственное оптимальное решение;
- задача имела множество оптимальных решений. Записать его параметрически;
- задача была неразрешима из-за неограниченности целевой функции;
- задача была разрешима при неограниченности области допустимых решений;
- задача имела вырожденное оптимальное решение.
- задача была неразрешима из-за несовместности системы ограничений;
Сформулировать аналитические признаки указанных ситуаций. Дать геометрическую интерпретацию каждого варианта.
2.5 Для сгенерированной задачи линейного программирования с 10 ограничениями и 15 переменными в симметричной форме найти оптимальные решения задач максимизации и минимизации симплекс-методом в обучающем режиме работы диалоговой системы IBLP. В отчете привести количество итераций, общее время решения каждой задачи и среднее время, затраченное на одну итерацию.
Лабораторная работа 3. Теория двойственности в задачах линейного программирования.
3.1 По содержательной постановке экономической задачи построить математическую модель задачи линейного программирования.
3.2 Выбрать метод ( симплекс-метод, метод искусственного базиса или двойственный симплекс-метод ) и решить задачу с помощью диалоговой системы решения и анализа задач линейного программирования IBLP. Привести в отчете симплекс-таблицу полученного оптимального решения.
3.3 Дать экономическую интерпретацию полученного оптимального решения.
3.4 Построить двойственную задачу. Дать экономическую интерпретацию двойственной задачи.
3.5 Получить оптимальное решение двойственной задачи четырьмя способами:
- с помощью диалоговой системы IBLP;
- по второй теореме двойственности;
- через матрицу, обратную к базисной;
- из оптимальной симплекс-таблицы прямой задачи.
Сравнить полученные результаты.
3.5 Дать экономическую интерпретацию трех теорем двойственности.
Лабораторная работа 4. Послеоптимизационный анализ задач линейного программирования.
Выполнить послеоптимизационный и параметрический анализ задачи, поставленной и решенной в третьей лабораторной работе. Привести экономическую интерпретацию всех производимых изменений условий задачи.
4.1 Анализ чувствительности оптимального решения задачи к изменению свободных членов ограничений.
- Найти интервалы устойчивости двойственных оценок к изменению свободных членов ограничений.
- Найти оптимальные решения при конкретных изменениях свободных членов ограничений внутри и вне интервалов устойчивости.
- Найти область устойчивости двойственных оценок к одновременному изменению двух свободных членов ограничений. Построить эту область графически. Найти оптимальные решения при конкретных изменениях внутри и вне области.
- Поставить и решить с помощью диалоговой системы IBLP задачу анализа дополнительно закупаемых объемов ресурсов задачи объемного планирования с целью обеспечения наибольшей эффективности планирования.
4.2 Анализ чувствительности оптимального решения задачи к изменению коэффициентов целевой функции.
- Найти интервалы устойчивости оптимального решения к изменению коэффициентов целевой функции при базисных и свободных переменных.
- Найти оптимальные решения при конкретных изменениях коэффициентов внутри и вне интервалов устойчивости.
4.3 Анализ чувствительности оптимального решения задачи к изменению технологических коэффициентов.
- Найти интервалы устойчивости оптимального решения к изменению технологических коэффициентов при свободных переменных оптимального решения.
- Найти оптимальные решения при конкретных изменениях технологических коэффициентов внутри и вне интервалов устойчивости.
4.4 Определить оптимальное решение задачи при введении новой переменной.
4.5 Определить оптимальное решение задачи при введении нового ограничения.
Перечень задач к лабораторным работам 3 и 4
Задача №1
Для изготовления книжной полки требуется 3 листа древесной плиты размером 8020 см и 2 листа размером 6525 см.
Мастерская может закупить не более 20 листов древесной плиты размером 11 м по цене 400 рублей за лист. Книжная полка продается по цене 1000 руб. Дополнительные затраты на вспомогательные материалы и оплату работы оборудования составляют 200 руб. на каждую книжную полку.
Определить план работы мастерской, обеспечивающий максимальную прибыль.
Задача №2
Трамвайно-троллейбусное управление имеет потребность в водителях в различное время суток, указанную в таблице :
|
Время |
Потребность в водителях |
|
2–6 |
10 |
|
6–10 |
40 |
|
10–14 |
40 |
|
14–18 |
60 |
|
18–22 |
70 |
|
22–02 |
20 |
Каждый водитель работает 8 часов без перерыва и приступает к работе в начале какого-либо периода. Водителям, заступающим в период с 22 до 02 и с 2 до 6 часов, зарплата выплачивается в двойном размере.
Составить служебное расписание (указать число водителей, приступающих к работе в каждом периоде) с тем, чтобы требуемый фонд заработной платы был минимальным.
Задача №3
В состав рациона кормления ребенка входят 4 продукта-смеси "Малыш", "Крепыш", "Силач", "Бoгатырь", содержащие витамины А, В и С. Содержание витаминов (в условных единицах на 100 грамм) соответствующего продукта, минимальные нормы их потребления приведены в таблице:
|
Витамины Продукт |
А |
В |
С |
Стоимость 100г смеси |
|
"Малыш" |
10 |
4 |
2 |
3 |
|
"Крепыш" |
24 |
3 |
1 |
2 |
|
"Силач" |
36 |
2 |
1 |
5 |
|
"Богатырь" |
30 |
5 |
2 |
6 |
|
Нормы потребления |
100 |
17 |
8 |
Определить оптимальный рацион кормления ребенка из условия минимальной стоимости питания.
Задача № 4
Ткань 3-х артикулов производится на ткацких станках двух видов с различной производительностью. Для изготовления ткани используется натуральное и синтетическое волокно. В таблице указаны производительности станков по каждому виду ткани (м/ч), нормы расхода волокна (в кг на 1000м), прибыль от реализации одного метра ткани (руб. за 1м).
|
Вид ресурса |
Производительность станков и нормы расхода волокна |
||
|
1 арт. |
2 арт. |
3 арт. |
|
|
Станки 1 типа, (м/ч) |
20 |
40 |
25 |
|
Станки 2 типа, (м/ч) |
25 |
50 |
– |
|
Натуральное волокно, (кг/1000м) |
30 |
20 |
40 |
|
Синтетическое волокно, (кг/1000м) |
10 |
10 |
15 |
|
Прибыль, (руб./м) |
30 |
15 |
40 |
Ресурсы времени работы станков 2 и 5 тыс. часов соответственно. Запасы волокна 4т и 3т.
Определить оптимальный ассортимент продукции, производимой на станках каждого типа, максимизирующий прибыль предприятия.
Задача №5
В состав полиметаллических руд, добываемых на шахтах А,B,C входят свинец, цинк, медь. Содержание цветных металлов (в кг/т) в руде шахт и минимальные нормы добычи цветных металлов в день на горнодобывающем предприятии (в кг) даны в таблице:
|
Металлы Руда в шахте |
Свинец |
Цинк |
Медь |
|
А |
8 |
5 |
20 |
|
В |
12 |
15 |
6 |
|
С |
25 |
6 |
5 |
|
D |
10 |
4 |
9 |
|
Нормы добычи металлов, кг |
200 |
100 |
180 |
На добычу и переработку 1т руды затрачивается по шахтам соответственно 8, 5, 10, 15 тыс. рублей. Определить оптимальный дневной план добычи и переработки руды с точки зрения минимизации затрат.
Задача №6
Пять компонент: лимонный сок, малиновый сироп, клубничный сироп, коньяк и вода используются для получения четырех марок коктейлей в следующих пропорциях:
|
Коктейль"Клубничный" |
– 1:0:4:3:10 |
|
Коктейль"Mалиновый" |
– 2:5:0:4:8 |
|
Коктейль"Застольный" |
– 2:3:3:5:0 |
|
Коктейль"Лимонный" |
– 5:2:3:0:2 |
Коктейли продаются по цене соответственно 6руб., 8руб., 15руб., 5руб. за 0.1 литра.
Запасы лимонного сока составляют 10л, малинового сиропа 12л, клубничного сиропа 14л, коньяка 10л. Запасы воды не ограничены.
Определить план смешения компонент, обеспечивающий максимальный доход от продажи коктейлей.
Задача №7
Для обеспечения жаростойкости металлокерамических изделий, изготовляемых методом порошковой металлургии, используют различные виды смесей железа с концентратами из цветных металлов, таких как хром, никель, титан. Концентраты поступают с нескольких горнообогатительных комбинатов и имеют различное процентное содержание металлов, используемых для получения необходимых металлических порошков:
|
Металлы Комбинаты |
Хром |
Никель |
Титан |
|
1 |
30 |
10 |
60 |
|
2 |
– |
20 |
80 |
|
3 |
30 |
70 |
– |
Для обеспечения жаростойкости металлический порошок помимо железа должен содержать не менее 2% хрома, 5% никеля, 9% титана.
Затраты на оплату тонны концентрата, получаемого от поставщиков, равны соответственно 3, 1.5, 2 тыс. руб. В течение месяца требуется выпустить 1000т металлокерамики.
Определить объемы месячной закупки концентратов, чтобы стоимость выплат за это сырье была наименьшей.
Задача №8
Кондитерский цех для производства пяти сортов шоколада использует компоненты: какао-порошок, сахар, орехи, молоко соответственно в пропорциях
|
3:2:1:0; |
6:4:4:1; |
5:2:0:2; |
4:2:1:1; |
5:3:0:1 |
На смену цеху выделяется: какао-порошка 130 кг, сахара 110 кг, орехов 70 кг, молока 60 кг. Цена одного кг шоколада по сортам составляет 300, 100, 200, 400, 200 руб. соответственно.
Определить план работы цеха на смену, обеспечивающий максимальный доход.
Задача №9
Фирма рекламирует свою продукцию с использованием телевидения, радио, газет "Рекламный вестник" и "Биржа". Минута телевизионной рекламы стоит 1тыс рублей, минута радиорекламы 600 рублей, 1 кв. см рекламы в "Рекламном вестнике" – 2 рубля, в "Бирже" – 8 рублей.
Предшествующий опыт показывает, что минута телерекламы увеличивает сбыт продукции на 2 тыс. руб., 1 кв. см в "Рекламном вестнике" – на 5 руб., минута радиорекламы – на 1 тыс. руб., 1 кв. см в "Бирже" – на 30 руб. Месячный рекламный бюджет фирмы не может превосходить 10 тыс. руб. Телерадиокомпания выделяет на теле- и радиорекламу не более 10 минут в месяц. Руководство фирмы считает, что бюджет газетной рекламы не должен превосходить половины бюджета телерадиорекламы.
Определить рекламную политику фирмы на месяц, приносящую максимальную прибыль.
Задача №10
Для застекления 500 рам нового здания экономфака можно использовать стекла размером 120160 см.
Для застекления каждой рамы требуется 2 стекла размером 12070 см, одно – 7050, одно – для форточки – 6040.
Определить план раскроя стекла, минимизирующий отходы.
Задача №11
Мебельное производственное объединение планирует работу двух своих фабрик на месяц по производству мебельных гарнитуров трех марок: "Каприз", "Гармония" и "Аскет". На первой фабрике на производство одного гарнитура каждой из указанных марок требуется соответственно 10, 8, 4 нормо-смены. Технологическая оснащенность второй фабрики не позволяет выпускать гарнитуры "Гармония", а на производство гарнитуров "Каприз" и "Аскет" требуется соответственно 15 и 5 нормо-смены. Затраты фабрик на зарплату рабочим и обеспечение работы оборудования в течение нормо-смены составляют 400 и 300 рублей. Первая фабрика имеет 50 рабочих мест , вторая – 75.Фабрики работают в две смены по 30 рабочих дней в месяц. Расходы на приобретение материалов для одного гарнитура составляют 20, 15, 10 тыс. рублей соответственно.
Объединение может обеспечить производство материалами на сумму не более 15 млн. рублей в месяц. Гарнитуры реализуются по цене 30, 24 и 14 тыс. рублей соответственно.
Гарнитуров "Аскет" в месяц должно производиться не менее 50.
Определить месячный план работы производственного объединения из требования максимизации прибыли.
Задача №12
Для грузовых перевозок создается автоколонна. На приобретение автомашин выделено 6 млн. руб. Можно заказать машины 3-х марок – А, Б и В, характеризующиеся данными, приведенными в таблице. Количество машин не должно превышать 30, а общее число водителей в автоколонне должно быть не более 144 человек.
|
Марка машины |
Стоимость в тыс. руб. |
Количество водителей, обслуживших машину за смену |
Число рабочих смен в сутки |
Производительность машин за смену, т/км |
|
А |
100 |
1 |
3 |
2100 |
|
Б |
200 |
2 |
3 |
3600 |
|
В |
230 |
2 |
3 |
3700 |
Сколько машин каждой марки следует заказать, чтобы автоколонна имела максимально возможную производительность т/км в расчете на одни сутки? Считать, что каждая машина будет использоваться в течение всех 3-х смен, а водители будут работать по одной смене в сутки.
Задача №13
Для изготовления определенного сплава из свинца, цинка и олова используется сырье из тех же металлов, отличающееся составом и стоимостью
|
Сырье |
Содержание в процентах |
||||
|
Компоненты |
1 |
2 |
3 |
4 |
5 |
|
Свинец |
10 |
10 |
40 |
60 |
70 |
|
Цинк |
10 |
30 |
50 |
30 |
20 |
|
Олово |
80 |
60 |
10 |
10 |
10 |
|
Стоимость |
4 |
4.5 |
5.8 |
6 |
7.5 |
Определить, сколько нужно взять сырья каждого вида, чтобы изготовить с минимальной себестоимостью сплав, содержащий олова не более 40% и цинка не менее 20%.
Задача №14
Производственный участок изготавливает изделия И-1,И-2,И-3 для сборочного конвейера предприятия-заказчика. Минимальная потребность в них 30, 50, 40 шт. соответственно. Запасы металла на изделие И-1 ограничены, поэтому их можно производить не более 200 шт.
Все изделия последовательно обрабатываются на станках С-1, С-2, С-3. Технология изготовления первого изделия допускает три способа обработки, второго изделия – два способа. Нормы времени на обработку, плановая себестоимость и оптовые цены изделий приведены в таблице:
|
Изделия и способы обработки |
||||||
|
Показатели |
И-1 |
И-2 |
И-3 |
|||
|
1 |
2 |
3 |
1 |
2 |
||
|
Норма времени на обработку, часов: |
||||||
|
на С-1 |
3 |
7 |
0 |
8 |
4 |
3 |
|
на С-2 |
2 |
3 |
6 |
3 |
2 |
3 |
|
на С-3 |
7 |
5 |
6 |
0 |
3 |
6 |
|
Плановая себестоимость руб. |
13 |
15 |
11 |
20 |
24 |
10 |
|
Оптовая цена руб. |
16 |
25 |
20 |
Плановый фонд времени работы станков составляет для станков С-1 и С-2 по 6000 часов, для С-2 – 40000 часов.
Определить план работы производственного участка, приносящий максимальную прибыль.
Задача №15
Взаимозаменяемое оборудование молочного завода позволяет производить 3 типа молочной продукции – молоко, сметану, кефир. Мощности производственного цеха позволяют производить за смену 40т молока или 10т сметаны, или 30т кефира, или любую их линейную комбинацию. Мощности цеха расфасовки за смену могут обеспечить расфасовку 30т молока или 30т кефира, или 20т сметаны, или любую их линейную комбинацию. Завод должен за смену производить не менее 20т расфасованного молока. Прибыль от реализации 1т молока – 3 тыс. руб.
|
1т сметаны |
–10 тыс. руб. |
|
1т кефира |
– 2 тыс. руб. |
Определить план производства, максимизирующий прибыль.
Задача №16
Студенческий сельскохозяйственный отряд в составе 200 человек (100 юношей и 100 девушек), ежедневно может выполнять 4 вида работ: подбор картофеля за картофелекопалкой; перенос собранного картофеля и погрузка его в машины; погрузка машин в овощехранилище для отправки в город; обслуживание картофелеуборочных комбайнов. При подборе картофеля девушка собирает 10-килограммовое ведро за 4 минуты, юноша – за 5 минут. За час юноша может перенести и погрузить в машину 700 килограммов картофеля, девушка – 400 килограммов. В овощехранилище юноша за день может погрузить 8 тонн картофеля, девушка – 5 тонн. Картофелеуборочный комбайн должны обслуживать 4 человека. За день комбайн с женской бригадой убирает картофель с 2 га, с мужской 1.5 га. Урожайность картофеля в хозяйстве 12 тонн с гектара. В хозяйстве 5 картофелеуборочных комбайнов. Отряд может не обслуживать все или часть картофелеуборочных комбайнов, тогда эти комбайны комплектуются бригадами из местного населения. Для перевозки картофеля по всем видам работ хозяйство может выделить ежедневно не более 16 4-х тонных грузовых машин. При обслуживании ручного подбора картофеля одна машина делает в день не более 4-х рейсов, за картофелеуборочным комбайном – не более 6 рейсов. Перевозка картофеля из овощехранилища в город и возвращение в хозяйство занимает 2 часа. Оплата за тонну собранного в поле и погруженного в машину картофеля 1 тысяча рублей, за тонну отгруженного из овощехранилища картофеля – 110 рублей, за тонну собранного комбайном картофеля – 200 рублей.
Найти распределение студентов по видам работ, обеспечивающее максимальный дневной заработок отряда. Рабочий день отряда 8 часов.
Задача №17
Предприятие закупает необработанную нефть трех сортов А, B, С по цене соответственно 500, 400, 300 рублей за тонну. В результате очистки без потерь веса и смешения нефти разных сортов производится два вида смазочных масел, которые продаются по цене 500 и 600 рублей за тонну. Масло первого вида должно содержать не менее 10% нефти сорта А и не более 30% сорта В. Масло второго вида должно содержать не менее 20% нефти сорта А и не более 50% нефти сорта C. Оценка спроса показала, что продать можно не более 100 тонн масла первого вида и 200 тонн второго вида.
Определить план закупки нефти и производства смазочных масел, максимизирующий прибыль предприятия, если запасы необработанной нефти не ограничены.
Задача №18
Фирма А выпускает изделия Х и поставляет их по договорным обязательствам фирме В ежемесячно в количестве 1000 шт. Каждое изделие состоит из двух деталей У и трех деталей Z. Детали У и Z можно купить в фирме С по цене соответственно 2 руб. и 1 руб. за шт. в объеме не более 800 и 1000 в месяц.
Детали можно также изготовить из заготовок U и V, закупаемых в фирме D по цене 4 и 7 руб. Из каждой заготовки U фирма Е за 2 руб. может изготовить 3 детали У и 1 деталь Z, а из заготовки V за 5 руб. – 3 детали У и 5 деталей Z, за 3 руб. – 5 деталей У и 2 детали Z.
Определить месячный план деятельности фирмы А, обеспечивающий выполнение договорных обязательств с минимальными затратами.
Задача №19
Предприятие может работать по трем технологическим режимам. При этом расходуется и производится 3 вида продуктов.
По первому технологическому режиму за смену расходуется 2т первого, 4 куб.м второго продукта и производится 1 тыс.кв.м третьего продукта.
По второму режиму за смену расходуется 5т первого, 2 куб.м второго и 2 тыс.кв.м третьего.
По третьему режиму за смену производится 1т первого, 4 тыс.кв.м третьего и расходуется 3 куб.м второго продукта.
Запасы первого продукта составляют 80т, второго 100 куб.м. Третьего продукта должно быть произведено не менее 300 тыс.кв.м.
Каждая смена работы по технологическим режимам приносит доход соответственно 1, 1.5, 2 тыс. рублей.
Найти план работы предприятия, приносящий максимальный суммарный доход.
Задача №20
Предприятие может выпускать 5 типов деталей. Каждая деталь проходит обработку в трех цехах – механическом, термическом и гальваническом.
Производственные мощности механического цеха позволяют за смену обработать 3 тыс. деталей первого типа, 2 тыс. деталей – второго, 6 тыс. – третьего, 5 тыс. – четвертого или 4 тыс. пятого или любую их линейную комбинацию.
Мощности термического цеха позволяют за смену обработать 5 тыс. деталей первого типа, 6 тыс. деталей – второго, 3 тыс. – третьего, 4 тыс. – четвертого или 5 тыс. пятого или любую их комбинацию.
Производственные мощности гальванического цеха также позволяют обработать за смену соответственно 7, 10, 5, 9, 4 тыс. деталей или любую их линейную комбинацию.
Гальванический цех работает в 2 смены, механический и термический в три.
Доход от реализации деталей составляет соответственно 30, 40, 35, 20, 50 рублей за одну деталь.
Количество деталей второго типа должно быть не менее общего числа деталей третьего и пятого типов.
Найти месячный план работы предприятия, приносящий максимальный суммарный доход.
Задача №21
Под посев пшеницы, овса и гречихи отведено 2 земельных участка площадью 120 га и 150 га. В таблице указаны средняя урожайность каждой культуры на каждом участке, выручка в руб. за 1ц культуры и плановые задания по производству зерна.
|
Культура |
Урожайность |
Выручка |
Плановое задание |
|
|
1 уч. (ц/га) |
2 уч. (ц/га) |
(руб.) |
(ц) |
|
|
Пшеница |
17 |
15 |
300 |
1600 |
|
Овес |
12 |
20 |
150 |
1200 |
|
Гречиха |
10 |
15 |
200 |
1500 |
Определить, какую площадь на каждом участке следует отвести под каждую культуру для получения максимальной выручки.
Задача №22
Кондитерский цех выпускает торты "Нижегородский", "Киевский", "Ежик", "Полет". Для выпечки торта "Нижегородский" следует взять 6 частей муки, 4 части масла, 3 части яиц, 3 части сахара, 1 часть шоколада, 1 часть орехов. Для "Киевского" торта эти продукты берутся в частях: 3, 4, 5, 1, 2, 2. Для торта "Ежик": 7, 5, 4, 3, 1, 0. Для торта "Полет": 3, 5, 7, 4, 0, 2. Продукты покупаются по цене соответственно: 25, 130, 60, 30, 200, 150 рублей за килограмм. Торты реализуются по цене: 150, 200, 100, 250 рублей за килограмм. Ежедневные поставки в цех муки, масла и сахара не могут превосходить 300, 200, 100 килограмм. Тортов "Ежик" должно быть произведено не менее 200 килограмм. Определить ежедневный план работы цеха, приносящий максимальный доход.
Задача №23
Студенческий сельскохозяйственный отряд в составе 200 человек закупает продукты: хлеб, мясо, молоко, масло, картофель, сахар, яйца (1 яйцо весом 50г.) по цене соответственно:30 руб./кг; 200 руб./кг; 25 руб./л; 130 руб./кг; 20 руб./кг; 30 руб./кг; 30 руб./10 шт.
В таблице указано содержание белков, жиров, углеводов в 1 кг продукта и их калорийность.
|
Продукт |
Белки |
Жиры |
Углеводы |
Калорийность (ккал/кг) |
|
Хлеб г/кг |
60 |
10 |
450 |
2000 |
|
Мясо г/кг |
200 |
100 |
– |
1500 |
|
Молоко г/л |
50 |
40 |
50 |
600 |
|
Масло г/кг |
– |
800 |
– |
8000 |
|
Картофель г/кг |
20 |
– |
200 |
900 |
|
Сахар г/кг |
– |
– |
950 |
4000 |
|
Яйца г/кг |
120 |
110 |
10 |
1500 |
Суточная норма потребления белков, жиров и углеводов на одного человека составляет соответственно: 120, 140, 550. Калорийность рациона должна быть не менее 5000 ккал. Определить оптимальный план ежедневной закупки продуктов для отряда из условий минимальной стоимости. При необходимости ввести ограничения на потребление некоторых продуктов.
Задача №24
Каждая из трех деталей может производиться на каждом из двух станков. Производительность станков (дет./час) приведена в таблице:
|
Деталь Станок |
1 |
2 |
3 |
|
1 |
20 |
15 |
4 |
|
2 |
6 |
25 |
15 |
Изготовленные детали проходят обработку в гальваническом цехе. Мощности гальванического цеха могут обеспечить обработку 10тыс. деталей первого вида, 20 тыс. второго или 25 тыс. третьего, или любую их линейную комбинацию.
Фoнд времени работы станков составляет 80 и 120 часов. Себестоимость часа времени работы станков 50 и 40 рублей. Оптовая цена деталей соответственно 8, 5, 10 рублей.
Деталей второго вида необходимо выпустить не менее 2-х тысяч.
Найти план работы станков, обеспечивающий максимальную прибыль.
Задача №25
Студенческий сельскохозяйственный отряд в составе 200 человек удовлетворяет потребность в минеральных веществах за счет закупки хлеба, мяса, молока, масла, картофеля, сахара, яиц (1 яйцо весом 50г) по цене соответственно : 30 руб./кг, 200 руб./кг, 25 руб./л, 130 руб./кг, 20 руб./кг, 30руб./кг, 30 руб./10 шт. В таблице указано содержание минеральных веществ в миллиграммах на 100г продукта.
|
Продукты |
Натрий |
Калий |
Кальций |
Фосфор |
Магний |
Железо |
|
Хлеб |
583 |
206 |
38 |
156 |
49 |
2,6 |
|
Мясо |
60 |
315 |
9 |
198 |
21 |
2,6 |
|
Молоко |
50 |
146 |
121 |
91 |
14 |
0,1 |
|
Масло |
74 |
23 |
22 |
19 |
3 |
0,2 |
|
Картофель |
28 |
586 |
10 |
58 |
23 |
0,9 |
|
Сахар |
1 |
3 |
2 |
– |
– |
0,3 |
|
Яйца |
71 |
153 |
55 |
185 |
54 |
2,7 |
Суточные нормы потребления минеральных веществ на одного человека : натрия – 6г, калия – 5г, кальция – 1г, фосфора – 1.5г, магния – 0.5г, железа – 10мг.
Определить ежедневный план закупки отрядом продуктов из условия его минимальной стоимости. При необходимости ввести ограничения на потребление некоторых продуктов.
Задача №26
Студенческий сельскохозяйственный отряд в составе 200 человек удовлетворяет потребность в микроэлементах за счет закупки хлеба, мяса, молока, масла, картофеля, моркови, капусты, гречневой крупы по цене соответственно: 30руб./кг, 200руб./кг, 25руб./л, 130руб./кг, 20руб./кг, 35руб./кг, 20руб./кг, 40руб./кг.
В таблице указано содержание минеральных веществ в мкг на 100 г продукта.
|
Продукты |
Медь |
Марганец |
Цинк |
Хром |
Йод |
Фтор |
|
Хлеб |
260 |
1760 |
1400 |
5.3 |
5.6 |
35 |
|
Масло |
25 |
2 |
100 |
– |
– |
– |
|
Картофель |
140 |
170 |
360 |
– |
5 |
30 |
|
Морковь |
80 |
200 |
400 |
3 |
5 |
55 |
|
Капуста |
75 |
170 |
400 |
– |
3 |
10 |
|
Гречневая крупа |
640 |
1560 |
2050 |
4 |
3 |
23 |
|
Молоко |
12 |
6 |
457 |
2 |
16 |
30 |
Суточные нормы потребления микроэлементов на одного человека: меди – 2мг, марганца – 10мг, цинка – 20мг, хрома – 200мкг, йода – 150мкг, фтора – 1мг. Определить ежедневный план закупки продуктов отрядом из условия его минимальной стоимости. При необходимости ввести ограничения на потребление некоторых продуктов.
1 миллиграмм = 1000 микрограммов (1мг = 1000мкг)
Задача №27
Студенческий сельскохозяйственный отряд в составе 200 человек удовлетворяет потребность в витаминах за счет закупки хлеба, мяса, молока , картофеля, моркови, капусты, гречневой крупы, яблок, черной смородины по цене соответственно: 30руб./кг, 200руб./кг, 25руб./кг, 20руб./кг, 35руб./кг, 20руб./кг, 40руб./кг, 30руб./кг, 80руб./кг. В таблице указано содержание витаминов в мг на 100г продукта.
|
Продукты |
А (каротин) |
В1 (тиамин) |
В2 (рибофла-вин) |
РР (ниацин) |
С (аскорб. кислота) |
|
Хлеб |
– |
0.2 |
0.3 |
0.5 |
– |
|
Мясо |
0.01 |
0.1 |
0.2 |
5 |
– |
|
Молоко |
0.05 |
0.03 |
0.2 |
0.1 |
1 |
|
Картофель |
0.02 |
0.12 |
0.05 |
1 |
20 |
|
Морковь |
9 |
0.06 |
0.07 |
1 |
5 |
|
Капуста |
0.02 |
0.06 |
0.05 |
0.4 |
50 |
|
Гречневая крупа |
– |
0.5 |
0.25 |
4 |
– |
|
Яблоки |
01 |
0.01 |
0.03 |
0.3 |
30 |
|
Черная смородина |
– |
0.02 |
0.02 |
0.3 |
300 |
Суточные нормы потребления витаминов на одного человека А – 2мг, В1 – 2мг, В2 – 3мг, РР – 15мг, С – 100мг.
Определить ежедневный план закупки продуктов отрядом из условия его минимальной стоимости. При необходимости ввести ограничения на потребление некоторых продуктов.
Задача №28
Производственный комплект состоит из двух изделий первого вида и одного изделия второго вида. Каждое изделие может производиться на одном из трех типов предприятий. Каждое предприятие специализируется по производству только одного изделия.
В таблице указаны производственные мощности (в тыс. штук) и количество предприятий каждого типа.
|
Тип предприятия |
1 |
2 |
3 |
|
№ изделия |
|||
|
1 |
10 |
40 |
2 |
|
2 |
30 |
4 |
5 |
|
Число предприятий |
20 |
10 |
40 |
Определить, сколько предприятий и какого типа нужно специализировать на производстве какого изделия, чтобы получить максимальное число производственных комплектов. По производству первого изделия должно специализироваться не более 40 предприятий.
Задача №29
Определить оптимальное сочетание производства зерновых фуражных культур, овощеводства и молочного скотоводства. Затраты производственных ресурсов в расчете на 1ц продукции и их объем приведены и таблице:
|
Показатели |
Зерновые фуражные |
Овощи |
Молоко |
Объем ресурсов |
|
Пашня, га |
0.03 |
0.009 |
0.02 |
780 |
|
Трудовые ресурсы, чел.дни |
0.1 |
0.7 |
0.8 |
100000 |
|
Корма, ц кормовых единиц |
– |
– |
1.5 |
7200 |
Выход кормов с 1ц зерновых – 0.9 ц кормовых единиц, овощей – 0.03 ц кормовых единиц. Себестоимость 1 ц овощей 700 рублей, молока – 1000 рублей, зерновых фуражных – 300 рублей. Молока необходимо произвести не менее 2 тыс. ц. Критерий оптимальности – максимум прибыли. Молоко реализуется по цене 2000 рублей за ц, а зерновые и овощи, неиспользованные на корм могут быть реализованы по цене 800 и 1000 рублей соответственно. Запасы кормов, которые могут быть использованы сверх выращенных, составляют 7200 ц кормовых единиц.
Задача №30
Ткацкая фабрика выпускает ткань трех артикулов, получая шерстяную и хлопчатобумажную пряжу из шерсти и хлопка в прядильном цехе и производя готовую продукцию в ткацких цехах.
Месячные поставки шерсти составляют 10 тонн, хлопка – 20 тонн. Мощности прядильного цеха позволяют обработать в месяц 15 тонн шерсти или 30 тонн хлопка, или любую их линейную комбинацию.
Расход пряжи в килограммах на тысячу квадратных метров ткани каждого артикула приведен в таблице:
|
Пряжа \ Артикул |
I |
II |
III |
|
Шерстяная |
10 |
6 |
15 |
|
Х/б |
5 |
14 |
3 |
Фабрика закупает шерсть по цене 200 рублей за килограмм, хлопок – по цене 100 рублей. Ткань реализуется по цене соответственно 300, 200 и 400 рублей за квадратный метр.
Определить план работы фабрики, приносящий максимальный доход.
Задача №31
Для получения двух сплавов используется 3 металла: медь, цинк и никель. Цены за 1 кг. металлов составляют 800, 500, и 1000 рублей соответственно. Сплавы реализуются по цене 1500 и 2000 рублей за 1кг.
Первый сплав должен содержать не менее 10% никеля и не более 40% меди. Второй – не более 50% цинка.
Производственные мощности мастерской позволяют выпустить за планируемый период не более 1 тонны общего веса веса двух сплавов.
Найти производственный план работы мастерской, обеспечивающий максимальную прибыль.
Задача №32
Три типа деталей проходят обработку на трех станках. Технологический маршрут обработки каждой детали с указанием времени ее обработки на станках указан на рисунке (так, деталь 1 обрабатывается сначала на первом или втором станке, затем на третьем).
Фонд времени работы станков составляет соответственно 90, 30 и 100 часов. Детали реализуются по цене соответственно 40, 50, и 30 рублей. Оплата одного часа времени работы станков составляет 50, 150 и 100 рублей.
Составить план обработки деталей с целью максимизации прибыли.
Задача №33
Нефтеперерабатывающий завод использует 3 технологии перегонки нефти для производства бензина и олифы. По первой технологии из 1 тонны нефти производится 0.6 тонн бензина и 0.3 тонны олифы, при этом отходы составляют 0.1 тонны. По второй технологии – 0.3 т бензина, 0.5 т олифы и 0.2 т отходов. По третьей – 0.5 т бензина, 0.4 т олифы и 0.1 т отходов. На обработку одной тонны нефти по первой технологии требуется 0.5 машинного часа, по второй – 0.3 машинного часа, по третьей – 0.4 машинного часа. Ресурс оборудования составляет 100 машинных часов в сутки. Стоимость машинного часа работы оборудования составляет 6 тыс. рублей. Стоимость нефти – 11тыс. рублей за тонну. Бензин реализуется по цене 20 тыс. рублей за тонну, олифа – 30 тыс. рублей.
Все отходы должны пройти очистные сооружения, производительность которых 30 тонн в сутки. Суточный объем производства бензина должен быть не менее 120 тонн.
Составить суточный план производства с целью максимизации прибыли.
EMBED Equation.3 ( EMBED Equation.3 )
(32)
(31)
(30)
(29)
(27)
(28)
(26)
(34)
(35)
(36)
(17)
(18)
(19)
(14’)
(15’)
(16’)
(14”)
(15”)
(16)
(15)
(14)
(13)
(12)
(8)
(9)
(10)
(7)
(1)
(2)
(3)
(4)
(5)
(6)
(10’)
(11)
(2’)
(3’)
EMBED Equation.3 ( EMBED Equation.3 )
(14’)
(15’)
(16’)
(16”)
D
(1)
(2)
(3)
(37)
EMBED Equation.3 *
(20)
(21)
(22)
(23)
(24)
(25)
EMBED Equation.3
EMBED Equation.3
1
1
2
2
0
EMBED Equation.3
0
-6
2
2
5
EMBED Equation.3
-1
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
(4)
(5)
(6)
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
(7)
не угловая
EMBED Equation.3
EMBED Equation.3
(8)
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
(9)
(10)
(13)
(11)
(12)
(14)
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
(1)
(2)
(3)
(1)
(1’)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(1)
(2)
(3)
(1’)
(2’)
(3’)
(4)
(5)
(6)
(4’)
(5’)
(6’)
(8)
(9)
(10)
(12)
(13)
(16)
(14)
(11)
(12)
(9)
(10)
(7)
(8)
(7)
(8)
(13)
(1)
(2)
(3)
(1)
(4)
(5)
(6)
(15)
(2)
(3)
(4)
(5)
(10)
(11)
(9)
(15)
(1)
(18)
(17)
(5)
(1)
(2)
(3)
(4)
(7)
(2)
(1)
(2)
(4)
(6)
(7)
(5)
(3)
(8)
(9)
(10)
(11)
(11)
(12)
(13)
(14)
(1)
(2)
(4)
(5)
(2)
(3)
(6)
Глобальный экстремум
Локальный экстремум
х
D
f