1 Тема 3. Математическое программирование в экономике

2 Модель – это некоторый материальный или абстрактный объект, находящийся в определенном объективном соответствии с исследуемым объектом, несущий о нем определенную информацию и способный замещать его на определенных этапах исследования. Математическая модель (знаковая) – это модель объекта или системы, заданная в виде формул, функций, уравнении других математических соотношений. § 3.1. Задача линейного программирования

3 Классификация задач В зависимости от свойств условий и целевой функции задачи методы методы линейного программирования; методы целочисленного программирования; методы нелинейного программирования; методы динамического программирования; методы стохастического программирования; методы многокритериальной оптимизации; методы теории игр.

4 Структура методов принятия решений Целочисленность Принятие решения в условиях неопределенности Теория игр Нелинейное программирование Одно лицо Линейность Много- критериальная оптимизация Определенность Линейное программирование да Целочисленное программирование нет да нет да нет да Проблема принятия решения Одна цель нет

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

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

7 Пример (Построение оптимального плана производства) Исходные ресурсы Расход ресурсов на 1 тонну готовой продукции Запас ресурса Шоколад Конфеты Сахар 114 Какао 5210 Прибыль 53 геометрия. решение

8 Переменные: – суточный объем производства шоколада, – суточный объем производства конфет. Целевая функция: Общая прибыль от реализации суточного плана определяется функцией Ограничения: содержательно ограничения на запас ресурсов можно записать следующим образом

9 на расход сахара Математически ограничения имеют вид (см. таблицу): на расход какао-бобов на знак переменных Математическая модель ресурсы Расход ресурсов Запас ресурса Шоколад Конфеты Сахар 114 Какао 5210 Прибыль 53

10 Пример (Формирование смеси минимальной стоимости) Мука КукурузаСоевая Белок 0,090,6 Клетчатка 0,020,06 Стоимость 0,30,9 Фабрика ежедневно производит не менее 800 фунтов пищевой добавки – смеси кукурузной и соевой муки, состав которой представлен в таблице (в фунтах на фунт муки): Диетологи требуют, чтобы в пищевой добавке было не менее 30 % белка и не более 5 % клетчатки. Фирма хочет определить рецептуру смеси минимальной стоимости. геометр. решение

11 – количество кукурузной муки; Переменные: – количество соевой муки. Целевая функция: общая стоимость произведенной пищевой добавки Ограничения: на количество белка в пищевой добавке на количество клетчатки в пищевой добавке на количество производимой смеси на знак переменных Мука КукурузнаяСоевая Белок 0,090,6 Клетчатка 0,020,06 Стоимость 0,30,9

12 Математическая модель

13 Пример (Поиск оптимального плана производства) Автомобильная компания производит легковые автомобили и грузовики. Каждое транспортное средство должно обрабатываться в покрасочном и сборочном цехах. Если бы в покрасочном цехе обрабатывались только грузовые автомобили, то можно было бы покрасить 40 машин в день. Если бы обрабатывались только легковые автомобили, то выпуск составил бы 60 единиц продукции. В сборочном цехе обрабатывается 50 транспортных средств в день. Прибыль от производства одного легкового автомобиля и грузовика составляет $200 и $300 соответственно. Определить оптимальный ежедневный выпуск продукции, обеспечивающий максимальную прибыль компании. геометрия.решение

14 Переменные: – количество грузовиков, производимых ежедневно; – количество автомобилей, производимых ежедневно. Ограничения: на время использования покрасочного цеха где – время (в днях), идущее на покраску одного грузовика; – время (в днях), идущее на покраску одного автомобиля; на время использования сборочного цеха на знак переменных

15 Целевая функция: Суммарный доход компании определяется функцией Математическая модель

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

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

18 § 3.2. Геометрический метод решения задачи ЛП Пример Решим графически задачу из примера 3.1.1:примера Геометрический метод реализуется в два этапа: построение допустимого множества решений задачи ЛП; нахождение оптимального решения задачи ЛП.

19

20 Пример Решим графически задачу из примера 3.1.2:примера 3.1.2

21 Пример Решим графически задачу из примера 2.1.3:примера оптимальные (альтернативные) решения

22 Теорема (об оптимальных экстремальных точках). Если в задаче ЛП существует оптимальное решение, то существует и оптимальная экстремальная (угловая) точка. Алгоритм графического метода для задач ЛП : записать каждое ограничение как равенство и нарисовать прямую; найти для каждого ограничения допустимую область и множество допустимых решений задачи ЛП; найти градиент целевой функции нарисовать линию уровня целевой функции сдвигать линию уровня в направлении градиента, до последней точки пересечения с множеством доп. решений.

23 При решении задачи ЛП возможны случаи: 1. Задача ЛП имеет единственное решение (см. примеры и 2.4.2). 2. Задача ЛП имеет бесконечное множество решений (пример 2.4.3) (альтернативные решения). 3. Задача ЛП не имеет оптимального решения вследствие: a. неограниченности множества допустимых решений b. пустоты множества.

24 Анализ на чувствительность ограничения активные (связывающие) неактивные (несвязывающие) дефицитные ресурсы недефицитные ресурсы Первая задача на чувствительность: найти максимальное увеличение запаса дефицитного ресурса; Цели: найти максимальное уменьшение запаса не дефицитного ресурса.

25 Ресурс 1

26 Ресурс 2

27 Результаты решения первой задачи анализа на чувствительность оформляются в виде таблицы: Ресурс Тип (статус) ресурса Максимальное изменение запаса Максимальное изменение дохода Ресурс 1 дефицитный 15/3 Ресурс 2 дефицитный 1020/3 Вторая задача на чувствительность: теневая (двойственная) цена ресурса

28 Третья задача на чувствительность: целевая функция активные ограничения Диапазон оптимальности если

29 Кейс 1 (Торговля валютой) Арбитраж – получение прибыли в результате обменных операции. Таблица текущих обменных операций:

30 Пусть начальный валютный портфель содержит по одной единице каждого вида валют. количество валюты j, которое дают за единицу валюты i, Таблица (матрица) текущих обменных курсов: Математическая модель Переменные: количество валюты i, которое меняется на валюту j. Обменная операция

31 Цель: целью обменной операции является максимизация прибыли. Количественная мера прибыли выраженная в единицах валюты 1 (можно любую другую валюту). Целевая функция: Прибыль = Доход – Затраты стоимость портфеля, выраженная в единицах валюты 1, доход от валютной операции,

32 Ограничения: Пусть оптимальное решение, если арбитраж есть, арбитража нет. если

33 § 3.3. Симплекс-метод решения задачи ЛП. Стандартная задача максимизации Матричная и векторная форма записи

34 Стандартная задача минимизации Матричная и векторная форма записи

35 Каноническая задача максимизации (минимизации) Матричная и векторная форма записи

36 Эквивалентные преобразования. Нахождение максимума линейной функции эквивалентно нахождению минимума этой функции, взятой с противоположным знаком, и наоборот: Если на переменную не накладывается условие неотрицательности, то ее можно заменить разностью двух неотрицательных переменных:

37 Если имеется n таких переменных, то их можно заменить n+1 неотрицательной переменной: Ограничение типа неравенства можно представить в виде равенства, используя слабые переменные, следующим образом:

38 Ограничение типа равенства можно заменить двумя неравенствами: Если имеется m равенств, то их можно заменить m+1 неравенством: Знак неравенства можно заменить на противоположный, умножив данное неравенство на (-1)!

39 Пример Представить задачу ЛП в стандартной и канонической формах максимизации: каноническая задача максимизации:

40 стандартная задача максимизации:

41 Базисное решение системы линейных уравнений Пусть СЛУ AX =B совместна, т. е. выполнено условие:

42 Базисным решением СЛУ, зависящим от множества индексов, будем называть решение СЛУ, которое находится по указанным ниже правилам. привести данную систему, используя метод Гаусса, к диагональной форме по переменным: - базисные переменные взяв небазисные переменные, получим

43 Утверждение Если у системы линейных уравнений существует решение, то существует и базисное решение этой системы ЛУ. Утверждение Если задача ЛП имеет допустимое решение, то она имеет и допустимое базисное решение. Утверждение Если задача ЛП имеет оптимальное решение, то она имеет и оптимальное базисное решение.

44 Пример (неформальное решение ЗЛП симплекс-методом) Рассмотрим задачу ЛП : z-уравнение Преобразуем целевую функцию к виду:

45

46 Геометрическая интерпретация расчетов по симплекс-методу:

47 Перейдем к описанию формального алгоритма симплекс-метода для канонической задачи максимизации: Выполним ряд вспомогательных построений. По задаче ЛП запишем СЛУ, рассматривая целевую функцию как одно из ограничений (z-уравнение):

48 Приведем данную систему к диагональной форме по переменным:

49 Симплексная таблица представляет собой таблицу коэффициентов диагональной формы СЛУ, построенной для канонической задачи максимизации.

50 Классификация симплексных таблиц: симплексная таблица называется прямо-допустимой, если симплексная таблица называется двойств.-допусти- мой, если симплексная таблица называется оптимальной, если она одновременно и прямо-допустимая, и двойственно- допустимая. Оптимальная СТ соответствует оптимальному базисному решению.

51 Алгоритм прямого симплекс-метода (максимизация) 0. Начать вычисления с прямо-допустимой СТ.прямо-допустимой СТ. В противном случае в базис вводим переменную, номер которой находится по правилу: Если то текущее базисное решение является оптимальным. Столбец s называется ведущим столбцом СТ. 1. Проверка оптимальности или нахождение ведущего столбца СТ. ИТЕРАЦИЯ

52 2. Проверка условия неограниченности задачи ЛП или нахождение ведущей строки СТ. Если в ведущем столбце все коэффициенты В противном случае следует выводить из базиса переменную, для которой: Строка под номером r называется ведущей строкой СТ, 3. Преобразование СТ. то решение задачи неограниченно. ведущим элементом СТ,

53 ведущий столбец ведущая строка алгоритм

54 Пример Решим задачу из примера с помощью СТ: Составим диагональную форму для СЛУ

55 zx1x1 x2x2 s1s1 s2s2 z10001 s1s1 203/51-1/5 x1x1 212/501/5 Итерация 3. zx1x1 x2x2 s1s1 s2s2 z40/3005/32/3 x2x2 10/3015/3-1/3 x1x1 2/310-2/31/3 zx1x1 x2x2 s1s1 s2s2 z s1s s2s Итерация 2. Итерация 1. Оптимальное решение

пункты потребления производительность спрос Транспортная задача заключается в опре- делении плана перевозок, при котором удовлетворен спрос каждого потребителя, вывезен весь объем продукции из каждого пункта производства и при этом суммарные транспортные затраты минимальны. пункты производства удельные транспортные затраты § 3.4. Транспортная задача (ТЗ) Содержательная постановка:

, аналитический сетевой табличный Способы задания ТЗ

Пример пункты производства пункты потребления

Напишем математическую модель задачи: объем перевозок из A i в B j Переменные: Целевая функция: Ограничения: план перевозок двойственная задача

Математическая модель транспортной задачи Теорема (О разрешимости ТЗ) Для существования оптимального решения ТЗ, необходимо и достаточно, чтобы выполнялось условие баланса:

Закрытая ТЗ: Открытая ТЗ: фиктивный пункт потребления штраф спрос условие баланса перепроизводство

фиктивный пункт производства производительность Открытая ТЗ:

Методы нахождения начального опорного плана ТЗ. Опорным планом X транспортной задачи будем называть допустимое базисное решение ТЗ. Метод северо-западного угла

Метод минимального элемента

Метод Фогеля штрафы строк штрафы столбцов

Проверка плана ТЗ на опорность (метод вычеркиваний): вычеркнуть все строки в матрице Х, содержащие не более одного положительного элемента; в получившейся матрице вычеркнуть все столбцы, содержащие не более одного положительного элемента; далее процесс вычеркивания строк и столбцов применя- ется к оставшейся подматрице. Процесс заканчивается одним из двух исходов: 1. Все строки (столбцы) вычеркнуты. Тогда Х опорный. 2. Получена подматрица, в каждой строке (столбце) которой не менее 2 положительных элементов. Х не опорный. Из оставшихся элементов можно построить цикл.

Пример опорный план неопорный план

68 § 3.5. Постановка задачи нелинейного программирования. Задачей нелинейного программирования (задачей НП) называется задача нахождения максимума (минимума) нелинейной функции многих переменных, когда на переменные имеются (не имеются) ограничения типа равенств или неравенств. Стандартная форма В векторном виде:

69 Множество будем называть множеством допустимых решений ЗНП. Допустимое решение называется оптимальным решением задачи НП, если т.е. наибольшее значение функции f на множестве М. Число называется значением задачи НП. Будем полагать, что функции дифференцируемы, т.е. существуют все частные производные

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

71 Безусловный экстремум Если в задаче нелинейного программирования нет ограничений на переменные, то такая задача называется задачей безусловной оптимизации и имеет вид безусловная максимизация безусловная минимизация Теорема (Необходимые условия оптимальности) Если оптимальное решение задачи без ограничений, то (условие стационарной точки)

72 Замечание (Достаточность условий оптимальности) Для того чтобы стационарная точка являлась оптимальным решением задачи безусловной максимизации, достаточно, чтобы функция была вогнутой. Для того чтобы стационарная точка являлась оптимальным решением задачи безусловной минимизации, достаточно, чтобы функция была выпуклой.

73 Пример Написать необходимое условие оптимальности и найти стационарные точки: Условие стационарной точки:Достаточное условие: Матрица Гессе является положительно определенной, выпуклая функция, точка минимума.

74 Условный экстремум Пусть требуется найти при ограничениях Такая задача называется задачей условной максимизации (минимизации). Метод множителей Лагранжа функция Лагранжа вектор множителей Лагранжа задача безусловной оптимизации

75 Теорема (Лагранжа). Если – оптимальное решение задачи условной оптимизации, то должны найтись множители Лагранжа, которые удовлетворяют соотношениям условия Лагранжа Замечание В теореме векторы-градиенты функций должны быть линейно независимы в точке X *, т. е. удовлет- ворять условиям регулярности.

76 Замечание (Достаточность условий оптимальности). Для того чтобы точка являлась оптимальным решением задачи условной максимизации, достаточ- но, чтобы функция была вогнутой, а все линейными. Для того чтобы точка являлась оптимальным решением задачи условной минимизации, достаточ- но, чтобы функция была выпуклой, а все линейными.

77 Пример Написать необходимые условия оптимальности для задачи: Функция Лагранжа: Условия Лагранжа:

78 Условия Куна – Таккера для задачи НП. Задача нелинейного программирования вида называется стандартной ЗНП максимизации. Задача нелинейного программирования вида называется стандартной ЗНП минимизации.

79 Теорема (Куна – Таккера). Если – оптимальное решение стандартной задачи максимизации нелинейного программирования, то должны найтись такие множители Лагранжа, которые удовлетворяют следующим соотношениям: а) условия допустимости: б) условия оптимальности: в) условия трансверсальности: условия Куна-Таккера

80 Замечание (Достаточность условий оптимальности). Для того чтобы точка являлась оптималь- ным решением стандартной ЗНП максимизации, доста- точно, чтобы функции и были вогнутыми. Для того чтобы точка являлась оптималь- ным решением стандартной ЗНП минимизации, доста- точно, чтобы функции и были выпуклыми.

81 Пример при условиях Решение. Оптимальное решение: