Исследование операций и методы оптимизации

Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет промышленных технологий и дизайна» В. В. ПОТИХОНОВА Исследование операций и методы оптимизации Конспект лекций Утверждено Редакционно-издательским советом университета в качестве учебного пособия Санкт-Петербург 2021 УДК ББК П Р е ц е н з е н т ы: кандидат физико-математических наук, доцент кафедры прикладной математики ФГБОУ ВО «ГУМРФ» имени адмирала С. О. Макарова А. А. Денисова; кандидат технических наук, доцент кафедры интеллектуальных систем и защиты информации СПбГУПТД О. Б. Тѐрушкина П Потихонова, В. В. Исследование операций и методы оптимизации. Курс лекций: учеб. пособие / В. В. Потихонова.– СПб.: ФГБОУВО «СПбПГУТД», 2021. – …...с. ISBN В учебном пособии дано краткое изложение основных методов оптимизации и исследования операций в экономике. Описаны различные модели математического программирования – линейного, нелинейного и динамического программирования. Теоретический материал иллюстрируется рассмотрением задач с подробным решением и необходимым методическим сопровождением. Дисциплина «Исследование операций и методы оптимизации» предназначена для формирования у студентов знаний, необходимых для разработки и практического применения методов эффективного управления различными организационными системами. Предназначено для студентов направления подготовки 09.03.03 – Прикладная информатика. УДК ББК ISBN © ФГБОУВО «СПбГУПТД», 2021 © Потихонова В. В., 2021 СОДЕРЖАНИЕ Введение……………………………………………………………………… …..5 Раздел 1. Линейное программирование………………………………………9 Тема 1. Теоретические основы методов линейного программирования. Векторные пространства……………………………………………………..….. 9 1.1. Понятие п-мерного вектора ……………………………………… ….…9 1.2. Линейная зависимость и независимость векторов………………….….12 1.3. Векторная форма системы линейных уравнений ……………………...13 1.4. Теоремы о векторах п-мерного векторного пространства ………….….16 1.5. Ранг и базис системы векторов п-мерного пространства ……………..17 1.6. Выпуклые множества в п-мерном пространстве………………………...22 Тема 2. Математические модели экономических задач……………………….25 2.1. Основные понятия и определения……………………………………… 25 2.2. Основные теоремы линейного программирования…………………….29 2.3. Примеры задач линейного программирования…………………………30 Тема 3. Геометрическая интерпретация задачи линейного программирования……………………………………………………………….34 Тема 4. Симплексный метод…………………………………………………….39 4.1 Сущность симплекс-метода, алгоритм, симплексные таблицы………..39 4.3. М-метод……………………………………………………………………45 Раздел 2. Специальные задачи линейного программирования………….47 Тема 5. Теория двойственности в операционном анализе экономических систем………………………………………………………………………….…47 5.1. Экономическая интерпретация двойственных задач…………………...47 5.2. Общие правила составления двойственных задач……………………..50 5.3. Основная теорема двойственности…………………………………… .52 Тема 6. Операционные модели транспортного типа………………………….56 6.1. Экономико-математическая модель транспортной задачи……………..56 6.2. Построение начального плана……………………………………………60 6.3. Критерий оптимальности решения ТЗ. Метод потенциалов…………...65 6.4. Методы улучшения неоптимального плана……………………………...67 6.4. Особенности решения ТЗ с неправильным балансом…………………..70 Раздел 3. Нелинейное программирование…………………………….……72 Тема 7. Основные понятия и модели нелинейного программирования….…72 3 7.1. Постановка задачи нелинейного программирования……………………72 7.2. Необходимое и достаточное условие существование экстремумов……75 7.3. Графический метод решения задач нелинейного программирования…79 Тема 8. Классические методы оптимизации……………………………………87 8.1. Задача безусловной оптимизации…………………………………………..87 8.2. Метод множителей Лагранжа……………………………………………..88 Тема 9. Модели выпуклого программирования………………………………...92 9.1. Выпуклые функции…………………………………………………………..93 9.2. Теорема Куна-Таккера……………………………………………………….97 Раздел 4. Динамическое программирование……………………………….101 Тема 10. Общая остановка задачи динамического программирования……………………………………………………………….101 10.1. Принцип Беллмана……………………………………………………… 104 10.2. Уравнение Беллмана……………………………………………………. 105 4.2. Задача о выборе кратчайшего пути…………………………………….. 107 4.3. Задача о распределении средств между предприятиями……………….111 Заключение………………………………………………………………….…..118 Библиографический список………………………………………….…….…118 4 ВВЕДЕНИЕ Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Первые публикации по исследованию операций относятся к 40-м годам ХХ века, в которых методы применены для решения военных задач, в частности, для анализа и исследования военных операций. Отсюда и пошло название дисциплины. Среди первых исследований в области экономики может быть названа работа Л. В. Канторовича «Математические методы организации и планирования производства», вышедшая в 1939 г. Интенсивные исследования в этой области начались лишь в конце сороковых годов, когда американским математиком Д. Данцигом был построен изящный алгоритм симплексного метода для линейных программ. В пятидесятые годы в работах Г. Куна, А. Таккера, Г. Зойтендейка, Л. Гурвица и других получают развитие методы нелинейного программирования. В 1957 г. появляется монография выдающегося американского математика Р. Беллмана, положившая начало одному из оригинальных методов исследования многошаговых процессов принятия решений – методу динамического программирования. Большой вклад в развитие методов оптимизации подобных задач внесла группа советских математиков во главе с Л. С. Понтрягиным. За выдающийся вклад в разработку теории оптимального использования ресурсов в экономике академику Л. В. Канторовичу вместе с профессором Т. Купмансом (США) в 1975 году присвоена нобелевская премия. Следует отметить, что до сих не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Чаще всего дается такое определение: исследование операций – это комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений при проведении операций. Под термином операция понимают систему управляемых действий, объединенных единым замыслом и направленную на достижение определенной цели. Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это: 1. Постановка задачи. 5 2. Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия. 3. Построение математической модели, т. е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат. 4. Решение задач, сформулированных на базе построенной математической модели. 5. Проверка полученных результатов на их адекватность природе изучаемой системы, и возможная корректировка первоначальной модели. 6. Реализация полученного решения на практике. Под математической моделью явления или процесса понимают совокупность формул, уравнений, неравенств и т.д., отражающую существенные черты этого явления или процесса. При создании математических моделей для исследования операций первоочередной задачей является определение параметров, однозначно описывающих операцию. Эти параметры обычно подразделяют на контролируемые (или управляемые), неконтролируемые и целевые. Контролируемые (управляемые) параметры x1 , x2 , ...., xn являются переменными, принимающими чаще всего числовые значения, которым можно  придавать значения по своему усмотрению. Вектор X  x1 , x2 ,..., xn  иногда называют вектором управлений. Неконтролируемые параметры (обозначим их 1 ,  2 ,... ) нельзя менять по своему усмотрению, они характеризуют определенные свойства операции, иными словами это - условия проведения операций. Наконец, целевые параметры характеризуют эффективность операции. Это могут быть общая величина прибыли, получаемой при реализации продукции, или общие затраты, связанные с производством, и т.п. Математическая модель операции должна связывать контролируемые и неконтролируемые параметры с целевыми параметрами. Для построения математической модели необходимо иметь строгое представление о цели 6 функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений управляемых параметров. Примеры операций Пример 1. Предприятие выпускает несколько видов изделий, при изготовлении которых используются ограниченные ресурсы различного типа. Требуется составить план выпуска изделий на месяц, т.е. указать количество выпускаемых изделий каждою вида, так, чтобы максимизировать прибыль при выполнении ограничений на потребляемые ресурсы. Пример 2. Планируется деятельность нескольких промышленных предприятий на очередной год. Требуется распределить выделяемые средства (капиталовложения) между предприятиями таким образом, чтобы получить максимальную суммарную прибыль. Пример 3. Требуется организовать строительство магазина. При этом необходимо указать порядок выполнения работ во времени и распределить требуемые ресурсы между работами так, чтобы завершить строительство вовремя и минимизировать его стоимость. В настоящем курсе рассматриваются задачи об использовании ресурсов (планирование производства), об использовании мощностей (загрузке оборудования), транспортная задача и др., в которых требуется найти решение, когда критерий эффективности (например, прибыль, выручка, затраты ресурсов и т.п.) принимает максимальное или минимальное значение. Критерий эффективности, выражаемый некоторой функцией, называемой целевой, как уже говорилось выше, зависит от параметров обеих групп, поэтому целевую функцию Z можно записать в виде Z  f x1 , x2 ,..., 1 ,  2 ... . Все модели исследования операций могут быть квалифицированы в зависимости от природы и свойства операций, характера решаемых задач, особенности применения математических методов. Рассматриваемые далее задачи относятся к классу оптимизационных задач. Такую задачу можно сформулировать в общем виде: найти переменные  x1 , x2 , ...., xn (вектор X  x1 , x2 ,..., xn  ) , удовлетворяющие системе неравенств (уравнений) 7 i x1 , x2 ,...., xn   bi , i  1, 2, ..., m (0.1) и обращающие в максимум (или минимум) целевую функцию, т.е. Z  f x1 , x2 ,..., 1 ,  2 ...  max(min) . (0.2) Условие неотрицательности переменных, если они есть, входят в ограничения (0.1). Учет специфики конкретных операций определяет разнообразные оптимизационные экономико-математические модели. Однако для некоторых часто повторяющихся ситуаций разработаны общие методы построения моделей. Исторически и содержательно наибольший интерес представляют линейные модели, т. е. те модели, в которых целевая функция и уравнения связи являются линейными функциями. Широкое распространение в экономике линейных моделей (или, как еще говорят, линейного программирования) связано, во-первых, с тем, что многие экономические операции с достаточной точностью могут быть описаны линейными моделями; во-вторых, за небольшим исключением только для этих моделей разработаны эффективные методы численного решения при приемлемой для практики размерности задачи. Примерами использования линейных моделей могут служить модели комплексного использования сырья, транспортная, размещения производства, перспективного планирования, развития экономического комплекса, различных ситуаций оперативного управления и т. д. Широко применяются такие модели и в связи с необходимостью анализа ситуаций, возникающих в экономике из-за большого числа возможных вариантов функционирования конкретного объекта при использовании различных видов сырья, материалов, технологий и других факторов. 8 Раздел 1. Линейное программирование Тема 1. Теоретические основы методов линейного программирования. Векторные пространства В этом разделе мы кратко рассмотрим математические основы линейного программирования, такие как теория выпуклых множеств, понятие N-мерного вектора, линейных векторных пространств. 1.1. Понятие п-мерного вектора Из курса аналитической геометрии известно, что в фиксированной системе координат каждый вектор A однозначно определен своими координатами: вектор, расположенный на числовой оси, определяется координатой A (х), т. е. одним действительным числом. Таким образом, прямая – одномерное векторное пространство. Всякий вектор A , расположенный на плоскости с заданной системой координат, определяется двумя координатами или компонентами: A = (х; у) ( A  a1 ;a2  ), т. е. упорядоченной системой из двух действительных чисел. Плоскость является двумерным векторным пространством. Всякий вектор A трехмерного векторного пространства определяется тремя координатами: A = (х; у; z) ( A  a1 ; a2 ; a3  ), т. е. упорядоченной системой из трех действительных чисел. В экономике, физике, геометрии приходится изучать объекты, для задания которых недостаточно трех действительных чисел. Пусть, например, некоторый промышленный район производит станки, хлопчатобумажные ткани, автомобили, телевизоры, шерстяные изделия и т. д. Для характеристики производства района, очевидно, потребуется упорядоченная система из n действительных чисел. Таким образом, целесообразно рассмотреть совокупности всевозможных упорядоченных систем из n действительных чисел. Обобщим понятие вектора следующим образом. Определение 1. Любая упорядоченная последовательность из п действительных чисел a1 , a2 ,...., an представляет собой п-мерный вектор A , который можно записать в виде A  a1 ; a2 ;..., an   a1     a2  или A    ,   a   n 9 где a i - координата вектора; п - размерность вектора. Замечание. Координаты п-мерного вектора удобнее обозначать одной буквой, но с разными индексами (в отличие от трехмерного вектора), а сам вектор – той же заглавной буквой. Для п-мерных векторов вводятся понятия равенства, операции сложения, вычитания, умножения на скаляр, так же, как и для трехмерных векторов. Напомним, что сложение векторов и его умножение на число называют линейными операциями над векторами.  Два вектора A u B с одним и тем же числом компонент  B  b1 , b2 , bn  будем считать равными в том A  a1 ; a2 ;..., an  , случае, когда a1  b1 ; a2  b2 ; ......., an  bn . Равенство обозначается обычно A  B .  Суммой векторов A u B называется вектор A  B  a1  b1 , a2  b2 , ...., an  bn .  Произведение вектора A на число: kA  ka1 , ka2 , ..., kan ; k  число.  Роль нуля играет нулевой вектор  0,0,...,0 .  Вектор  1A называется противоположным вектору A и обозначается  A  A   a1 ;a2 ;..., an  . Определение 2. Множество всех п-мерный векторов с действительными компонентами, для которых введено понятие линейных операций, называется п-мерным векторным пространством и обозначается R n . Подчеркнем тот факт, что непосредственный геометрический смысл имеют лишь пространства R1 , R 2 , R 3 . Пространство R n при n  3 – чисто математический объект. Вместе с тем этот объект очень удобен для описания реальных процессов, в том числе экономических. Как известно из геометрии, если векторы A и B заданы своими координатами,  т. е. A  a1 ; a2 ; a3  и B  b1 , b2 , b3  , то их скалярное произведение A  B  a1b1  a2 b2  a3b3 . По аналогии:  Скалярным произведением п-мерных векторов A и B называется число A  B  a1b1  a2 b2  ...  an bn . Скалярное произведение имеет экономический смысл. Если A  a1 ; a2 ;..., an   есть вектор объемов различных товаров, а B  b1 , b2 , b3  – вектор их цен, то их скалярное произведение A  B выражает суммарную стоимость этих товаров. 10  Свойства скалярного произведения: 1. A  B  B  A 2. A  B  C   A  B  A  C 3. kA   B  k A  B  4. A  A  0, если А  ненулевой вектор; А  А  0, если А  нулевой вектор. Определение 3. Векторное п-мерное пространство, в котором введено понятие скалярного произведения, удовлетворяющее указанным свойствам, называется евклидовым пространством. Вектор называется нормированным, если длина его равна единице. Каждый ненулевой вектор A можно нормировать, т.е. умножить на такое число k , чтобы вектор kA был нормированным. В самом деле, при k  1 / A : 1 1 A  A  1. A A  Два вектора называются ортогональными, если их скалярное произведение равно нулю. В случае R 3 ортогональность векторов A и B означает перпендикулярность вектора A к вектору B . Векторы e1 , e2 ,..., en п-мерного евклидова пространства образуют ортонормированный базис, если эти векторы попарно ортогональны, и длина каждого из них равна единице. Таким базисом в трехмерном пространстве R 3 являются орты координатных    осей – векторы i , j , k . Рассмотрим линейное уравнение, содержащее п неизвестных: a1 x1  a2 x2  ...  an xn  b . Левая часть этого уравнения – линейная функция от п неизвестных Z  a1 x1  a2 x2  ...  an xn и может быть представлена в виде скалярного произведения векторов Z  A  X , где A  a1 ; a2 ;..., a n  , X  x1 ; x2 ;..., xn  . Линейная функция от неизвестных x1 ; x2 ;..., xn вполне определяется вектором A из своих коэффициентов, и, наоборот, всякий п-мерный вектор однозначно определяет некоторую линейную функцию. Исходя из этого, сложение и умножение вектора на число превращаются в операции над 11 линейными функциями, которые широко используются при решении задач математического программирования. 1.2. Линейная зависимость и независимость векторов Одним из важных понятий линейной алгебры является понятие линейной зависимости. Сначала заметим следующее: если при рассмотрении некоторого вопроса приходится иметь дело с несколькими векторами, то, как правило, их обозначают одной и той же буквой, но с различными индексами, например, A1 , A2 ,..., Am . Весь такой набор векторов называют системой векторов.  Определение 1. Пусть даны векторы A1 , A2 ,..., Am из R n . Любой вектор A вида A = k1 A1  k2 A2  ...  km Am - называется линейной комбинацией векторов Ai с коэффициентами k1 , k 2 ,..., k m (какие угодно числа) m (или коротко k A i 1 i i ). При наличии последнего равенства также говорят, что вектор A линейно выражается через векторы A1 , A2 ,..., Am или, что A разлагается по векторам A1 , A2 ,..., Am .  Определение 2. Векторы A1 , A2 ,..., Am называются линейно зависимыми, если линейная комбинация равна нулю k1 A1  k 2 A2  ...  k m Am  0 при условии, что хотя бы один из коэффициентов k1 , k 2 ,..., k m отличен от нуля.  Определение 3. Векторы A1 , A2 ,..., Am называются линейно независимыми, m если линейная комбинация равна нулю k A i 1 i i  0 только при условии, что все числа k1  k 2  ...  k m  0 . Пусть теперь задан еще п-мерный вектор B , он равен некоторой линейной комбинации векторов A1 , A2 ,..., Am , т.е. найдется такой набор чисел l1 , l2 ,..., l m , что B = l1 A1  l2 A2  ...  l m Am . В этом случае будем говорить, что вектор B разлагается по векторам 12 A1 , A2 ,..., Am . Числа l1 , l2 ,..., l m в разложении называются коэффициентами A1 , A2 ,..., Am . разложения вектора B по системе Разложение B  k1 A1  k 2 A2  ...  k m Am считается отличным от разложения B  l1 A1  l 2 A2  ...  l m Am , если различна, хотя бы одна пара соответствующих коэффициентов разложения. Перечислим ряд свойств линейной зависимости. 1. Система из одного вектора A линейно зависима, если A =0. 2. Если система векторов A1 , A2 ,..., Am линейно зависима, то хотя бы один из векторов этой системы разлагается по остальным. Пусть k i  0 , тогда Ai  k1 k k k k A1  2 A2  ...  i 1 Ai 1  i 1 Ai 1  ...  m Am . ki ki ki ki ki Т. е. один из векторов системы A1 , A2 ,..., Am разложен по остальным векторам этой системы. 3. Верно и обратное: система, содержащая более одного вектора, линейно зависима тогда и только тогда, когда среди данных векторов имеется такой, который линейно выражается через остальные. 4. Если часть системы линейно зависима, то и вся система линейно зависима. 5. Если система A1 , A2 ,..., Am линейно независима, но при прибавлении к ней еще одного вектора A становится линейно зависимой, то вектор A линейно выражается через векторы A1 , A2 ,..., Am . Теорема. В пространстве R n любая система из т векторов, где m>n линейно зависима. Если вектор B и система векторов A1 , A2 ,..., Am – произвольные векторы, то задача разложения вектора B по системе векторов A1 , A2 ,..., Am , как будет показано далее, сводится к решению системы линейных уравнений. 1.3. Векторная форма системы линейных уравнений Используя введенные операции над векторами, запишем систему линейных уравнений в векторной форме 13 a11 x1  a12 x2  ...  a1n x n  b1  a21 x1  a22 x2  ...  a2 n x n  b2  . . . . . . . . . . . . . . . . . . . . . . . . . . . a m1 x1  a m 2 x2  ...  a mn x n  bm Обозначим через A1 , A2 ,..., An (1.1) столбцы коэффициентов при неизвестных x1 , x2 ,..... x n , через B столбец свободных членов системы уравнений, т. е.  a1n   a11   a12   b1           a2n   a 21   a 22   b2  A1   ; A  ; .... ; A  ; B  2 n                 a  a  b  a   m1   m2   m  mn  Теперь систему уравнений (1.1) можно записать в виде A1 x1  A2 x2  ....  An xn  B. (1.2) Последнее уравнение называется векторной формой системы линейных уравнений. Его называют также просто системой линейных уравнений. Последовательность чисел k1 , k 2 ,...., k n  является решением уравнения (1.2), если A1k1  A2 k 2  ....  An k n  B – верное векторное равенство. Таким образом, для разложения вектора B по системе A1 , A2 ,..., An достаточно найти решение системы линейных уравнений A1 x1  A2 x2  ....  An xn  B , а для доказательства линейной независимости векторов какое-нибудь A1 , A2 ,.... , An надо показать, что однородная система A1 x1  A2 x2  ....  An xn  0 имеет только нулевые решения. Пример. Дана система векторов A1 , A2 , A3 , A4 и вектор B : 1  0   1 1    1           A1   0 ; A1   2 , A3   5 , A4   2 , B   7  .  2  2 3   4 5            Разложить вектор B по системе векторов A1 , A2 , A3 , A4 . Решение. Найдем общее решение системы линейных уравнений методом Гаусса. Замечание. Решение систем линейных уравнений методом Гаусса (последовательных исключений) рассматривалось в основном курсе математики. 14 A1 x1  A2 x2  A3 x3  A4 x4  B . Представим систему в виде расширенной матрицы:  1 0  1 1  1   0 2 5 2 7  2 2 3 4 5    Прибавим к последней строке первую, предварительно умноженную на -2:  1 0  1 1  1   0 2 5 2 7  , 0 2 5 2 7    Из последней строки вычтем вторую:  1 0  1 1  1   0 2 5 2 7  0 0 0 0 0    И, наконец, вторую строку поделим на 2:  x1  x3  x 4  1 1 0 1 1 1     5 7  0 1 5 / 2 1 7 / 2  или  0 0 0 0 0   x2  2 x3  x 4  2   Переменные x1 и x 2 называются разрешенными (или основными), а x3 и x 4 – свободными переменными. Система имеет бесчисленное множество решений. Выразив разрешенные переменные через свободные, получим общее решение системы:  x1  1  x3  x4  .  7 5  x2  2  2 x3  x4 Если свободные неизвестные x3 и x 4 положить равными нулю, то для 7 2 разрешенных неизвестных получим значения x1  1, x2  . Следовательно, 7 A2  0 A3  0 A4 . 2 Если x3  x4  1 , то x1  1, x2  0 и тогда получим еще одно разложение вектора B   A1  B   A1  0 A2  A3  A4 . Замечание. Если система состоит из п векторов п-мерного линейного векторного пространства R n , то для того чтобы векторы A1 , A2 ,..., An в R n были линейно независимыми, необходимо и достаточно, чтобы определитель, составленный из координат векторов, не был бы равен нулю (   0 ). 15 1.4. Теоремы о векторах п-мерного векторного пространства  Теорема 1. В п-мерном линейном векторном пространстве существует система из п линейно независимых векторов. Rn Рассмотрим следующую систему из п единичных п-мерных векторов: 1   0  0        0 1   0 E1   ; E 2   ; ... E n              0  0 1        Эта система называется системой единичных векторов n-мерного векторного пространства (называемых также ортами по аналогии с системой ортов трехмерного пространства). Покажем, что они линейно независимы. Не нарушая общности доказательства, положим п = 4 и вычислим определитель, составленный из координат векторов: 1  1 1 1 0, 1 т. О. векторы линейно независимы. *) Напомним, что диагональный определитель равен произведению элементов, стоящих на главной диагонали.  Теорема 2. Любая совокупность n  1 векторов п-мерного пространства линейно зависима.  Определение. Размерность пространства – это максимальное число содержащихся в нем линейно независимых векторов.  Определение. Любая совокупность п линейно независимых векторов пмерного пространства R n называется базисом. Система единичных векторов образует один из базисов n-мерного векторного пространства называется ортонормированным базисом. 16  Теорема 3. Каждый вектор A линейного пространства R n можно представить и притом единственным способом в виде линейной комбинации векторов базиса. Пример. Вектор A  3;2; 4;5 можно записать как линейную комбинацию единичных векторов E1  1; 0; 0; 0; E2  0;1; 0; 0; E3  0; 0;1; 0; E4  0; 0; 0;1 коэффициентами, которые равны компонентам вектора A : A = 3 E1 -2 E 2 + 4 E 3 -5 E4 = (3;-2,4;-5). 1.5. Ранг и базис системы векторов п-мерного пространства  Определение. Рангом r  системы векторов A1 , A2 ,..., Am называется максимальное число линейно независимых векторов данной системы. Т. О. базис системы векторов A1 , A2 ,..., Am – это линейно независимая часть системы векторов, например, векторы B1 ; B2 ; .....Br , входящие в систему. Следовательно, остальная часть системы A1 , A2 ,..., Am разлагается по векторам B1 ; B2 ; .....Br . Ранее показано, что диагональная система п-мерных векторов 1   0  0        0 1   0 E1   ; E 2   ; ... E n    линейно независима.           0  0 1         Теорема 4. Если диагональная система векторов является частью системы п-мерных векторов A1 , A2 ,..., Am , то эта диагональная система является базисом системы векторов.  Теорема 5. Каждый вектор системы A1 , A2 ,..., Am единственным образом разлагается по векторам ее базиса. 1  0  3        Пример. Показать, что векторы A1  1 ; A2  1  ; A3    2  образуют базис и  2   1 2        3   выразить A4   4  через базис. 5   17 с Решение. Имеем три вектора в R 3 , поэтому для проверки независимости векторов достаточно вычислить определитель, составленный из координат векторов A1 , A2 , A3 : 1  1 1 3 1 2 1 1 2   3  9  0 1 2 2 1 2 1 2 определитель отличен от нуля, следовательно, векторы A1 ; A2 ; A3 - линейно независимы. Составим линейную комбинацию векторов A4  A1 x1  A2 x2  A3 x3 , где x1 , x2 , x3 коэффициенты разложения вектора A4 по базису. Заметим, что разложение вектора A4 представляет собой систему уравнений в векторной форме. Запишем ее в виде расширенной матрицы и решим методом Гаусса. 1 0 3 3    1 1  2 4  2 1 2 5   1 0 3 3   1 0 3 3  1 0 0 3       0 1  5 1   0 1  5 1  0 1 0 1 .  0  1  4  1  0 0  3 0   0 0 1 0        Итак, разложение вектора A4 по базису A1 , A2 , A3 будет иметь вид A4  3  A1  1  A2  0  A3  3 A1  A2 . Пусть задана система векторов п-мерного пространства A1 , A2 ,..., Am Алгоритм построения базиса системы векторов систему уравнений в векторной форме: 1. Составить A1 x1  A2 x2  ....  Am xm  0. 2. Найти методом Гаусса ее общее решение, т.е. получить разрешенную систему уравнений A1x1  A2 x2  ....  Am xm  0 3. Отметить диагональную часть системы векторов. Векторы, соответствующие диагональной части, образуют базис в данной системе векторов. 4. Компоненты векторов, не вошедших в базис, являются коэффициентами разложения этих векторов по базису. Пример. Найти базис системы векторов, векторы, не вошедшие в базис разложить по базису. 18 A1  3; 1;2; 4; A2  1; 3; 1; 2; A3  1; 5; 0; 1; A4  3;  5; 1; 7; A5  7;15;  11; 8 . Решение: Составим систему уравнений в векторной форме и применим к ней преобразование Гаусса: A1 x1  A2 x2  A3 x3  A4 x4  A5 x5  0.  3   1  2   4   3   3  1   0  1 3 1 2 1 1 5 1 1 3 7    5  15 1  11  7 8  0  15  0 10  . 1 4   0 0   3  8 ~ 5   2  1 1 3 7   7   0 2  14  36    4 ~ 0  1  2  18    9   0 1 1  6    6 1 1 10 25    7  18  ~  9  36   6  24  Базис: A2 ; A3 ; A4 ; r  3 ,  15 x5  0  3x1  x 2   x3  10 x5  0  3x1 x  x 4  4 x5  0  1   3 1 0 0   15             3  0 1 0  10  А1    ; А2    ; А3   ; А4    ; А5   1 1 4             0  0 0 0  0            A1  3 A2  3 A3  A4 ; A5  15 A2  10 A3  4 A4 - есть линейные комбинации векторов базиса. Вернемся к системе линейных уравнений (1.1) a11 x1  a12 x 2  ...  a1n x n  b1 ; a x  a x  ...  a x  b ;  21 1 22 2 2n n 2  .. . . . . . . . .. . . . . . . . .. . . . . . . . a m1 x1  a m 2 x 2  ...  a mn x n  bm . Система содержит п неизвестных и т уравнений. Введем векторы (векторы т-мерного пространства)  a1n   a11   a12   b1           a2n   a 21   a 22   b2  A1   ; A  ; ...... A  ; B  2 n                 a  a  b  a   m1   m2   m  mn  Запишем систему в векторном виде A1 x1  A2 x2  ....  An xn  B . Рассмотрим конкретный пример. 19 Пример 1. Дана система линейных уравнений  x1  3x 4  x5  7   x 2  2 x 4  4 x5  12   x  4 x  3x  10 4 5  3  3 x 4  x5  7  x1   2 x 4  4 x5  12  x2  x3  4 x 4  3x5  10  1   0  0 3 1  7              Введем векторы A1   0 ; A2  1 ; A3   0 ; A4   2 ; A5   4 ; B  12  .  0  0 1   4 3  10              A1 ; A2 ; A3 ; A4 ; A6 ; B – векторы трехмерного пространства; A1 ; A2 ; A3 – составляют базис пространства. Данная система имеет бесчисленное множество решений, зависящих от двух переменных, в частности: x1  7  3x 4  x5 ; x 2  12  2 x 4  4 x5 ; x3  10  4 x 4  3x5 . Здесь x4 , x5 свободные, а x1 ; x2 ; x3 основные или базисные переменные. Если свободные переменные приравнять нулю, т.е. x4  0; x5  0 , то базисные переменные будут равны свободным членам: x1  7; x2  12; x3  10 . Запишем это решение в виде вектора X 0  7;12;10; 0; 0 . Принимая x4  1; x5  0  x1  4; x2  10; x3  6 , получим другое решение X 1  4;10; 6;1; 0. Аналогично для системы (1.1). Если среди векторов A1 ; A2 ; A3 ; ....... An есть базис из т единичных векторов, то решение системы будет иметь n  m свободных переменных, через которые будут выражаться т базисных переменных. Если векторы A1 ; A2 ; ..... Am составляют базис пространства, то система будет иметь следующее решение: x1  b1 ; x2  b2 ;.... xm  bm ; xm1  xm2  ....  xn  0 . Здесь все свободные переменные приняты равными нулю.  Назовем это решение базисным. В приведенном ранее примере это X 0  7;12;10; 0; 0 . Так как любой из векторов-коэффициентов может быть ортом, то система может иметь не одно базисное решение. Систему всегда можно преобразовать в равносильную ей систему с таким расчетом, чтобы любой из ортов ( A1 ; A2 ; ..... Am ) вывести из базиса, а вместо него сделать ортом другой вектор-коэффициент системы, который не входил в первоначальный базис. Во вновь полученной системе базисное решение будет отличаться от первоначального. 20 Пример 2. В рассмотренном выше примере 1 вывести из базиса вектор A2 , а ввести вместо него вектор A 5 . Решение выполним в виде таблицы. Номер Базис B A1 A2 A3 A4 A5 уравнения 1 A1 7 1 0 0 3 1 2 A2 12 0 1 0 2 4 3 A3 10 0 0 1 4 3 Для того, чтобы ввести вектор A 5 в базис (т.е. A 5 должен стать единичным вектором), а вектор A2 вывести из базиса, определим разрешающий элемент матрицы коэффициентов, с помощью которого проведем дальнейшие преобразования системы. Этот коэффициент находится на пересечении второй строки, соответствующей выводимому вектору A2 , и столбца, соответствующего вводимому вектору A 5 . Отметим его скобками ( a 25  4 ). Назовем указанные строку и столбец разрешающими. Разделим разрешающую строку на 4 и обнулим весь столбец. Номер Базис B A1 A2 A3 A4 A5 уравнения 1 A1 4 1  1/ 4 0 5 / 2 0 2 A5 3 0 1/ 4 0 1/ 2 1 3 A3 1 0  3/ 4 1 5/ 2 0 Решение системы: 1 5 x2  x4 4 2 1 1 x5  3  x 2  x 4 14 2 3 5 x3  1  x 2  x 4 4 2 x1  4  Последовательность выполнения операций изменения базиса: 1. Разрешающую строку умножить на ij  1 . aij 2. Без изменения переписать в матрицу те строки матрицы, в которых компоненты вектора A j уже были равны нулю. 3. К каждой из оставшихся строк прибавить разрешающую строку, умноженную на соответствующий множитель. 21 Известно, что любая система уравнений имеет конечное число базисных решений, равное C nr , где r - ранг системы векторов A1 ; A2 ; ..... An . 1.6. Выпуклые множества в п-мерном пространстве В школьном курсе математики выпуклыми назывались многоугольники, целиком расположенные по одну сторону от прямых, на которых лежат их стороны. Общим определяющим свойством, отличающим выпуклый многоугольник от невыпуклого, является то, что если взять любые две его точки и соединить отрезком, то весь отрезок будет принадлежать этому многоугольнику. A B M N C а) D б) Рис.1.1. Выпуклое а) и невыпуклое б) множества  Говорят, что множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит весь отрезок, соединяющий эти точки. Примерами выпуклых множеств являются не только многоугольники, но и круг, сектор, отрезок, куб, шар, пирамида и т. д. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество. Среди точек выпуклого множества можно выделить внутренние (M и N на рис.1.1 ), граничные (отрезки АВ, ВС, СD, DА на рис.1.1 а, ребра многогранника и угловые точки (вершины многогранника). Множество точек называется замкнутым, если оно включает все свои граничные точки. В противном случае множество точек называется неограниченным. 22 Рис.1.2. Выпуклые области Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное угловых точек, называется выпуклым многогранником (многоугольником), если оно ограниченное, и выпуклой многогранной областью, если оно неограниченное. До сих пор рассматривались выпуклые множества точек на плоскости и в пространстве. Аналитически такие точки изображались упорядоченной парой x1 ; x2  или упорядоченной тройкой чисел x1 ; x2 ; x3  . Понятие точки можно обобщить, подразумевая под точкой (или вектором) упорядоченный набор п чисел X  x1; x2 ;... xn  , в котором числа x1 ; x2 ;... xn называются координатами точки (вектора). Как известно, множество всех точек X  x1; x2 ;... xn  образует п-мерное векторное пространство. Фигуры п-мерного пространства уже не имеют реального геометрического смысла и все исследования этого пространства уже надо проводить в аналитической форме. Тем не менее, оказывается целесообразным и в этом случае использовать такие понятия как выпуклость для облегчения представления об объектах п-мерного векторного пространства. Итак, ранее было дано определение выпуклого множества как множества, которое вместе с любыми двумя своими точками содержит отрезок их соединяющий. Что следует понимать под «отрезком» в случае п-мерного пространства? Дадим аналитическое определение этого понятия. Определение. Точка М называется выпуклой линейной комбинацией двух точек А и В, если M  1 A  2 B; 1  0, 2  0, 1  2  1 (1.5) 23 В А М х Рис.1.3. Отрезок АВ Если  пробегает все значения от 0 до 1, то точка М описывает отрезок АВ. Точки А и В называются угловыми или крайними точками отрезка АВ. Т.о. отрезок АВ можно определить как множество точек М, подчиненных соотношению (1.5). n Пусть теперь имеется k точек A1 , A2 ,..., Ak  R и действительные числа i i  1,..., k  , тогда линейную комбинацию этих точек можно записать в виде точки А: A  A11  A2 2  ....  Ak k . Точка А называется выпуклой линейной комбинацией точек A1 , A2 ,..., An , если выполняются условия A  A11  A2 2  ....  An n ; i  0; n  i 1 i 1 (1.6) 1 2 4 A1  A2  A3 - есть выпуклая линейная комбинация 7 7 7 3 2 4 1 2 4 точек A1 , A2 , A3 , а линейные выражения A1  A2  A3 u A1  A2  A3 не 7 7 7 7 7 7 Например, выражение являются выпуклыми комбинациями, т.к. для первого выражения 3 2 4 4    1 u 3    0 - для второго выражения. 7 7 7 7 Из определения выпуклой линейной комбинации точек, очевидно, что угловая точка не может быть представлена как выпуклая линейная комбинация двух других точек отрезка.  Выпуклым множеством будем называть множество таких точек, которое вместе со своими любыми точками содержит и их любую выпуклую линейную комбинацию (т.е. содержит отрезок между ними).  Крайними (или угловыми) точками выпуклого множества будем называть такие точки, которые нельзя представить в виде выпуклой линейной комбинации других точек. Например, вершины треугольника являются крайними точками. 24  Любую точку выпуклого множества можно представить в виде выпуклой линейной комбинации ее крайних точек.  Выпуклое множество будем называть многогранником или многогранной областью, если оно содержит конечное количество крайних точек. Теорема. Выпуклый п-мерный многогранник является выпуклой линейной комбинацией своих угловых точек. Например, треугольник (рис.1.4) можно описать как множество точек М, которые являются выпуклыми комбинациями вершин А, В и С: M  1 A  2 B  3C; 1  2  3  1; 1  0; 2  0; 3  0. В М А С Рис.1.4 Тема 2. Математические модели экономических задач 2.1. Основные понятия и определения Математической моделью экономической задачи называется совокупность математических соотношений, описывающих рассматриваемый экономический процесс. Для составления математической модели необходимо: 1) выбрать переменные задачи; 2) составить систему ограничений; 3) задать целевую функцию. x1; x2 ;... xn , которые Переменными задачи называются величины, характеризуют экономический процесс. Их обычно записывают в виде вектора X  x1; x2 ;... xn  . Системой ограничений задачи называется совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из 25 ограниченности ресурсов или других экономических условий, например, положительности переменных. В общем случае они имеют вид:  i x1 , x2 ,...., xn   0, i  1,2,...l (2.1)   i x1 , x2 ,...., xn    0; , i  l  1, l  2,...m Целевой функцией называют функцию Z  X   f x1 , x2 ,...xn  (2.2) переменных x1; x2 ;...xn , которая характеризует качество выполнения задачи и экстремум которой требуется найти. Если целевая функция (2.2) и система ограничений (2.1) линейны, то задача математического программирования называется задачей линейного программирования (ЗЛП). Допустимым решением (планом) задачи ЛП называется любой п-мерный вектор X  x1; x2 ;... xn  , удовлетворяющий системе ограничений и условиям неотрицательности переменных. Оптимальным решением задачи ЛП называется такое допустимое решение (план) X *  x1* , x2* ,..., xn*  задачи, при котором целевая функция достигает экстремума. Таким образом, решение задачи ЛП заключается в нахождении оптимального решения (плана) X * и вычислении целевой функции при этом решении Z X *   Z max Z min  . Будем рассматривать три формы ЗЛП, а именно: 1) общая задача; 2) основная задача; 3) каноническая задача. Задачу ЛП будем называть общей задачей, если система ограничений (2.1) содержит, хотя бы одно неравенство, и основной задачей, если все ограничения системы (2.1) являются уравнениями. Таким образом, общая задача ЛП имеет вид: система ограничений – система т линейных уравнений и неравенств с п переменными 26 a11 x1  a12 x 2  ....  a1n x n  b1 ; a x  a x  ....  a x  b ;  21 1 22 2 2n n 2  ... . . . . . . . . . . . a m1 x1  a m 2 x 2  ...  .a mn x n  bm . (2.3) Условие неотрицательности переменных, вытекающее из экономического смысла вводимых переменных, x j  0; j  1,2,..., n. (2.4) Линейная целевая функция, зависящая от п неизвестных Z  X   c1 x1  c2 x2  ...  cn xn  opt max или min , (2.5) где X  x1 , x2 ,..., xn  - вектор неизвестных. Общую задачу линейного программирования можно привести к основному виду при помощи следующих утверждений: 1. Неравенство равносильно равенству a1 x1  a2 x2  ....  an xn  b a1 x1  a2 x2  ....  an xn  xn1  b и простейшему неравенству xn1  0 . 2. Неравенство a1 x1  a2 x2  ....  an xn  b равносильно равенству a1 x1  a2 x2  ....  an xn  xn1  b и простейшему неравенству xn1  0 . Переменные, вводимые в неравенства ЗЛП, называются дополнительными или вспомогательными. Каноническая задача является частным случаем основной задачи, т. е. система ограничений содержит только уравнения, при этом система уравнений удовлетворяет двум условиям: 1) в каждом уравнении содержится переменная с коэффициентом, равным единице, отсутствующая во всех остальных уравнениях. Такая переменная называется базисной переменной; 2) свободные члены всех уравнений неотрицательны. Переменные, не являющиеся базисными, называются свободными переменными. В канонической задаче целевая функция выражается только через свободные переменные. При т=2, п=4, например, каноническую задачу можно представить в виде: a11 x1  a12 x 2  x3  b1  0,  a 21 x1  a 22 x 2  x 4  b2  0, Z  X   c0  c1 x1  c2 x2  opt max или min  x j  0,  j  1  4 (2.6) 27 Здесь x3 и x 4 - базисные переменные. Если в канонической задаче положить все свободные переменные равными нулю, то базисные переменные будут равны неотрицательным свободным членам уравнений. Полученное таким способом решение ЗЛП называется базисным решением (планом) канонической задачи. При x1  x2  0 из системы (1.6) получим, что x3  b1  0; x4  b2  0 и базисное решение задачи будет иметь вид. При этом значение целевой функции Z  X   c0 . Из трех задач ЛП главная роль отводится канонической задаче, так как алгоритм симплекс-метода (речь о нем идет далее) непосредственно применяется к канонической задаче, а общая и основная задачи в конечном счете сводятся к канонической. Рассмотрим ЗЛП в основном виде. Ведем более короткую запись ЗЛП в матричной форме: Z  CX  min (max) при ограничениях AX  B, X  0 , где C  c1 , c2 ,..., cn  ;  a11  a A   21  ... . a  m1  x1   b1  a1n        x2   b2  a22 a 2 n  X  ; B  ;  ...   ...  . . . .        b   a m 2 a mn   xn   n a12 Векторная форма записи ЗЛП: Z  X   CX  min (max) при ограничениях A1 x1  A2 x2  ...  An xn  В; и условии X  0 , где CX – скалярное произведение векторов C  c1 , c2 ,..., cn  и X  x1 , x2 ,..., xn  , векторы  a1n   a11   a12   b1           a2n   a 21   a 22  b  A1   ; A2   ; ...; An   ; В 2    ... ... ... ...         a  a  b  a   m1   m2   n  mn  (их называют векторами условий) состоят соответственно из коэффициентов при переменных и свободных членов. Пример. Привести к основному виду ЗЛП: 28 Z  X   3x1  x2  x3  min  x1  2 x 2  x3  7   x1  x 2  2 x3  1 2 x  x  2 x  2 2 3  1 x j  0, j  1, 2, 3 Первое уравнение системы ограничений оставляем без изменения, во второе и третье неравенства введем дополнительные переменные x4  0 u x5  0 :  x1  2 x 2  x3  7   x1  x 2  2 x3  x 4  1 2 x  x  2 x  x  2 2 3 5  1 x j  0, j  1, 2, 3, 4, 5 . Целевая функция имеет вид Z  X   3x1  x2  x3  0 x4  0 x5  min .  Иногда возникает необходимость перейти в задаче от нахождения максимума к нахождению минимума, или наоборот. Для этого достаточно изменить знаки всех коэффициентов целевой функции на противоположные, а в остальном задачу оставить без изменения, т. е. Z  max   Z   min . Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций при оптимальных решениях отличаются только знаком. 2.2. Основные теоремы линейного программирования Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. В частном случае, когда в систему ограничений входят только две переменные x1 и x 2 , это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях ( x1 ≥ 0 и x2  0 ), то соответствующее множество будет располагаться в первой четверти декартовой системы координат (Рис. 2.1). Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой. 29 Рис.2.1. Область допустимых решений: а) неограниченная; б) замкнутая; в) противоречивая Теорема 2. Если ЗЛП имеет оптимальное решение, то целевая функция принимает максимальное или минимальное значение (достигает экстремума) в одной из угловых точек многогранника решений. Если целевая функция принимает максимальное (минимальное) значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек. Эта теорема является фундаментальной, т.к. она указывает принципиальный путь решения задач линейного программирования. Действительно, вместо исследования бесконечного множества допустимых решений для нахождения оптимального решения, надо исследовать лишь ограниченное число угловых точек многогранника решений. Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение. Следствие т.2 и т.3: Если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайне мере, с одним из ее допустимых базисных решений. 2.3. Примеры задач линейного программирования 1. Задача об использовании ресурсов При производстве двух видов продукции P1 и P2 используются три вида сырья (ресурсов). Составить такой план выпуска продукции, при котором прибыль от ее реализации была бы максимальной. 30 Исходные данные представлены в табл. 2.1. Вид ресурса Запас ресурса S1 20 12 30 S2 S3 Прибыль Т а б л и ц а 2.1 Расход ресурса на единицу продукции P1 P2 2 1 1 40 1 1 3 50 Решение: Составим экономико-математическую модель задачи. Обозначим вектор переменных величин X x1 , x2  , где x1 – объем выпуска продукции 1-го вида, x 2 – объем выпуска продукции 2-го вида. Для их изготовления потребуется единиц сырья в соответствии с таблицей. Т.к. потребление ресурсов не должно превышать их запасов, то связь между запасами и потреблением сырья выразится системой неравенств (система ограничений): 2 x1  x2  20   x1  x2  12  x  3x  30 2  1 По смыслу задачи переменные x1  0; x2  0 . Суммарная прибыль от реализации продукции (целевая функция): Z  X   C1 x1  C2 x2  max; Z  X   40 x1  50 x2  max . Итак, экономико-математическая модель задачи: найти такой план выпуска продукции X x1 , x2  , удовлетворяющий системе ограничений, при котором функция Z  X  принимает максимальное значение. Задачу легко обобщить на случай выпуска п видов продукции с использованием т видов сырья (ресурсов). Обозначим x j  j  1, 2, ..., n – число единиц продукции Pj , запланированной к производству; bi i  1, 2, ..., m – запас ресурса S i , a ij – число единиц ресурса, затрачиваемого на изготовление единицы продукции Pj (число a ij часто называют технологическими коэффициентами); c j – прибыль от реализации единицы продукции Pj . Тогда, экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: 31 найти такой план X x1 , x2 ,..., x n  выпуска продукции, удовлетворяющей системе a11 x1  a12 x2  ....  a1n xn  b1 ; a x  a x  ....  a x  b ;  21 1 22 2 2n n 2  . . . . . . . . . . . . . . . . a m1 x1  a m 2 x2  ....  a mn xn  bm ; и условию xi  0; i  1, 2,..., n , при котором целевая функция Z  X   C1 x1  C2 x2  ...  Cn xn принимает максимальное значение. 2. Задача составления рациона (задача о диете, задача о смесях) Имеется 3 вида корма, содержащие питательные вещества А, В, С. При откорме животных каждое животное ежедневно должно получать не менее 60 ед. питательного вещества А, не менее 50 ед. питательного вещества В, не менее 12 ед. питательного вещества С. Содержание единиц питательного вещества в 1 кг каждого из видов корма приведены в табл. 2.2. Питательные вещества А В С Стоимость 1 кг корма, усл.ед. Т а б л и ц а 2.2 Количество ед. питательных веществ в 1 кг корма 1-й вид 2-й вид 3-й вид 1 3 4 2 4 2 1 4 3 9 12 10 Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах. Составим экономико-математическую модель задачи. Обозначим x1 ; x2 ; x3 – количество кормов 1, 2 и 3 вида, входящих в дневной рацион. Тогда этот рацион будет включать x1  3x2  4 x3 – вещества А, 2 x1  4 x2  2 x3 – вещества В, x1  4 x2  3 x3 – вещества С. 32 Т.к. содержание каждого питательного вещества должно быть соответственно не менее 60, 50 и 12 ед., то получим систему неравенств:  x1  3x2  4 x3  60;  2 x1  4 x2  2 x  50; (2.7)  x  4 x  3x  12. 2  1 Кроме того, переменные x1  0; x2  0; x3  0 (2.8) Общая стоимость рациона составит Z  X   9 x1  12 x2  10 x3 . Итак, экономико-математическая модель задачи: составить дневной рацион X  x1 , x2 , x3  , удовлетворяющий системе (2.7) и условию (2.8), при котором целевая функция Z  X   9 x1  12 x2  10 x3  min принимает минимальное значение. Задачу можно обобщить на любое количество переменных. 3. Задача об использовании мощностей (о загрузке оборудования) Для производства двух видов изделий А и В используются три типа технологического оборудования: S1 , S 2 и S 3 . Для производства единицы изделия А оборудование первого типа используется в течении 1 ч, оборудование второго типа – 3 ч, оборудование третьего типа – 3 ч. Для производства единицы изделия В оборудование первого типа используется в течение 2 ч, оборудование второго типа – 3 ч, оборудование третьего типа – 1 ч. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 ч, оборудование второго типа – 60 ч, оборудование третьего типа – 50 ч. Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Запишем исходные данные (табл. 2.3) 33 Тип оборудования Общий фонд рабочего времени оборудования, ч S1 32 S2 60 S3 50 Прибыль, ден.ед. Т а б л и ц а 2.3 Затраты времени на обработку одного изделия, ч А В 1 2 3 3 3 1 4 2 Составим экономико-математическую модель задачи. Под планом производства будем понимать ответ вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна. Ведем переменные задачи: пусть x1 – объем выпуска изделия А, x 2 – объем выпуска изделия В. Прибыль рассчитывается по формуле: Z  4 x1  2 x2 . Тогда математическая модель задачи будет иметь вид: 1) Система ограничений:  x1  2 x2  32;  3x1  3x2  60; 3x  x  50.  1 2 2) По смыслу задачи переменные x1  0; x2  0 (условие неотрицательности переменных). 3) Целевая функция суммарная изделий: Z ( x1 , x2 )  4 x1  2 x2  max . прибыль от реализации Итак, экономико-математическая модель задачи: найти такой план выпуска изделий X x1 , x2  , удовлетворяющий системе ограничений, при котором функция Z  X  принимает максимальное значение. Тема 3. Геометрическая программирования интерпретация задачи линейного В случае, когда система ограничений общей задачи ЛП содержит неравенства, связывающие только две переменные, задача допускает наглядный графический способ решения. При n  2 общая задача имеет вид: 34 a11 x1  a12 x 2  b1 ; a x  a x  b ;  21 1 22 2 2  ... . . . ... . a m1 x1  a m 2 x 2  bm ; x1  0; x2  0. (3.1) (3.2) Z  X   c1 x1  c2 x2  max  min  (3.3) Каждое линейное неравенство системы (3.1) на плоскости x1 0x2 определяет полуплоскость с границей, задаваемой прямой ai1 x1  ai 2 x2  bi , i  1, 2,..., m ; условие неотрицательности переменных x1  0 и x2  0 определяют полуплоскости справа от прямой x2  0 и вверх от прямой x1  0 , т.е. первую координатную четверть. Если система (3.1) – (3.2) совместна, то пересечение полуплоскостей образуют выпуклый многоугольник, внутренние и граничные точки которого образуют область допустимых решений (множество планов). Этот многоугольник может быть ограниченным или представлять собой бесконечную выпуклую область. В случае несовместности системы (3.1) – (3.2) множество решений пусто. Целевая функция Z  X   F x1 , x2  является функцией двух переменных. Градиент функции ( grad Z ) – это вектор, координатами которого являются  Z Z  ; .  x  1 x 2  частные производные данной функции, т.е. grad Z   Z Z  c1;  c2 , вектор grad Z  c1 ;c2  перпендикулярен к линиям уровня и x1 x 2 направлен в сторону наибольшего возрастания функции. Линии уровня функции двух переменных – множество параллельных прямых Z  X   const , т.е. c1 x1  c2 x2  C , где С – произвольная постоянная. Решение задачи (3.1) – (3.3) сводится к отысканию такой точки X * области Z X   c o , n решений, через которую проходит линия уровня соответствующая наибольшему (наименьшему) значению функции * Z X   Z max Z min  . Построив прямую c1 x1  c2 x2  const (например, при значении C=0), параллельным переносом ее перемещают по области решений в направлении grad Z , если Z  max или в противоположном направлении, если Z  min (рис.3.1). 35 s t Рис.3.1. Отыскание оптимума целевой функции Оптимальное значение целевая функция принимает в угловых точках или на границе многоугольника решений (в соответствии со свойствами задачи ЛП). Для нахождения координат точки, в которой целевая функция оптимальна, сначала по чертежу определяют те границы, пересечением которых является найденная точка. Затем из уравнений этих прямых составляется система уравнений, решение которой дает координаты точки. Вернемся к примеру о производстве двух видов изделий А и В, рассмотренному в теме 2. Математическая модель задачи: 1) Система ограничений  x1  2 x2  32;  3x1  3x2  60; 3x  x  50.  1 2 2) x1  0; x2  0 (условие неотрицательности переменных); 3) Целевая функция – суммарная Z ( x1 , x2 )  4 x1  2 x2  max . прибыль от реализации изделий Поскольку задача содержит две переменные, решим ее графически. Для этого построим на плоскости ( x1 0 x2 ) области, описываемые системой ограничений. Каждое из неравенств определяет полуплоскость с границей, задаваемой прямой. Выпишем соответствующие уравнения. 1) x1  2 x2  32; 2) 3x1  3x2  60; 3) x1  x2  50. 36 Проведем на плоскости эти прямые (рис.3.2) Рис.3.2. Построение области допустимых решений Для того чтобы определить, какая из двух полуплоскостей является решением данного неравенства, нужно в любой из полуплоскостей выбрать пробную точку и подставить ее координаты в левую часть неравенства. Если получится верное неравенство, то содержащая пробную точку полуплоскость будет решением неравенства; если неравенство не выполняется, то решением является полуплоскость, не включающая пробной точки. Если прямая не проходит через начало координат, то в качестве пробной точки удобно брать точку (0;0) – начало координат. Подставим в первое неравенство x1  0 и x2  0 , получим верное неравенство 0  32 , следовательно, точка (0;0) – принадлежит полуплоскости решений. Ее можно пометить каким-либо способом (на рис.2.3 – это штриховка). Аналогично решаем остальные неравенства. В результате три неравенства системы ограничений и условие неотрицательности переменных определяют на плоскости многоугольник АВСDЕ, ограниченный слева и снизу координатными осями (рис.3.3). Найдем вектор grad Z  4; 2 , он, как отмечалось ранее, указывает направление наискорейшего возрастания целевой функции. Начало этого вектора в начале координат, конец в точке с координатами (4;2). 37 Найдем максимальное значение целевой функции на области решений. Для этого построим произвольную линию уровня, например, Z  X   4 x1  2 x2  0 . График линии уровня (построен пунктирной линией красного цвета) передвигается в направлении своего градиента, до тех пор, пока не достигнет граничной точки многоугольника (точка D ). Эта точка является точкой пересечения линий (2) и (3). Решая систему, составленную из данных уравнений  x1  x2  20 (2) ,  3x1  x 2  50 (3) получаем координаты точки D(15; 5), определяющие оптимальный план (решение) задачи X *  15;5 . Таким образом, для получения максимальной прибыли объем выпуска изделия А – x1 должен составлять 15 единиц, объем выпуска изделия В – x 2 должен составлять 5 единиц. При этом прибыль от реализации изделий составит: Z  X *  Z max (15;5)  4  15  2  5  60  10  70 (ден. ед.) Рис.3.3. Графическое решение 38 Тема 4. Симплекс- метод 4.1. Сущность симплекс-метода и алгоритм Симплекс-метод разработан для решения ЗЛП в каноническом виде. Основное содержание симплексного метода состоит в следующем. Для последовательного улучшения решения необходимо:  определить способ нахождения первоначального допустимого базисного, т.е. опорного решения;  указать способ перехода от одного опорного решения к другому;  задать критерии, которые позволяют своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения. Как указывалось, ранее, задача линейного программирования называется приведенной основному виду, если 1) система ограничений содержит только равенства; 2) правые части системы ограничений и все переменные неотрицательны; Иногда ЗЛП симплексным методом решают только в одном виде, например, на максимум. Будем рассматривать задачи, когда требуется найти максимум целевой функции. Тогда основная задача ЛП имеет вид: Z  X   c1 x1  c2 x2  ...  cn xn  max a11 x1  a12 x 2  ....  a1n x n  b1 a x  a x  ....  a x  b  21 1 22 2 2n n 2  ... . . . . a m1 x1  a m 2 x 2  ....  a mn x n  bm x j  0; j  1,2,..., n (4.1) x j  0; j  1,2,..., n. Векторная форма записи основной ЗЛП: Z  X   CX  max при ограничениях A1 x1  A2 x2  ...  An xn  B; и условии X  0 , где СХ – скалярное произведение векторов C  c1 , c2 ,..., cn  и X  x1 , x2 ,..., xn  , векторы  a1n   a11   a12   b1           a2 n   a21   a22   b2  A1   ; A  ; ...; A  ; В  2 n  ...   ...   ...  ...          a  a  b  a   m1   m2   n  mn  39 (векторы условий) состоят соответственно из коэффициентов при переменных и свободных членов. Переход от общей формы к основной: 1. Если в правой части системы ограничений (4.1) имеются отрицательные числа, то необходимо умножить на «-1» обе части равенства, в котором в правой части стоит отрицательное число. 2. Чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную неотрицательную переменную к левой части неравенства. 4. Если в задаче требуется найти минимум целевой функции, то можно ввести новую целевую функцию Z1  X   Z  X  , тогда max Z1   min Z . Т. е. достаточно изменить знаки всех коэффициентов целевой функции на противоположные, а в остальном задачу оставить без изменения. Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций при оптимальных решениях отличаются только знаком. Пример. Решить задачу ЛП Z  X   x1  2 x2  3x3  min 2 x1  x2  x3  1;  4 x1  2 x2  x3  2; 3x  x  5; 3  1 x j  0; j  1, 2, 3 Задача задана в общем виде. Приведем ее к основной задаче. Добиваемся, чтобы все правые части неравенств оказались неотрицательными. Для этого второе неравенство системы умножаем на (-1), при этом знак неравенства меняется на противоположный. Система приобретает вид: 2 x1  x2  x3  1;   4 x1  2 x2  x3  2; x j  0; j  1, 2, 3. 3x  x  5;  1 3 Во все неравенства x4  0, x5  0, x6  0 : введем Z  X   x1  2 x2  3x3  min  1; 2 x1  x2  x3  x4   4 x1  2 x2  x3  x5  2; 3x  x3  x6  5;  1 40 x j  0; j  1, 2,..., 6. дополнительные переменные Целевая функция имеет вид: Z1  X   Z  X    x1  2 x2  3x3  0  x4  x5  x6   min . Решение основной задачи ЛП симплекс-методом проводится в симплекстаблице, куда заносятся все исходные данные. Каждому уравнению системы ограничений соответствует строка таблицы. В первый столбец выписывается базис системы векторов-условий. Во второй столбец – коэффициенты целевой функции, соответствующие базисным переменным; в третий столбец выписываются свободные члены уравнений bi , остальные элементы таблицы равны коэффициентам при соответствующих неизвестных. Последняя строка называется индексной, о ней скажем позже. Последний столбец оставим для оценочных отношений, необходимых для расчета наибольшего возможного значения переменной. Базис Z X  Cб Свободный член В c1 c2 A1 A2 b1 a11 a12 b2 a 21 a 22 … … … bm a m1 am2 … … … … … cn An Т а б л и ц а 4.1 Оценочное отношение a1n a2 n … a mn Если система ограничений состоит только из уравнений, правые части которых неотрицательны, и в каждом уравнении содержится разрешенная переменная, то это задача в канонической форме. Векторы, соответствующие разрешенным переменным, составляют базис, а базисные переменные канонической задачи составят естественный начальный опорный план (решение) X 0 при условии, что все неосновные переменные приняты равными нулю. Т.е., если, например, векторы A1 , A2 ,... Ak составляют базис, то начальное базисное решение будет X 0  x1 , x2 ..., xk ,0, 0...0  b1 , b2 ,...bk , 0, 0,...0 , k при этом значение целевой функции составит: Z  X    ci bi i 1 Такая задача называется задачей с естественным базисом. Если система ограничений не имеет базиса, то базисное решение можно найти методом Гаусса, однако чаще всего применяют так называемый М-метод, который будет рассмотрен далее. 41 Продолжим решение примера. Составим симплексную таблицу (табл. 4.2) Базис A4 A5 A6 Сб В 1 2 5 -1 1 3 A1 A2 A3 A4 A5 2 -4 3 -1 2 1 1 1 -1 1 Т а б л и ц а 4. 2 Оценочные A6 отношения 1 Векторы A4 , A5 , A6 образуют естественный ортонормированный поэтому запишем их базис, в первый столбец таблицы. Переменные x4 , x5 , x6 являются базисными переменными. Приравняв нулю свободные переменные ( x1  x2  x3  0 ), получаем начальное базисное решение X 0  0, 0, 0,1, 2, 5 . С помощью вышеприведѐнной таблицы мы выполнили шаг решения ЗЛП симплексным методом. Эта часть решения называется нулевым шагом или нулевой итерацией. Чтобы проверить оптимальность найденного решения, нужно для каждого вектора A j при неизвестном x j вычислить оценку  j по формуле: m  j  Cб A j  c j или  j   ci xij  c j . i 1 Здесь Cб A j - скалярное произведение векторов Cб и A j . Для нашего примера: 0  2   0 1          1   0     4    1  1;  4   0    0   0  0; 0  3   0 0          0    1  0  0          2   0    2   1  1;  5   0    1   0  0;  0  0   0  0         0  1       3   0     1  3  3; 0  1      0 0      5   0    0   0  0. 0 1     Найденные значения оценок вносятся в индексную строку. Обратим внимание на то, что оценки всех базисных векторов равны нулю. Проверка на оптимальность - это анализ индексной строки. 42 Возможны 3 случая: 1. Все элементы индексной строки неотрицательны (  j  0 ) в задаче на максимум (или неположительные  j  0 в задаче на минимум), тогда план оптимален и целевая функция достигла своего максимума. Ранее мы условились, что будем рассматривать каноническую задачу на максимум. Если решается задача на минимум, то возможно ее преобразование к задаче на максимум заменой целевой функции Z  X  на функцию Z1  X   Z  X  . Как известно решения этих задач совпадают. 2. Среди элементов индексной строки есть отрицательные оценки (в задаче на максимум), но в столбцах над ними нет положительных элементов. В этом случае целевая функция не ограничена сверху на области решений, и оптимального решения не существует. 3. Среди оценок  j есть отрицательные оценки и в столбцах над ними есть хоть один положительный элемент. Значит, целевая функция не достигла максимума и надо переходить к следующему шагу. В нашем случае в индексной строке имеется две отрицательные оценки  2  1 и  3  3 . Следовательно, найденное решение X 0  0, 0, 0,1, 2, 5 неоптимальное и его можно улучшить за счет введения в ортонормированный базис одного из векторов, имеющих отрицательные оценки. Лучше всего для этого выбрать вектор с максимальной по абсолютной величине оценкой  j  0 . В нашем примере это  3  3 и, следовательно, вектор A3 будем вводить в базис. Пометим его стрелочкой, а весь столбец выделим серым цветом, этот столбец называется разрешающим. Для определения вектора, выводимого из базиса, составляют так называемые  , если a ij  0;  оценочные отношения, вычисляемые по формулам  i   bi , если a ij  0  aij  В строке с минимальным  i >0 находится вектор, выводимый из базиса. Эту строку будем называть разрешающей (или ключевой) строкой. На пересечении разрешающей (i-ой) строки и разрешающего (j-го) столбца находится разрешающий (ключевой) элемент (выделен жирным шрифтом и подчеркнут). Значения оценочных отношений для нашего примера внесены в последний столбец таблицы.  min =1. Следовательно, разрешающий элемент находится на пересечении первой строки и третьего столбца (помечен красным цветом) и, следовательно, вектор A4 выводится из базиса, а вектор A3 вводится. Теперь 43 вектор, вводимый в базис, должен стать ортом, т.е. единичным вектором. Эта операция выполняется методом Гаусса: 1) Разрешающую строку делим на разрешающий элемент (если он не равен 1, как в нашем случае), получаем новую разрешающую строку для следующей симплексной таблицы; 2) все остальные элементы разрешающего столбца обнуляем с помощью новой разрешающей строки. В результате получим новую симплексную таблицу (первая итерация). X 1  0, 0,1, 0, 3, 4 - новое базисное решение, значение целевой функции при этом решении Z  X 1   3 . Базис A4 A5 A6 Сб j В -1 1 3 A1 A2 A3 A4 A5 A6 1 2 5 2 -4 3 -1 2 1 -1 1 1 1 1 Z1  X 0   0 1 -1 -3 A5 A6 3 1 3 4 2 -2 1 -1 1 1 1 1 1 -1 1 1 Z1  X 1   3 7 -4 3  A3 A2 A6 3 1 4 3 1 -2 3 1 1 2 1 -2 1 1 -1 1 Z1  X 2   15 -1 7 4 1 1  A3 A2 A1 44 3 1 -1 4 11/3 1/3 1 Z1  X 3   46 / 30 X 0  0, 0, 0,1, 2, 5 1 5  1 1    min  ;   1 вектор A3 вводится, вектор A4 выводится  A3 Т а б л и ц а 4.3 Оценочные отношения 2 1 -1/3 1/3 -2/3 -1/3 2/3 1/3 19 3 1 3 11 3 X 1  0, 0,1, 0, 3, 4 3 4  1 1    min  ;   3 Вводится вектор A2 , A5 выводится X 2  0, 3, 4,0, 0,1 1  3 A1 вводится, A6   min    1 / 3 выводится  1 11  X 3   , ,4, 0, 0, 0  3 3  Все оценки отрицательны – план оптимален и единственен В результате трех итераций получено оптимальное решение X *   , 1 11  ,4,0,0,0  . 3 3  Т. к. исходная задача содержала три переменные, то отбросим значения дополнительных переменных: X *   , 1 11  ,4  . Оптимальное значение целевой 3 3  функции: Z min  X *  46 / 3 . Следует отметить, что, если в оптимальном решении есть оценки, равные нулю, у векторов, не вошедших в базис, то это говорит о том, что найденное оптимальное решение не единственно. 4.2. М-метод (решение искусственным базисом) задачи линейного программирования с Метод искусственного базиса применяется для решения основной ЗЛП в случае, когда задача не имеет начального решения с базисом из единичных векторов (ортонормированным базисом). В этом случае в уравнения, не содержащие базисной переменной, добавляют со знаком «+» неотрицательные переменные, называемые искусственными. В отличие от дополнительных переменных, искусственные переменные влияют на целевую функцию Z  X  , они входят в нее с коэффициентами М, причем в задачу на максимум к коэффициентом –М, в задачу на минимум с коэффициентом +М. Величина М предполагается достаточно большим положительным числом M  1 , значение которого не задается. Поэтому такая задача носит название М-задачи. В случае решения задачи на максимум расширенная задача имеет вид: Z ( X )  c1 x1  c2 x2  ...  cn xn  M xn1  ...  xnm   max при ограничениях: a11 x1  a12 x 2  ...  a1n x n  x n 1  b1 a x  a x  ...  a x  x  b  21 1 22 2 2n n n2 2  ..... a m1 x1  a m 2 x 2  ...  a mn x n  x n  m  bm xj  0. Векторы An1 , An2 ,..., Anm называются искусственными векторами. Данная задача имеет начальное опорное решение X 1  0,0,...,0, b1 , b2 ,..., bm  с базисом Б  ( An1 , An2 ,..., Anm ) (в этом случае исходный базис целиком состоит из искусственных векторов). 45 Справедлива следующая теорема. 1. Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи; 2. если в оптимальном решении М-задачи хотя бы одна искусственная переменная отлична от 0, то исходная задача не имеет решения (из-за несовместимости системы ограничений); 3. если М-задача не имеет решения из-за неограниченности целевой функции, то и исходная задача решения не имеет. Особенности алгоритма метода искусственного базиса 1. Виду того, что начальное опорное решение расширенной задачи ЛП содержит искусственные переменные, входящие в целевую функцию с коэффициентами -М (max) или +М (min), оценка разложений векторов условий  j  Cб X j  c j состоит из двух слагаемых  j  j  j M  . Так как М – велико, то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемое j M  . 2. Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения. 3. После того как все векторы, соответствующие искусственным переменным, исключены из базиса, расчет продолжается обычным симплексным методом с использованием оценок  j , не зависящих от М. 4. Переход от решения расширенной задачи к решению исходной задачи осуществляется с помощью указанных ранее замечаний. Пример. Найти решение следующей задачи. Z  X   x1  x2  4 x3  max  x1  4 x2  x3  20  2 x1  x2  3x3  24 x  x  6  1 2 x j  0  j  1, 2,3 Приведем задачу к основному виду, введя дополнительные переменные 46  x1  4 x2  3x3  x4  20  2 x1  x2  3x3  x5  24 x  x  x  6 6  1 2 x j  0  j  1  6 Z  X   x1  x2  4 x3  0 x 4  0 x5  0 x6  Mx7  max   x1  4 x2  3x3  x 4  20  2 x1  x2  3x3  x5  24 x  x  x  x  6 2 6 7  1 В первых двух уравнениях содержатся базисные переменные x4 u x5 (это дополнительные переменные), а в третьем базисная переменная отсутствует, поэтому введем искусственную переменную x 7 , которая и будет являться базисной. Решаем М-задачу. Составим симплексную таблицу: Базис A4 A5  A7 В Сб -M 20 24 6 Z 0 = 0-6М A4  A5 A1 1 14 12 6 Z 1 =6  A4 A3 A1 4 1 10 4 6 Z 2 =22 A2 A3 A1 1 4 1 3 5 3 Z 3 =26 Т а б л и ц а 4.4 -M 1 1 4 A1 A2 A3 A4 A5 A6 A7 1 2 1 4 1 1 1 3 1 1 -1 1 -1 1М  1 -1 -1 -4 1 3 -1 1 1 3 1 1 1 2 1 -4  -1 1 10/3 1/3 1 1 1 -1/3 1/3 1/3 2/3 -1 -4/3 4/3 5/3 1 1 1 2/10 1/10 1/10 4/10 6/5 9/5 47 Все оценки положительны, поэтому решение X 3  3, 3, 5, 0, 0, 0 оптимально. Отбрасывая дополнительные переменные, получим ответ: Z max  26 при X *  3, 3, 5 . Раздел 2. Специальные задачи линейного программирования Тема 5. Теория двойственности в операционном анализе экономических систем Любой задаче линейного программирования (исходной, или прямой) можно оставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе задачи образуют пару двойственных задач. Каждая из задач является двойственной к другой задаче рассматриваемой пары. 5.1. Экономическая интерпретация двойственных задач Пусть предприятие имеет т видов сырья в количестве b1 , b2 ,..., bm , которые используются для изготовления п видов продукции. Известно: a ij – расход i -го сырья на единицу j -й продукции; c j – прибыль при реализации единицы j -го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Математическая модель данной задачи (рассматривалась в теме 2) имеет вид: Z  X   c1 x1  c2 x2  ...  cn xn  max a11 x1  a12 x 2  ....  a1n x n  b1 a x  a x  ....  a x  b  21 1 22 2 2n n 2  ... . . . . . . . . . . . . a m1 x1  a m 2 x 2  ....  a mn x n  bm xi  0; y1 y2 ... (5.1) ym i  1, 2, ..., n Здесь xi – объем производства j -го вида продукции. Предположим, что второй производитель хочет перекупить сырье. Необходимо определить оптимальные цены на сырье. Ведем вектор оценок (цен) видов сырья Y   y1 , y2 ,..., ym  . Затраты на приобретение i -го вида сырья в количестве bi равны bi y i . Второму производителю выгодно минимизировать 48 суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид F Y   b1 y1  b2 y2  ...  bm ym  min (5.2) Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j -й продукции, т.е. a1 j y1  a2 j y2  ....  amj y m меньше прибыли c j , получаемой от реализации этого изделия. Система ограничений приобретает вид a11 y1  a 21 y 2  ....  a m1 y m  c1  a12 y1  a 22 y 2  ....  a m 2 y m  c 2  (5.3) . . . . . . . . . . . . a1n y1  a 2 n y 2  ....  a mn y m  c n Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности: yi  0; i  1,2,..., m . Т. е. связь исходной и двойственной задач состоит в том, что:  коэффициенты c j целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи;  коэффициентами целевой функции F (Y ) являются свободные члены системы ограничений исходной задачи;  матрица коэффициентов системы ограничений двойственной задачи есть транспонированная матрица коэффициентов системы ограничений исходной задачи;  В исходной задаче п неизвестных и т ограничений, в двойственной т неизвестных и п ограничений. Рассмотренная пара задач относится к симметричным парам двойственных задач. В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи): Исходная задача Двойственная задача Симметричные пары 1. Z  X   CX  max, AX  A0 , X  0; F Y   YA0  min, AT Y  C , Y  0. 49 F Y   YA0  max, 2. Z  X   CX  min, AX  A0 , AT Y  C , Y 0 X 0 3. Z  X   CX  max, Несимметричные пары AX  A0 , F Y   A0Y  min, YAT  C. X  0; 4. Z  X   CX  min, AX  A0 , X 0 Здесь C  c1 , c2 ,...cn  , Y   y1 , y2 ,..., y m  , F Y   A0Y  max, AT Y  C.  a11 a21....am1    a a ... a   AT   12 22 m 2  , . .  . .  a a ....a  mn   1n 2 n  b1   x1       b2  x  A0   , X   2  .  ..   ..  b  x   m  n 5.2. Общие правила составления двойственных задач 1. Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными – в левой. 2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону. 3. Если знаки неравенств в исходной задаче «  », то целевая функция должна максимизироваться, т.е. Z  X   max , а если «  », то минимизироваться. 4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче, при этом неизвестное, отвечающее ограничениюнеравенству, должно удовлетворять условию неотрицательности. Если в системе ограничений исходной задачи имеются равенство, то неизвестное, отвечающее этому ограничению-равенству, может быть любого знака. 5. Целевая функция двойственной задачи имеет вид: F Y   c0  b1 y1  b2 y2  ...  bm y m , 50 где c 0 - свободный член целевой функции Z  X  исходной задачи, y1 , y2 ,..., y m - неизвестные в двойственной задаче, b1 , b2 ,..., bm - свободные члены в ограничениях исходной задачи. 6. Целевая функция F Y  двойственной задачи должна оптимизироваться противоположным по сравнению с Z  X  образом, т. е. если Z  X   max , то F Y   min и наоборот. Пример. Пусть у предприятия имеется 2 вида сырья S1 u S 2 , остатки которых составляют 35 и 20 ед. Из них можно наладить производство 3 видов товаров T1 , T2 , T3 . От реализации единицы каждого вида продукции предприятие получит прибыль: от реализации товара T1 – 7 ден. ед., от реализации T2  6 ден. ед., от T3  18 ден. ед. Нормы расхода сырья приведены в таблице: Т а б л и ц а 5.1 Виды сырья S1 S2 Прибыль, ден. ед. Запас сырья 35 20 T1 T2 T3 1 2 7 1 1 6 5 2 18 Задача 1 – наладить производство, тогда возникает вопрос о плане выпуска, который задается тремя неизвестными x1 , x2 , x3 – объемами выпуска продукции, которые в свою очередь подчинены условиям:  x1  x 2  5 x3  35;  2 x1  x 2  2 x3  20; x1  0; x 2  0; x3  0. Прибыль от реализации товаров Z  X   7 x1  6 x2  18x3  max . Вторая возможность: задача 2 – продать сырье другой организации, тогда возникает вопрос, по какой цене. Пусть y1 u y 2 - условная цена единицы сырья ( y1  0 ; y2  0 ). Требования к цене со стороны продающего предприятия: если продать сырье, идущее на изготовление ед. каждого товара, то выручка должна быть не менее чем прибыль от его реализации. 51 T1 Сырье S1 : Сырье S 2 : T2 T3  x1  x 2  5 x3  35 условная цена y1  2 x1  x 2  2 x3  20 условная цена y 2 Тогда ограничения для условных цен будут иметь вид: по T1 :  y1  2 y 2  7  по T2 :  y1  y 2  6 yi  0; i  1, 2. по T3 :  5 y1  2 y 2  18 Других требований к ценам предприятие – продавец предъявить не может. Что касается покупателя, то его пожелание заключается в сокращении до минимума расходов на покупку сырья: F  y   35 y1  20 y 2  min . Таким образом, сформулированы 2 задачи: задача 1 (прямая, исходная) задача 2 (двойственная) Z  X   7 x1  6 x2  18x3  max F  y   35 y1  20 y 2  min  x1  x2  5 x3  35;  2 x1  x2  2 x3  20; x1  0; x2  0; x3  0.  y1  2 y 2  7;   y1  y 2  6; 5 y  2 y  18; 2  1 yi  0; i  1, 2. В короткой, матричной, записи они будут иметь вид Z  X   CX  max, AX  B, X  0; 5.3. F Y   YB  min, AT Y  C , Y  0. Основная теорема двойственности Если из пары двойственных задач одна обладает оптимальным решением (планом), то и другая имеет решение, причем для экстремальных значений целевых функций выполняется соотношение min Z  X   max F Y  . Если целевая функция одной из задач не ограничена, то другая не имеет решения вследствие несовместимости системы ограничений. Докажем эту теорему на примере. Продолжим рассмотрение примера, приведенного выше. Решим исходную задачу симплексным методом. 52 Математическая модель задачи имеет общий вид Z  X   7 x1  6 x2  18x3  max  x1  x 2  5 x3  35;  2 x1  x 2  2 x3  20; x1  0; x 2  0; x3  0. Преобразуем систему ограничений к основному виду, введя дополнительные переменные.  x1  x 2  5 x3  x 4  35;  2 x1  x 2  2 x3  x5  20; xi  0; i  1  5 Z  X   7 x1  6 x2  18x3  0  x4  0  x4  max Решение выполним в симплексной таблице Базис Cб Свободный член В A5 35 20 Z X  j Z 0 =0  A4 7 6 18 A1 A2 A3 A4 A5 1 2 -7 1 1 -8 5 2 -18 1 1  35   5 ;   min    7  20   2  1 1/5 -2/5 18/5 1  7  1 / 5 ;   min    15 / 4  6   8 / 5  1 1/4 -1/8  25 / 4  ;  -1/4 5/8   min  1 / 8   10 15 / 4  11/4 17/8   1 1/3 -2/3 2  A3  A5 Z X  18 7 6 j Z 1 =126 Т а б л и ц а 5.2 Оценочное отношение 1/5 1/5 8/5 3/5 -12/5 17/5  A3  A1 Z X  18 7 j 25/4 15/4 Z 2 =138,75 1 1/8 3/8 -9/8  A3 A2 Z X  18 5 5 10 j Z 3 =150 -1/3 8/3 3 1  3/8  -1/3 5/3 4 53 Все оценки неотрицательны, следовательно, получено оптимальное решение X опт*  0,10, 5; Z опт  X *  150 . Решим теперь двойственную задачу. F  y   35 y1  20 y 2  min  y1  2 y 2  7;   y1  y 2  6; 5 y  2 y  18; 2  1 yi  0; i  1, 2. Система ограничений содержит две неизвестные, поэтому можно решить задачу графическим методом. Многоугольник решений – открытая область АВСD (Рис.5.1) Рис.5.1 . Решение двойственной задачи Границу АВ образует прямая 5 y1  2 y 2  18 , границу ВС – прямая y1  y 2  6 , границу CD – прямая y1  2 y 2  7 . Рассмотрим целевую функцию задачи F  y   35 y1  20 y2  min . Построим прямую, отвечающую значению функции F  y   0; 35 y1  20 y2  0 . Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(у). Начало вектора – точка (0; 0), конец – точка (35; 20). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На рис.5.1 эта прямая обозначена пунктирной линией. 54 Прямая F(у) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:  y1  y 2  6;  5 y1  2 y 2  18. Решив систему уравнений, получим: y1  2; y 2  4 . Откуда найдем минимальное значение целевой функции: Fmin  y   35  2  20  4  150 . Мы убедились, что экстремальные значения целевых функций совпадают. Рассмотрим еще один пример. Даны две взаимно двойственные задачи. F  y   6 y1  4 y 2  min Z  X   2 x1  3x2  max  x1  3x2  6   2 x1  x2  4 x1  0; x2  0  y1  y2  2   3 y1  y2  3 yi  0; i  1,2. Убедимся в том, что исходная задача не имеет решения из-за неограниченности целевой функции Z (X )   , а система ограничений двойственной задачи противоречива, т.е. выполняется вторая часть основной теоремы двойственности. На рис.5.2 представлено графическое решение прямой и двойственной задач. Рис.5.2. Решение прямой и двойственной задач 55 Тема 6. Операционные модели транспортного типа 6.1. Экономико-математическая модель транспортной задачи Под названием «транспортная задача» (ТЗ) объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к ЗЛП и могут быть решены симплексным методом. Однако матрица системы ограничений ТЗ настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Транспортная задача формулируется в следующем виде: однородный продукт, сосредоточенный в т пунктах отправления A1 , A2 ,..., Am в количествах a i единиц соответственно, следует доставить в п пунктов назначения B1 , B2 ,..., Bn в количествах b j . Стоимость перевозки продукта из i-го пункта отправления в j-й пункт назначения (тариф) равна cij . Исходные данные ТЗ обычно представляют в виде табл. 6.1. Пункт поставки Запас поставщиков Т а б л и ц а 6.1 Пункты потребления B1 B2 … Bn A1 a1 c11 c12 … c1n A2 a2 c 21 c 22 … c2n … … … … c m1 cm2 … c mn b1 b2 … bn … Am Запрос потребителя am Требуется составить такой план перевозок (т. е. указать количество перевезенного груза от каждого поставщика к каждому потребителю), при котором будут полностью разгружены поставщики и удовлетворены потребители, а транспортные издержки будут минимальны. Составим математическую модель задачи. Пусть xij – количество единиц продукта, перевозимого по маршруту i, j  . Задача заключается в нахождении таких величин xij , при которых суммарная 56 стоимость перевозок была бы минимальной. Таким образом, переменными (неизвестными) ТЗ являются xij i  1, 2,..., m; j  1, 2,..., n .  x11   x 21 X  mn  Матрица ...  x  m1 ... x1n   ... x 2 n  ... ...  называется планом перевозок.  ... x mn  Так как произведение cij xij определяет затраты на перевозку груза из i-го x12 x 22 ... xm 2 m пункта отправления в j-й пункт назначения, то суммарные затраты n  c i 1 j 1 ij xij определяют целевую функцию, минимум которой необходимо обеспечить по условию задачи. Следовательно, целевая функция имеет вид m n Z  X    cij xij  c11 x11  c12 x12  ...  c mn x mn  min (6.1) Система ограничений состоит из двух групп уравнений:  x11  x12  ....  x1n  a1     x 21  x 22  ....  x 2 n  a 2  m уравнений ...................................     x m1  x m 2  ....  x mn  a m    x11  x 21  ....  x m1  b1   x  x  ....  x  b  22 m2 2  12  n уравнений ....................................   x  x  ....  x  b  2n mn n  1n Первая группа из т уравнений описывает тот факт, что запасы всех т поставщиков вывозятся полностью: (6.2) i 1 j 1 n x j 1 ij  ai ( i  1,..., m ) Вторая группа из п уравнений выражает требование полностью удовлетворить запросы потребителей: m x i 1 ij  bj  j  1,..., n Необходимо учесть также условие неотрицательности объемов перевозок: i  1,2,..., m; j  1,2,..., n xij  0 (6.3) 57 Таким образом выражения (6.1) – (6.4) есть математическая модель транспортной задачи. В рассмотренной задаче предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. m n  a  b i 1 i j 1 (6.4) j Такая задача называется задачей с правильным балансом, а модель (6.1) - (6.4) называется закрытой моделью. Если нарушается условие (6.4), то модель транспортной задачи называется открытой.  Теорема. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. чтобы выполнялось условие (6.4) (задача должна быть с правильным балансом). На практике чаще встречаются открытые модели. Они могут быть двух видов: а) m n i 1 j 1 m n i 1 j 1  ai  b j - запас превышает потребность; б)  ai  b j - потребность превышает запас. В случае а) вводят фиктивный n  1 -й пункт назначения с потребностью m n i 1 j 1 bn 1   ai   b j и полагают стоимость перевозок в этот пункт назначения ci ,n1  0 . В случае б) вводится фиктивный m  1 -й пункт отправления с запасами n m j1 i 1 груза a m1   b j   a i и стоимостью перевозок cm1. j  0 . Таким образом, открытая модель ТЗ может быть сведена к закрытой модели. ТЗ – есть задача линейного программирования, которая имеет следующие особенности: 1. все ограничения заданы в виде уравнений; 2. каждая неизвестная входит только в два уравнения; 3. коэффициенты при неизвестных во всех уравнениях равны единице. 4. ранг матрицы системы векторов-условий ТЗ равен N  n  m  1 . 58 Последняя особенность (4) формулируется как теорема (о ранге матрицы): ранг матрицы системы ограничений ТЗ на единицу меньше числа уравнений системы ограничений. Итак, математически транспортная задача ставится следующим образом: среди множества решений системы линейных уравнений (6.2) и неравенств (6.3) найти такое решение (план)  x11 x12 ... x1n    x x ... x  22 2n  X *   21 ... ... ... ...  ,   x  x ... x m2 mn   m1 которое минимизирует целевую функцию (6.1). Как и все задачи линейного программирования ТЗ может быть решена симплекс-методом, алгоритм которого состоит из следующих шагов: 1) построение начального плана; 2) проверка его на оптимальность. Если план оптимален, то задача решена, в противном случае – переход к п.3: 3) построение нового плана с меньшей (или равной) стоимостью перевозок. Специфические особенности системы ограничений ТЗ привели к разработке упрощенного метода решения на каждом шаге алгоритма. Рассмотрим алгоритм решения транспортной задачи на примере. Пример. Имеются четыре пункта поставки однородного груза А1, А2, А3, А4 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. Количество запасов грузов, потребности потребителей и тарифы перевозок заданы в табл. 6.2. Т а б л и ц а 6.2 Поставщики B1 Потребители B3 B4 B2 Запасы B5 A1 10 7 4 1 4 100 A2 2 7 10 6 11 250 A3 8 5 3 2 2 200 A4 11 8 12 16 13 300 потребности 200 200 100 100 250 850 59 Найти такой план перевозок, при котором общие затраты будут минимальными. Составим математическую модель задачи. Обозначим xij – количество груза, перевезенного от поставщика i к потребителю j. Становятся очевидными следующие ограничения (так как весь груз должен быть вывезен и все потребности удовлетворены полностью): 4 x i 1 i1 4 x i 1 i2 4 x i 1 i3 4 x i 1 i4 4 x i 1 i5  200;  200;  100;  100;  250; 5 x j 1 1j 5 x j 1 2j  250; 3j  200; 4j  300; 5 x j 1 5 x j 1  100; При этом должна быть минимизирована целевая функция Z ( X )  10 x11  7 x12  4 x13  x14  4 x15  2 x21  7 x22  10 x23  6 x24  11x25  8 x31   5 x32  3x33  2 x34  2 x35  11x41  8 x42  12 x43  16 x44  13x45  min . 6.2. Построение начального опорного плана Как и для других ЗЛП, итерационный процесс по отысканию оптимального плана ТЗ начинают с нахождения начального опорного решения.  Опорным решением ТЗ называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Рассмотрим систему ограничений (6.2) и (6.3) ТЗ. Она содержит тхп неизвестных и т+п уравнений, связанных соотношением (6.4), называемым уравнением баланса. Ранг системы ограничений равен N  n  m  1 . Следовательно, невырожденный план ТЗ содержит m  n  1 положительных компонент или перевозок. Таким образом, если каким либо способом получаем 60 невырожденное решение ТЗ, то в матрице X mn значения его компонент положительными являются только m  n  1 , а остальные равны нулю. Если условия ТЗ и ее опорное решение записано в виде таблицы, то клетки, в которых находятся отличные от нуля перевозки, называются занятыми, остальные – незанятыми или свободными. Занятые клетки соответствуют базисным неизвестным, и для невырожденного плана их количество равно m  n 1 . Любое допустимое решение ТЗ можно записать в ту же таблицу, что и исходные данные. Клетки таблицы ТЗ нумеруются так, что клетка, содержащая переменную xij , имеет номер i, j  . Каждой клетке i, j  соответствует переменная xij , которой соответствует вектор-условие Aij . Существуют несколько простых схем построения первоначального опорного плана ТЗ, которые рассмотрим на нашем примере. Метод «северо-западного угла» Прежде всего, проверим, выполняется ли уравнение баланса: a1  a2  a3  a4  100  250  200  300  850; b1  b2  b3  b4  b5  200  200  100  100  250  850. Поскольку 4 5 i 1 j 1  ai  b j , то мы имеем дело с задачей закрытого типа. Решение будем строить непосредственно в транспортной таблице (табл. 6.3), приведенной в условии примера. Принцип заполнения таблицы состоит в том, что начиная с крайней левой верхней ячейки (северо-западный угол) количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился. Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет первого поставщика A1 . Для этого сравниваем a1  100 с b1  200 , a1  b1 . Меньший из объемов, т.е. 100 ед., записываем в клетку (1,1) (выделено красным цветом). Запасы первого поставщика полностью израсходованы, поэтому остальные клетки первой строки прочеркиваем. Потребности B1 остались неудовлетворенными на 200 100 = 100 ед. Сравниваем этот остаток с запасами второго поставщика A2 : т.к. 100<250, то 100 ед. записываем в клетку (2,1) потребителя B1 , а оставшиеся клетки этого столбца прочеркиваем. У поставщика A2 осталось 150 ед. груза. 61 Т а б л и ц а 6.3 Поставщики B1 B2 10 A1 7 - 100 8 A3 11 A4 потребности 200 100 8 - 100 100 11 250 2 200 13 300 2 - 50 12 200 6 3 50 4 - - 5 - B5 1 10 - 150 B4 - 7 100 Запасы 4 - 2 A2 Потребители B3 16 50 100 250 250 850 Удовлетворяем потребности потребителя B2 за счет оставшегося у A2 груза, т.е. записываем 150 ед. в клетку (2,2) и т.к. запасы A2 полностью израсходованы, то прочеркиваем оставшиеся клетки второй строки. Недостающий B2 груз берем у поставщика A3 и записываем в клетку (3,2) 50ед. Теперь потребности B2 полностью удовлетворены, поэтому в оставшейся клетке второго столбца ставим прочерк. Переходим к удовлетворению потребителя B3 , сделаем это за счет остатка, имеющегося у поставщика A3 , записываем в клетку (3,3) 100 ед., в остальных клетках третьего столбца ставим прочерки, поскольку потребности B3 удовлетворены полностью. Продолжим этот процесс, пока не удовлетворим всех потребителей за счет запасов всех поставщиков. На этом построение первоначального опорного плана заканчивается. Табл. 6. 3 представляет собой начальный план задачи. Заполненные клетки таблицы (выделены цветом) соответствуют базисным переменным, пустые – свободным переменным из системы ограничений (6.2) (свободные переменные равны нулю). Поскольку система ограничений содержит n  m  1 линейно независимых уравнений, то и число базисных переменных будет таким же (т – число поставщиков, п – число потребителей). План с n  m  1 заполненными клетками называется невырожденным, при меньшем числе заполненных клеток – вырожденным. Для того чтобы снять вырождение, необходимо в пустые клетки записать нулевые перевозки, дополнив число базисных переменных до количества n  m  1 . Ноль можно поставить только в пустую клетку, которая не образует цикла вместе с уже заполненными. 62 Циклом называется такая последовательность клеток таблицы ТЗ i1 , j1 , i1 , j2 ; ... ik , j1  , в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последние клетки также находятся в одной строке или столбце. Цикл изображают в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900. Простейшие циклы изображены на рис. 6.1. Рис. 6.1. Виды циклов Построение циклов начинают с какой-либо занятой клетки и переходят по столбцу (строке) к другой занятой клетке, в которой делают поворот на 90 0 и движутся по строке (столбцу) к следующей занятой клетке и т.д., пытаясь возвратиться к первоначальной клетке. Проверим вырожденность плана нашей задачи: мы имеем четырех поставщиков ( т = 4) и пять потребителей (п = 5), следовательно n  m  1 = 8. Заполненных клеток 8, т. е. план – невырожденный. Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости, стоящие в правом углу этих же клеток: Z  100 10  100  2  150  7  50  5  100  3  50 16  250 13  6950 (ден.ед.). При составлении первоначального опорного плана методом «северозападного угла» стоимость перевозок не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом работ. Если при составлении опорного плана учитывать стоимость перевозок, то, очевидно, план будет значительно более близким к оптимальному. Метод минимальной стоимости 63 Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai u b j . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы. Либо исключается столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс повторяется. Вернемся к рассмотренной выше задаче. Т а б л и ц а 6.4 Поставщики B1 B2 10 A1 - 7 - 8 A3 - 11 A4 200 2 11 250 2 200 13 300 200 12 100 100 100 - - 8 150 200 6 3 - 4 - - 5 - B5 1 10 - 50 B4 100 7 200 Запасы 4 - 2 A2 потребности Потребители B3 16 100 50 250 850 Выбираем наименьшую стоимость перевозки единицы груза, она равна 1 ед. и соответствует клетке (1,4), а т.к. a 4  b4 , то 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице наименьшая стоимость соответствует клеткам (2,1) , (3,4) и (3,5). Заполняем любую из них, например, (2,1). Имеем 200<250, следовательно, записываем в нее 200 ед. и исключаем из рассмотрения первый столбец. В клетку (3,5) записываем 200 и исключаем из рассмотрения третью строку, соответствующую поставщику A3 , т.к. его запасы израсходованы. В оставшейся таблице выбираем опять наименьшую стоимость и продолжаем процесс. В результате получен план: X  x14  100; x21  200; x22  50; x35  200; x42  150; x43  100; x45  50 , остальные переменные равны нулю. План не содержит циклов и состоит из 7 положительных компонент, следовательно, является вырожденным опорным планом. Определим его стоимость Z  100 1  200  2  50  7  200  2  150  8  100 12  50 13  4300 ден.ед. Стоимость перевозок значительно меньше, следовательно, план ближе к оптимальному. 64 6.3. Критерий оптимальности решения ТЗ. Метод потенциалов При проверке плана на оптимальность воспользуемся потенциалов. В основе метода лежит следующая теорема. методом  Теорема. Если план X *  xij * транспортной задачи является оптимальным, то ему соответствует система из т+п чисел U i * u V j * , удовлетворяющих условиям U i *  V j *  cij для xij  0 и U i *  V j *  cij для xij  0 i  1,2,..., m; j  1,2,..., n . Числа U i , V j называются потенциалами соответственно поставщиков и потребителей. Каждому поставщику Ai и потребителю B j поставим в соответствие потенциалы U i и V j , таким образом, чтобы для каждой занятой клетки ( xij  0 ) сумма потенциалов равнялась бы стоимости перевозки, стоящей в этой клетке, т. е. U i  V j  Cij . Количество неизвестных потенциалов составит n  m , а уравнений в системе ограничений всего n  m  1 . Поэтому один из потенциалов задается произвольно, после чего остальные потенциалы определяются однозначно. Обычно полагают U 1  0 . Критерий оптимальности: для того чтобы план ТЗ был оптимальным, необходимо и достаточно, чтобы для всех пустых (незанятых) клеток сумма потенциалов должна быть меньше или равна стоимости перевозки, стоящей в этой клетке, т.е. U i  V j  Cij . Рассмотрим алгоритм метода потенциалов и одновременно проиллюстрируем его применение на опорном плане, полученном в предыдущем примере. Для этого к табл.6.4 добавим строку и столбец, в которых будем записывать значения потенциалов. Получим таблицу 6.5. Построение системы потенциалов Систему потенциалов можно построить только для невырожденного опорного плана. В таблице 6.5 опорный план вырожденный, т.к. не хватает одной занятой клетки, поэтому для устранения вырожденности запишем, 65 например, в клетку (3,4) нулевую перевозку. Клетки, в которые введены нулевые перевозки, называют фиктивно занятыми. Т а б л и ц а 6.5 v1  3 Поставщики v2  8 v3  12 v4  13 v5  13 vj ui запасы A1 B1 10 100 B3 B2 B4 7 B5 1 4 u1  12 + 6 11 u 2  1 +2 u3  11 - 13 u4  0 4 100 A2 2 250 200 A3 8 200 50 7 10 1 6 5 1 3 - 2 A4 потребности 11 300 850 200 + 8 150 200 12 100 100 200 16 100 50 250 Используем условие U i  V j  Cij для занятых клеток: (1.4): (2.1): (2.2): (3.4): U1 + V4 = 1 ; U2 + V1 = 2; U2 + V2 = 7; U3 + V4 = 2; (3.5): U 3  V5 = 2; (4.2): U4 + V2 = 8 ; (4.3): U4 + V3 = 12 ; (4.5): U4 + V5 = 13. Выбираем строку, которая содержит наибольшее количество занятых клеток, строка A4 и полагаем U 4  0 . В строке A4 три занятых клетки (4,2),(4,3) и (4,5), которые связывают потенциал U 4 с потенциалами V2 ,V3 u V5 , отсюда V2  C 42  U 4  8  0  8 V3  C 43  U 4  12  0  12 V5  C 45  U 4  13  0  13 Продолжая аналогичные вычисления, получаем остальные потенциалы: V1 = 3, V4 = 13, U1 = -12, U2 =-1, U3 = -11, которые вносим в таблицу. Система потенциалов построена. Проверка оптимальности для незанятых клеток. Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия U i  V j  C ij : 66 1;1 : 3   12  10; 2;3 : 12  1  10; 3;1 : 3  11  8; 1;2 : 8   12  7; 2;4 : 13  1  6; 3;2 : 8  11  5; 1;3 : 12   12  4; 2;5 : 13  1  11; 3;3 : 12  11  3; 1;4 : 13   12  4; 4;3 : 13  16. Видим, что неравенство не выполняется для трех клеток. Обозначим разность между суммой потенциалов и соответствующей стоимостью перевозки через  ij (эту разность назовем оценкой клетки), тогда  ij  U i  V j   Cij . Если для какой-либо клетки  ij  0 , то план не оптимален. Для каждой такой клетки величину  ij  0 (  23  1;  24  6;  25  1) записываем в левый нижний угол. Найденный план не оптимален и его можно улучшить. 6.4. Методы улучшения неоптимального плана Выбор клетки, в которую необходимо послать перевозку. Транспортная задача решается на минимум, поэтому алгоритм ее решения также следует общим принципам алгоритма решения симплексным методом на минимум. Если отождествлять занятые клетки с векторами, составляющими базис, а незанятые – с остальными векторами системы ограничений, то в базис включается тот вектор, у которого оценка  k максимальна. В ТЗ значению  k соответствует оценка  ij . В рассматриваемом примере max1; 6; 1  6 , т.е. клетку (2,4) следует сделать занятой. Для этого следует определить, сколько единиц груза должно быть перераспределено в нее. Построение цикла и определение величины перераспределения груза Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+» клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало m  n , поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «-» и «+». Затем находим значение 67  0  min xij , где xij - перевозки, стоящие в клетках, отмеченных знаком «-». Величина  0 определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение  0 записываем в незанятую клетку, отмеченную знаком «+», двигаясь по циклу, вычитаем  0 из объемов перевозок, расположенных в клетках, отмеченных знаком «-», и прибавляя к объемам перевозок в клетках, отмеченных знаком «+». Если  0 соответствует нескольким минимальным перевозкам, то оставляем нулевые перевозки в таком количестве, чтобы во вновь полученном плане было заполнено m  n  1 клеток. В рассматриваемом примере клетку (2,4) отмечаем знаком «+» и находим цикл. Имеем:  0  min 50; 50; 0=0, т.е. нулевую перевозку надо переместить в клетку (2,4), остальные числа, естественно, не изменяются. Получен новый опорный невырожденный план (табл.6.6). Т а б л и ц а 6.6. Поставщи ки A1 запасы 3 8 12 7 13 B1 B2 B3 B4 B5 100 10 7 4 2 A2 250 2 200 A3 A4 200 300 50 8 11 7 10 1 5 + 3 8 150 12 1 100 3 + 6 1 2 16 100 vj ui +4 -6 11 -1 2 -11 200 -3 50 Проверка на оптимальность нового опорного плана Для проверки на оптимальность нового опорного плана необходимо снова построить систему потенциалов и проверить выполнение условие оптимальности ( U i  V j  Cij ) для всех незанятых клеток. Если план окажется снова неоптимальным, то следует повторить вычисления, приведенные ранее. Процесс повторяют до тех пор, пока не получат оптимальный план. В рассматриваемом примере вновь определены потенциалы занятых клеток и вычислены оценки незанятых клеток, среди которых есть положительные (внесены в левые нижние углы соответствующих клеток табл.4). 68 11  3  6  10  13;  25  13  1  11  1  0;  34  7  11  2  6; 12  8  6  7  9;  31  3  11  8  16;  41  3  0  11  8; 13  12  6  4  2  0;  32  8  11  5  8; 15  13  6  4  3  0;  44  7  16  9.  33  12  11  3  2;  23  12  1  10  1  0; Найденный опорный план неоптимальный, поэтому строим новый цикл. Перспективной является клетка (1,4), отмечаем ее знаком «+». Отмечаем вершины цикла, чередуя знаки (+) и «-». Находим 1  50;50;100  50 . Перераспределяем 50 ед. груза по циклу. Получаем новый опорный план, приведенный в табл.6.7.. Т а б л и ц а 6.7 Поставщики запасы A1 3 8 12 7 10 B1 B2 B3 B4 B5 100 10 7 4 2 + A2 250 2 200 7 0- 10 1 A3 200 8 5 3 A4 300 11 + 8 200 12 100 - -1 4 1 50 50 6 11 + 50 1 2 2 200 16 13 vj ui -6 -1 -8 Проверяем план на оптимальность. Рассчитываем потенциалы, принимая U 4  0 , находим оценки незанятых клеток: 11  3  6  10  13;  25  10  1  11  2;  34  7  8  2  3; 12  8  6  7  9;  31  3  8  8  13;  41  3  0  11  8; 13  12  6  4  2  0  32  8  8  5  5;  44  7  16  9;  23  12  1  10  1  0;  33  12  8  3  0;  45  10  13  3. План не оптимален, т.к. есть положительные оценки. Клетку (1,3) отмечаем «+», как перспективную и строим цикл. Находим   min 50;0;100  0 . Клетка (2,2) становится незанятой. Нулевую перевозку перемещаем в клетку (1,3). Распределение грузов осталось без изменения. Вновь проверяем план на оптимальность (табл.6.8). 69 Т а б и ц а 6.8 Поставщики запасы -3 4 1 4 B1 B2 B3 B4 B5 100 A1 10 7 4 250 A2 2 7 200 A3 ui 1 50 10 200 vj 4 11 5 2 -2 13 8 50 6 50 8 5 3 2 200 300 A4 11 8 200  11  3  10  13;  12  7; 12 16 100  25  4  5  11  2;  34  1  2  2  4  3;  31  3  2  8  13;  41  3  8  11  6;  23  5  7  2;  32  2  5  7;  24  4  5  10  1;  33  4  2  3  1;  44  1  8  16  7;  45  4  8  13  1. Все оценки отрицательны, план оптимален. Его стоимость равна 4150 ден.ед. 0 50 50   0   50 0   200 0 X*   0 200     0 200 100 0    6.5. Особенности решения ТЗ с неправильным балансом Модели ТЗ с неправильным балансом (иначе открытые модели) могут быть двух видов: а) б) m n i 1 j 1 m n i 1 j 1  ai  b j – запас превышает потребность;  ai  b j – потребность превышает запас. В случае а) вводят фиктивный n  1 -й пункт назначения с потребностью m n i 1 j 1 bn 1   ai   b j и полагают стоимость перевозок в этот пункт назначения ci ,n1  0 . Соответствующие значения в оптимальном плане будут означать оставшийся неотправленным груз поставщиков. 70 В случае б) вводится фиктивный m  1 -й пункт отправления с запасами груза n m j1 i 1 a m1   b j   a i и стоимостью перевозок cm1. j  0 . Груз, соответствующий поставкам от фиктивного поставщика, останется недополученным потребителями. Таким образом, открытая модель ТЗ может быть сведена к закрытой модели. Пример. Исходные данные транспортной задачи приведены в табл. 6.9. Пункты поставки А1 А2 потребности Запасы 120 100 Т а б л и ц а 6.9 Пункты потребления В1 В2 В3 В4 5 6 2 5 6 9 3 4 40 180 60 170 m n i 1 j 1 Уравнение баланса не выполнено:  ai  b j . Таким образом, это задача открытого типа. Поскольку спрос превышает предложение, добавляем фиктивного поставщика А3 с объем запасов 360 - 220 = 140 единиц груза. Пункты Запасы поставки А1 120 А2 100 А3 140 потребности В1 5 6 40 Т а б л и ц а 6.10 Пункты потребления В2 В3 В4 6 2 5 9 3 4 180 60 170 Получена закрытая транспортная задача: спрос равен предложению. Решение задачи такого типа рассмотрено выше. 71 Раздел 3. Нелинейное программирование Тема 7. Основные понятия и модели нелинейного программирования Во многих экономических исследованиях операций зависимости между постоянными и переменными факторами при более детальном рассмотрении оказываются нелинейными. Как правило, такие показатели, как прибыль, себестоимость, совокупные транспортные затраты, капитальные затраты на производство, зависят от объема производства и других факторов нелинейно. В этом случае возникает задача нелинейного программирования (НП). 7.1. Постановки задачи нелинейного программирования Математическая модель задачи НП в векторной форме может быть представлена таким образом: найти вектор X  R n , (или точку M ( x1 , x2 , .... , xn ) ), такой (такую), что целевая функция достигает максимума (минимума): Z ( X )  f ( x1 , x2 , xn )  max min  (7.1) на множестве допустимых решений, заданных ограничениями  i ( x1 , x2 , xn )  bi i  1, 2,k (7.2)  i ( x1 , x2 , xn )  bi i  k  1,...., m (7.3) где f x1 , x2 , xn  и i x1 , x2 , xn  некоторые известные функции n переменных, а bi – заданные числа и хотя бы одна из функций f и  нелинейная. Рассмотрим пример задачи НП. Возьмем пример использования сырья, рассмотренную в линейном программировании. Предприятие производит два вида продукции P1 и P2 с использованием трех видов сырья (ресурсов). Исходные данные приведены в табл.7.1. 72 Т а б л и ц а 7.1 Расход ресурса на единицу продукции P1 P2 Вид ресурса Запас ресурса S1 20 2 1 S2 12 1 1 S3 30 1 3 Себестоимость Цена 30 42 20 35 Усложним задачу, добавив следующее условие: выпуск продукции производится с браком. Конкретизируем это дополнительное условие. Из-за брака расход сырья зависит от объема x j производства изделий в первом приближении выражается линейной функцией aij  x j , а себестоимость продукции – функцией с j  0,1 x j . Изделия могут выпускаться в любых соотношениях, так как сбыт их обеспечен. Требуется составить план выпуска продукции, обеспечивающий получение максимальной прибыли. Построим математическую модель задачи: пусть x1 – объем выпуска продукции 1-го вида, x 2 – объем выпуска продукции 2-го вида. На изготовление изделий будет израсходовано 2  x1 x1  1  x2 x2 сырья первого вида ( S1 ). По условию 2  x1 x1  1  x2 x2  20  2 x1  x1  x2  x2  20 . Аналогичным образом получаем ограничения по другим видам сырья 2 2 2 x1  x12  x2  x2 2  20;  2 2  x1  x1  x2  x2  12;  2 2  x1  x1  3x2  x2  30. В результате реализации единицы изделия P1 предприятие получит прибыль 42  30  0,1x1  усл.ед.; единицы изделия P2 – прибыль 35  20  0,1x2  усл.ед. Общая прибыль составит Z ( X )  42  30  0,1x1 x1  35  20  0,1x2 x2  12 x1  15x2  0,1x1  0,1x2 . 2 2 Итак, задача свелась к нахождению неотрицательных переменных x1 и x 2 , удовлетворяющих нелинейным ограничениям и доставляющих максимум нелинейной целевой функции. Такая задача относится к задачам нелинейного программирования. В течение последних десятилетий выделились самостоятельные разделы: из нелинейного программирования – выпуклое программирование; – квадратичное программирование; – целочисленное программирование; – стохастическое программирование; 73 – динамическое программирование и др.      Задачи выпуклого программирования – это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены. Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратичная, а ограничения – линейны. В задачах целочисленного программирования неизвестные параметры могут принимать только целочисленные значения. В задачах стохастического программирования в целевой функции или в функциях ограничений содержатся случайные величины, которые подчиняются законам теории вероятностей. В задачах динамического программирования ограничения содержат как параметр время и при этом описываются дифференциальными уравнениями. Процесс нахождения решений в задачах динамического программирования является многоэтапным. Методы решения задач НП различаются в зависимости от вида ограничений. Перечислим основные свойства задач НП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования: 1. Множество допустимых решений может иметь очень сложную структуру (например, быть невыпуклым). 2. Глобальный максимум (минимум) может достигаться как внутри области, так и на ее границах (где он будет не совпадать ни с одним из локальных экстремумов). 3. Целевая функция может быть недифференцируемой, что затрудняет применение классических методов математического анализа. Этим объясняется отсутствие общих методов, подобных симплекс-методу в линейном программировании. Тем не менее отдельные классы нелинейных задач хорошо изучены. Типичными областями применения нелинейного программирования (НЛП) являются прогнозирование, планирование промышленного производства, 74 управление товарными ресурсами, контроль качества выпускаемой продукции, учет и планирование капиталовложений и др. По возрастанию сложности исследования признаков оптимальности задачи нелинейного программирования можно расположить в следующем порядке: – задачи безусловной оптимизации (когда отсутствуют все ограничения вида (7.2) – (7.3); – задачи с ограничениями-равенствами вида (7.2); – задачи с ограничениями-неравенствами вида (7.3); – задачи со смешанными ограничениями (7.2) – (7.3). Три последних типа называются задачами условной оптимизации. Задачи первого типа относятся к классическим методам оптимизации и в принципе решать их можно классическими методами дифференциального исчисления. Однако на этом пути встречаются такие вычислительные трудности, которые делают необходимым поиск других методов решения. Поэтому классические методы часто используют не в качестве вычислительного средства, а как основа для теоретического анализа. Напомним некоторые определения и алгоритмы решений ряда задач математического анализа, которые используются в данной главе. 7.2. Необходимые и достаточные условия существования экстремумов Применяя методы классической теории оптимизации, следует четко представлять себе различие между локальным экстремумом функции, глобальным экстремумом и условным экстремумом. Пусть x принадлежит некоторой области D ( x  D ).  Точка x0 называется точкой локального экстремума, если существует  окрестность этой точки (   D ), для которой f x   f x0  (точка локального максимума) или f x   f x0  (точка локального минимума).  Точка x0 называется точкой глобального экстремума, если для любого x  D f x  f x0  ( в точке глобальный максимум) или f x  f x0  (глобальный минимум). 75 Рис.7.1. Локальный и глобальный минимумы функции у = f(x) Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2. Необходимые условия экстремальности Для функции нескольких переменных F ( X )  f ( x1 , x2 , xn ) справедлива следующая теорема (необходимый признак существования экстремума): для того, чтобы дифференцируемая функция F(X) имела локальный экстремум в точке M 0 ( x10 , x20 , .... , xn0 ) необходимо, чтобы ее все частные производные обращались бы в ноль в этой точке F  0 (i  1, 2, ... , n) в точке M 0 . xi Такие точки называются стационарными точками функции, точками, «подозрительными» на экстремум или критическими точками.  Главными минорами матрицы  a11 a12 a13 ..... a1n    a a a ..... a  21 22 23 2n   A  a31 a32 a33 ..... a3n     ..... ..... ..... ..... .....  a   n1 an 2 an3 ..... ann  называются определители левого верхнего угла: m1  a11 , m2  a11 a12 a 21 a 22 a11 a12 a13 ..... a1n a a 22 a 23 ..... a 2 n a32 a33 ..... a3n 21 a11 a12 a13 m  a31 , m3  a 21 a 22 a 23 , … n ..... a31 a32 a33 a n1 76 ..... ..... ..... ..... an2 a n 3 ..... a nn Достаточный признак существования экстремума дифференцируемой функции. Рассматривается функция F  f ( x1 , x2 , .... , xn ) . Пусть в точке F 0 xi все частные производные функции M 0 ( x10 , x20 , .... , xn0 ) (i  1, 2, ... , n) и в точке M 0 ( x10 , x20 , .... , xn0 ) главные миноры матрицы  2F  2  x1  2F   x2 x1 Н   2F   x3x1  .....  2F   xn x1 2F x1x2 2F 2 x2 2F x3x2 ..... 2F xn x2 2F x1x3 2F x2 x3 2F 2 x3 ..... 2F xn x3 ..... ..... ..... ..... ..... 2F x1xn 2F x2 xn 2F x3 xn ..... 2F 2 xn              имеют знаки « , , , , , ...... » или « , , , , , , , ...... » (обратим внимание – первый знак – минус) Тогда в первом случае в точке M 0 функция имеет минимум, во втором случае — максимум. При любых других распределениях знаков главных миноров функция F  f ( x1 , x2 , ...., xn ) не имеет экстремума в точке M 0 . Замечание. Приведенная выше матрица вторых производных называется матрицей Гессе. Для функции двух переменных достаточное условие выглядит наиболее просто: 1) Определяют стационарные точки, приравнивая нулю все частные производные первого порядка и решая получившуюся систему. 2) Находят частные производные второго порядка функции F  Х   f ( x1 , x2 ) 2F A ; 2  x1 2F B ;  x1x2 2F C . 2  x2 77 3) Составляют  2F 2  x1  F  x1x2 2 определитель 2F  x1x2   F 2  x2 2 (матрицы Гессе) A B  AC  B 2 . B C Если в найденных точках   0 , то экстремум есть, причем при А<0 – это максимум, при А>0 – минимум. Если   0 , то экстремума в стационарной точке нет. Если   0 , то нужны другие исследования.  Поиск условного экстремума дифференцируемой F  f ( x1 , x2 , ...., xn ) нескольких переменных. функции Рассматривается функция F  f ( x1 , x2 , ...., xn ) . Требуется найти еѐ экстремум при ограничениях:  i ( x1 , x2 ,, xn )  bi , i  1, 2,т (7.4) Такой экстремум носит название «условный». Функцией Лагранжа для F  f ( x1 , x2 , ...., xn ) при ограничениях (7.4) называется функция L( x1 , x2 ,, xn , 1 , 2 ,, m )  m f ( x1 , x2 ,, xn )   i  bi   i ( x1 , x2 ,, xn )  (7.5) i 1  Необходимый признак существования условного экстремума Пусть функция F  f ( x1 , x2 , .... , xn ) при условиях (7.1) имеет экстремум в точке M 0 ( x10 , x20 , .... , xn0 ) и дифференцируема в этой точке. Все функции i  i ( x1 , x2 ,, xn ) также дифференцируемы. Тогда в точке M 0  L  0, j  1; 2;; n    xj  L   0, i  1; 2;; m    i или 78 (7.6) m  i  F   i   0, j  1; 2;; n   xj   x j i 1    b  0, i  1; 2;; m i i  (7.7) Как правило, решив систему (7.6), т.е. найдя точки M k ( x1( k ) , x2( k ) , .... , xn( k ) ) , подозрительные на условный экстремум, вопрос об отсутствии или наличии экстремума в них, а также о типе экстремума (max или min) решают исходя из физического смысла задачи. 7.3. Графическое решение задачи нелинейного программирования Графический метод можно использовать для решения задач НП, которая содержит две переменные x1 и x 2 , в частности, задач следующего вида: Z ( X )  f ( x1 , x2 )  max (min)  i ( x1 , x2 )  bi , i  1, 2,m Схема решения данной задачи мало отличается от схемы графического метода решения задачи ЛП. Решение сводится к следующим действиям: 1. Найти область допустимых ограничениями задачи. решений (ОДР), определяемую 2. Построить семейство линий уровня целевой функции f ( x1 , x2 )  С при различных значениях числового параметра С. 3. Определить направление возрастания целевой функции для задач на максимум или убывания – для задач на минимум. 4. Найти точку ОДР, через которую проходит линия уровня с наибольшим значением параметра С в задаче на максимум и наименьшим в задаче на минимум. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения. 5. Найти координаты точки оптимума и определить в ней значение целевой функции. Отметим, что в отличие от задачи ЛП точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может оказаться внутренняя точка этого множества. 79 Рис.7.2. Различные положения точки минимума Здесь ОДР изображена окрашенной, а линии уровня – пунктирные линии. Точка Х - точка минимума целевой функции. * Рассмотрим примеры решения задач нелинейного программирования с двумя переменными, причем их целевые функции и системы ограничений могут быть заданы в линейном и нелинейном виде. Также, как и в задачах линейного программирования, они могут быть решены графически.  Задача с линейной целевой функцией и нелинейной системой ограничений Пример 1. Найти минимальное и максимальное значение функции Z  f ( x1 , x2 )  3x1  4 x2 при условиях  x1 2  x2 2  25;   x1  x2  4;  x  0; x  0 . 2.  1 Решение. Построим область допустимых решений. Первое неравенство – дуга окружности АВ с центром в начале координат и с радиусом R=5. Второе неравенство геометрически представляет гиперболу вида x2  80 4 , x1 которая в виде кривой CD совместно с дугой окружности АВ образует ОДР. Рис. 7.3. Геометрическая трактовка задачи 1 3 Линия уровня – это прямая, имеющая уравнение x2   x1 (угловой 4 3 4 коэффициент этой прямой, как известно, равен  ). Решения задачи получим, если линию уровня будем параллельно самой себе перемещать в направлении ОДР. Там, где она в первый раз коснется ограничительной линии ОДР, будет находиться точка, определяющая минимум функции цели (т.к. переменные в функции цели имеют плюсовые множители). Там же, где линия уровня выйдет из ОДР, т.е. в точке касания с другой ограничительной линией, будет находиться решение на максимум функции цели. В первом случае это точка Е, во втором случае это точка N. Для нахождения первого решения продифференцируем гиперболы как функции в неявном виде и получим: x2   уравнение 4 . x12 Так как это угловой коэффициент касательной к гиперболе, то действительно равенство:  4 3   , 4 x12 81 * откуда получаем x1  4 , 3 и соответственно из уравнения линии * уровня находим x2  3 . Z min  3  4  4 3  8 3 3 Для нахождения координат точки уравнение окружности и получим:  2 x1  2 x2  x2  0 , откуда Очевидно также, что  x2   x1 x2 N теперь продифференцируем . x1 3  . 4 x2 Получаем второе решение: x1*  3; x2*  4 и Z max  25 .  Задачи с нелинейной целевой функцией и линейной системой ограничений Пример 2. Решить задачу нелинейного программирования графическим методом Z  f ( x1 , x2 )  x1  2  x2  4  min(max) 2 2 2 x1  x2  4; 2 x  3x  6;  1 2   x1  x2  11;  x1  0; x2  0. Решение: Определим область допустимых решений задачи, которая задается системой неравенств. С учетом неотрицательности переменных искомая область представляет собой четырехугольник ABCD, представленный на рис. 3.4. 82 Рис.3.4. Область допустимых решений задачи 2 Линии уровня целевой функции f ( x1 , x2 ) задаются следующим образом: f ( x1 , x2 )  const или в данном случае x1  22  x2  42  C 2 , C  0 Замечание. Геометрически уравнение x1  x0   x2  x20   R 2 окружность радиуса r  R с центром в точке Ox 0 ; x 0  . 2 2 1 1 представляет 2 Таким образом, линии уровня задачи представляют семейство концентрических окружностей радиуса С с центром в точке O2; 4 . Следует заметить, что точка O2; 4 расположена внутри области допустимых решений. В точке O2; 4 целевая функция имеет минимальное значение, то есть * Х min  2; 4; f min 2; 4  0 Очевидно, что точкой максимума является вершина С многоугольника решений. Координаты точки С являются решением системы 2 x1  x2  4; 7 26  x1  ; x2  .  3 3  x1  x2  11; Получаем оптимальное решение задачи на максимум 2 2  7 26   7 26   1   13  170 * Х max  ; . ; f max  ;       9 3 3   3 3   3  3  Пример 3. Решить задачу графическим методом. 83 f ( x1 , x2 )  x1  5  x2  1  min 2 2 При ограничениях 2 x1  x2  4; 2 x  3x  6;  1 2   x1  x2  11;  x1  0; x2  0. Обратим внимание на то, что область ограничения задана той же системой неравенств, что и в предыдущем примере. Поэтому воспользуемся рис.3.4, на котором представлено графическое изображение ОДР. Линии уровня целевой функции в данном примере - это семейство окружностей с центром O5; 1 , причем центр находится вне области допустимых решений задачи. Минимум целевой функции достигается в точке касания окружности с центром O5; 1 с прямой АD. Найдем координаты этой точки. Векторградиент целевой функции определяется следующим образом:   f f grad f   ;  x  1 x2    2x1  5; 2x2  1  2 x1  10; 2 x2  2 .  Как известно, градиент перпендикулярен линии уровня функции, следовательно, в данном случае перпендикулярен касательной окружности в точке касания с прямой АD  уравнение AD : 2 x1  3x2  6 . Таким  образом, он коллинеарен нормальному вектору n  2;  3 границы АD области допустимых решений задачи, что соответствует условию: 2 x1  10 2 x2  2  , 2 3 или  3x1  15  2 x 2  2;  3x1  2 x 2  17 . С учетом уравнения прямой АD: 2 x1  3x2  6 , получаем точку минимума: Ответ: X 1*  3; 4, f min 3; 4  13. Замечание: Координаты точки касания окружности и границы АD можно определить и другим способом. Радиус в точку касания перпендикулярен 2 x1  3x2  6 касательной (прямая АD). Угловой коэффициент прямой k AD  84 2 . 3 Уравнение прямой, перпендикулярной AD, найдем как уравнение прямой проходящей через точку (5, 1) - центр окружности, и имеющей 3 2 угловой коэффициент k   . x2  1   3 x1  5   3x1  15  2 x2  2;  3x1  2 x2  17 . 2 Решим теперь систему 2 x1  3x2  6;  x1  3; x2  4 .  3 x  2 x  17 2  1 Ответ: X 1*  3; 4, f min 3; 4  13. Ответы, естественно, совпадают.  Задачи с нелинейной целевой функцией и нелинейной системой ограничений Пример 4. Найти глобальные экстремумы функции Z  x1  2  x2  1 2 2  x12  x2 2  16; при ограничениях:   x1  0; x2  0. Рис.3.5. Область допустимых решений задачи 4 Решение. Областью допустимых решений является окружность с радиусом 4, расположенная в первой четверти. Линиями уровня будут окружности с центром в точке O1 (2, l). Глобальный минимум достигается в точке O1. Глобальный максимум — в точке А (0, 4), при этом Z  А  0  2  4  1  13 . 2 2 85 Ответ. Глобальный минимум, равный нулю, достигается в точке O1 (2, l), глобальный максимум, равный 13, находится в точке А (0, 4). Пример 5. Найти глобальные экстремумы функции Z  x1  x2 ограничениях: 2 2 при  x1 x2  4;  x  x  5;  1 2  x1  7;  x  6;  2  x1  0; x2  0. Решение. x1 x2  4 – гипербола x2  4 , x1 x1  x2  5 – прямая линия x2  5  x1 . Рис. 7.6. Область допустимых решений задачи 5 Область допустимых решений (рис.3.6) не является выпуклой и состоит из двух частей - криволинейных четырехугольников ABCD и EFGH , ограниченных осями координат, прямыми x1  7 , x2  6 , x1  x2  5 и гиперболой x1 x2  4 . 86 Линиями уровня являются окружности с центром в точке O (0, 0).  x1 x2  4, Найдем координаты точек А и Е, решая систему   x1  x2  5. Получим А (1, 4), Е(4, 1). В этих точках функция имеет глобальные минимумы, равные 17. Найдем координаты точек D и F, решая системы  x1 x2  4,  x1 x2  4,    x2  6,  x1  7, Откуда получаем D (2/3, 6) и Z(D) = 328/9, F (7, 4/7) и Z(F) = 2417/49. Ответ. Целевая функция имеет два глобальных минимума, равных 17, в точках А (1, 4) и E (4, 1), глобальный максимум, равный 2417/49, достигается в точке F (7, 4/7). Тема 8. Классические методы оптимизации 8.1. Задача безусловной оптимизации Рассмотрим конкретный пример. Фирма производит продукцию двух видов в количествах x1 и x 2 . Задана функция полных издержек Qx1 , x2  . Цены этих изделий на рынке равны С1 и С 2 . Определить, при каких объемах выпуска изделий достигается максимальная прибыль, найти эту прибыль. Qx1 , x2   7 x12  8x1 x2  3x22  90; С1  110, С2  70 . Решение. Пусть Z  f x1 , x2  - функция прибыли (целевая функция), тогда   Z  f x1 , x2   110 x1  70 x2  7 x12  8 x1 x2  3x22  90   110 x1  70 x2  7 x12  8 x1 x2  3x22  90. Перед нами задача нахождения безусловного экстремума функции двух переменных. Применим необходимое условие экстремума. Найдем первые частные производные функции f x1 , x2  : 87 f f  110  14 x1  8x2 ;  70  8x1  6 x2 . x1 x2 Найдем критические точки графика функции f x1 , x2  , приравняв частные производные нулю и решив систему: 110  14 x1  8x2  0; 14 x1  8 x2  110; 7 x1  4 x2  55;     70  8 x1  6 x2  0; 8x1  6 x2  70; 4 x1  3x2  35; Решим систему методом Крамера:  7 4 4 3  21  16  5; 1  55 4 35 3  25;  2  7 55 4 35  25. Отсюда x1  5; x2  5 . Следовательно, точка М 5; 5 - критическая точка. Проверим ее на экстремум в соответствии с достаточным условием экстремума. Найдем производные второго порядка 2F A  14; 2  x1 Составим  и 2F 2  x1 2F  x1x2 2F  x1x2 2F 2  x2 2F B  8;  x1x2 вычислим   14  8 8 6 2F C  6. 2  x2 определитель (матрицы Гессе)  20  0 Таким образом экстремум есть, а т.к. А = -16 < 0, то это максимум. Следовательно, при объемах выпуска x1  5 и x2  5 достигается максимальная прибыль равная Z  f x1 , x2   110  5  70  5  7  25  8  25  3  25  90  360 . Схема нахождения безусловного экстремума функции п переменных аналогична и отличается только сложностью решения соответствующих систем. Выше речь шла об локальном экстремуме функции п переменных. Как правило, в практических задачах необходимо определять наибольшее и наименьшее значение функции (глобальный экстремум) в некоторой области. 88 Говорят, что функция Z  f  X  имеет в точке X 0 заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f  X   f X 0  или f  X   f X 0  соответственно выполняется для любых точек области D. Если область D замкнута и ограничена, то дифференцируемая функция Z  f  X  достигает в этой области своих набольшего и наименьшего значения или в критической точке, или в граничной точке области (теорема Вейерштрасса). 8.2. Метод множителей Лагранжа Одним из наиболее общих подходов к решению задачи поиска локального минимума или максимума функции при наличии ограничений на ее переменные (задача условной оптимизации) является метод Лагранжа. Рассмотрим частный случай задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения. Кроме того, отсутствуют условия неотрицательности переменных, а функции f ( x1 , x2 ,...xn ) и i ( x1 , x2 ,...xn ) непрерывны вместе со своими частными производными. Z  f ( x1 , x2 , ...., xn )  max (min);  i ( x1 , x2 ,...xn )  bi ; i  1, 2,..., m. В курсе математического анализа данную задачу называют задачей на условный экстремум или классической задачей оптимизации. 1 , 2 ,, m , Чтобы найти решение этой задачи вводят переменные называемых множителями Лагранжа, и составляют функцию Лагранжа m L( x1 , x2 , , xn , 1 , 2 , , m )  f ( x1 , x2 , , xn )   i  bi  i ( x1 , x2 , , xn )  , i 1 которая достигает экстремума в тех же точках, что и целевая функция Z(X ). Далее, находят частные производные функции Лагранжа по всем переменным x j и i . Для нахождения стационарных точек функции Лагранжа приравнивают частные производные нулю и рассматривают систему из m+n уравнений: 89  L  0, j  1; 2;; n   x j  L   0, i  1; 2;; m    i Всякое решение системы уравнений определяет точку X  ( x1 , x2 ,...xn ) , в которой может иметь место экстремум функции f ( x1 , x2 ,...xn ) . Среди этих решений после дополнительного анализа (проверки достаточного признака экстремума) отбираются такие, которые действительно являются точками локального оптимума. После сравнения значений целевой функции в этих точках находится точка, являющаяся глобальным оптимумом. Итак, определение экстремальных точек методом множителей Лагранжа включает следующие этапы: 1) составляют функцию Лагранжа; 2) находят частные производные от функции Лагранжа по переменным x j и i , приравнивают их нулю; 3) решая данную систему уравнений находят критические точки, в которых целевая функция может иметь экстремум; 4) среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значение функции в этих точках. Подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений, к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума. Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений. При решении конкретных практических задач обычно используются прямые методы, основанные на итерационных процессах вычисления и сравнения значений оптимизируемых функций. К таким методам относят градиентные методы решения задач безусловной оптимизации (в данном курсе мы их не рассматриваем). Пример 1. По плану производства предприятию надо изготовить 200 изделий. Эти изделия изготавливаются по двум технологиям. Производственные затраты 90 на изготовление п изделий первым способом составляют 4n  n , а вторым 2 — 8n  n 2 . Сколько изделий каждого вида надо изготовить, чтобы затраты на их производство были бы минимальными? Решение. Обозначим x1 — количество изделий, изготавливаемых по первому технологическому способу, производство составят x2 — по второму. Суммарные затраты на их Z x1 x2   4 x1  x1  8x2  x2 . При этом общее число изделий должно составлять 200 единиц, т.е. 2 2 x1  x2  200 . Тогда математическая модель задачи будет иметь вид; Z x1 x2   4 x1  x1  8 x2  x2  min 2 2  x1  x2  200;   x1  0; x2  0. Для решения этой задачи составим функцию Лагранжа L( x1 , x2 ,  )  4 x1  x1  8x2  x2   200  x1  x2  . Найдем ее частные производные и приравняем их нулю 2 2  L f      4  2 x1   ;   x  x  x 1 1 1  4  2 x1    0;  L f      8  2 x 2   ;  8  2 x 2    0;   x2   x2  x2 200  x  x  0. 1 2   L  200  x  x .  1 2   Вычитая из второго уравнения первое для исключения  , получим систему 4  2 x2  2 x1  0;  x1  101; x2  99  200  x  x  . 1 2  Таким образом, в соответствии с необходимым условием существования экстремума получена стационарная точка М(101;99), в которой может быть условный экстремум целевой функции. Дальнейшее исследование будем проводить так, как это делалось в случае нахождения безусловного экстремума функции двух переменных. Найдем частные производные второго порядка A 2L  x1 2  2; 2L B  0;  x1x2 C 2L  x2 2  2. 91 Для данного примера частные производные постоянны и не зависят от переменных x1 , x2 . Вычислим определитель A B B C  2 0 0 2 40 Поскольку определитель больше нуля, то в найденной точке экстремум, причем А>0, следовательно, в точке М(101;99) функция Z имеет минимум: Z x1 x2   4 101  1012  8  99  992  21198 (ден. ед.) Ответ: При изготовлении 101 изделия по первой технологии и 99 - по второй предприятие будет иметь минимальные затраты в размере 21198 ден.ед. Замечание 1. Если функцию Z (X ) интерпретировать как доход (стоимость), соответствующий плану X  ( x1 , x2 ,...xn ) , а i ( x1 , x2 ,...xn ) - издержки i-того ресурса, bi - как объемы ресурсов, то множители Лагранжа i показывают, как изменится максимальный доход (минимальная стоимость), если количество ресурса i -го вида увеличить на единицу. Замечание 2. Основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной, тем самым расширяя арсенал доступных средств решения задач НП. Однако следует заметить, что задача решения системы уравнений, к которой сводится данный метод, в общем случае достаточна сложна. Тема 9. Модели выпуклого программирования Рассмотрим теперь задачу НП с условиями неотрицательности переменных и ограничениями в виде неравенств: Z ( X )  f ( x1 , x 2 ,  x n )  max  i ( x1 , x 2 ,  x n )  bi ;  i  1, 2,  m ,   x j  0;  j  1, 2,  n , f x1 , x2 , xn  и i x1 , x2 , xn  некоторые нелинейные функции n переменных. Для решения задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сформулированы дополнительные ограничения относительно свойств функций f и  i есть где 92 эффективные методы решения. В частности, это условие, что функции f и  i  i  1, 2,m являются выпуклыми (вогнутыми). 9.1. Выпуклые функции Введем необходимые понятия. Ранее давалось понятие выпуклого множества n точек: множество M  R называется выпуклым, если для любых точек X 1 , X 2  M и любого   0;1 выполняется условие X 1  1   X 2  М . Содержательно это означает, что если M  R выпукло, то вместе с любыми двумя точками X 1 , X 2  M оно должно содержать и все точки отрезка, соединяющего эти точки. n  Определение 1. Функция F  X   f x1 , x2 , xn  , заданная на выпуклом множестве М п-мерного пространства, называется выпуклой (выпуклой вниз) на этом множестве, если для любых X 1 , X 2  M и числа   0;1 выполняется неравенство F X 1  1   X 2   F  X 1   1   F  X 2  (9.1) Рис. 9.1. Выпуклая функция По определению F  X  является выпуклой, если значение ее от выпуклой комбинации значений аргумента X 1 и X 2 не больше, чем выпуклая комбинация значений F  X  при этих значениях аргумента. Геометрически это означает, что график такой функции лежит ниже отрезка, соединяющего любые две точки. Если в условии (9.1) знак неравенства  заменить на определение вогнутой (выпуклой вверх) функции.  , то получим 93 F X 1  1   X 2   F  X 1   1   F  X 2  Рис. 9.2. Вогнутая (выпуклая вверх) функция Геометрически это означает, что график такой функции лежит выше отрезка, соединяющего любые две точки. Если в условии (9.1) неравенство выполняется как строгое, то функция называется строго выпуклой или строго вогнутой. Для дифференцируемых функций удобней использовать другое определение выпуклой функции. * Функция F  X   f x1 , x2 , xn  является выпуклой в точке x , если матрица ее вторых частных производных (матрица Гессе)     2 f x*  2  x1   2 f x*   x2 x1 * H x    2 f x*   x3x1  .....   2 f x*   xn x1            2 f x* x1x2  2 f x* 2 x2  2 f x* x3x2 .....  2 f x* xn x2          2 f x* x1x3  2 f x* x2 x3  2 f x* 2 x3 .....  2 f x* xn x3       ..... ..... ..... ..... .....     2 f x* x1xn  2 f x* x2 xn  2 f x* x3 xn .....  2 f x* 2 xn                  положительно определена. Для функции одной переменной это означает, что функция f(x) лежит ниже хорды, соединяющей любые две точки ее графика. Проверить положительную или отрицательную определенность числовой матрицы можно, например, по критерию Сильвестра: 94 1) матрица А является положительно определенной, если все ее угловые миноры больше нуля  a11   a21 A   a31   ..... a  n1 a13 a a12 m2  11 0, a21 a22 m1  a11  0 , a11 ..... a1n   a22 a23 ..... a2 n  a32 a33 ..... a3n   ..... ..... ..... .....  an 2 an3 ..... ann  a12 a12 a13 ..... a1n a21 a22 a23 ..... a2 n mn  a31 a32 a33 ..... a3n  0 a11 a12 m3  a 21 a 22 a31 a32 a13 a 23  0 , … a33 . ..... ..... ..... ..... ..... an1 an 2 an 3 ..... ann 2) Матрица А является отрицательно определенной, если знаки угловых миноров чередуются m1  a11  0 , a11 a12 a13 a11 a12 m2   0 , m3  a 21 a 22 a 23  0 , …, a21 a22 a31 a32 1n mn  0 . a33 Или все угловые миноры удовлетворяют неравенству  1 mi  0 . n Пример. Показать, что функция F  X   2 х12  х22  х1 х2  5х1  6 х2  8 является выпуклой. Решение. Находим частные производные: F F  4 х1  х2  5;  2 х2  х1  6; x1 x2 2F 2F 2F  4;  1; 2 2 2 x1x2 x1 x2 Матрица вторых частных производных имеет вид A  4 1 1 2 . 95 Ее главные миноры 1  4  0;  2  7  0 . Значит, функция F является положительно определенной и, следовательно, строго выпуклой при всех X.  Определение 2. Говорят, что множество допустимых решений задач нелинейного программирования (ЗНП) удовлетворяет условию регулярности (условию Слейтера), если существует, по крайней мере одна точка Х 0 , принадлежащая области допустимых решений такая, что  i ( Х 0 )  bi ;  i  1, 2,m  Определение 3. Задача задачей выпуклого программирования (ЗВП), если целевая функция Z ( X )  f ( x1 , x2 , xn ) (3.6) называется является вогнутой (выпуклой), а ОДР, определяемая системой неравенств, – только выпуклая. Теорема. Любой локальный экстремум задачи выпуклого программирования является и глобальным экстремумом. Задача выпуклого программирования состоит в отыскании такого решения системы ограничений, при котором выпуклая (вниз) целевая функция достигает минимального значения либо выпуклая вверх своего максимального значения. Для решения ЗВП применяется метод множителей Лагранжа.  Определение 4. Функцией Лагранжа задачи выпуклого программирования (3.6) называется функция: m L( x1 , x2 ,, xn , y1 , y 2 ,, y m )  f ( x1 , x2 ,, xn )   yi  bi   i ( x1 , x2 ,, xn )  i 1 Здесь y i – множители Лагранжа.  Определение 5. Точка X  ;Y 0  ( x10 , x20 ,, xn0 , y10 , y20 ,, ym0 ) седловой точкой функции Лагранжа, если выполняется L( x1 , x2 ,, xn , y10 , y20 ,, ym0 )  L( x10 , x20 ,, xn0 , y10 , y20 ,, ym0 )   L( x10 , x20 ,, xn0 , y1 , y2 ,, ym ) 96 называется для всех x j  0;  j  1, 2,n и yI  0;  i  1, 2,m . Рис. 9.3. Геометрическая интерпретация седловой точки функции Лагранжа Замечание: в определении седловой точки подразумевается, что при Х* минимизирует функцию L(X, Y*) По всем Х, а У* максимизирует функцию F(X*, Y) по всем У. В теории нелинейного программирования центральное место занимает теорема КунаТаккера, обобщающая классический метод множителей Лагранжа на случай, когда ограничения нелинейной задачи наряду с ограничениями в виде равенств содержат также и ограничения в виде неравенств. 9.2. Теорема КунаТаккера Для задачи выпуклого программирования, множество допустимых решений X 0  ( x10 , x20 ,, xn0 ) которой обладает свойством регулярности, точка является оптимальным решением тогда и только тогда, когда существует такой вектор Y 0  ( y10 , y20 ,, ym0 )  y I  0; i  1, 2,m , что X ;Y 0  – седловая точка функции Лагранжа Если предположить, что функции f и  i непрерывно дифференцируемы, то теорема Куна – Таккера может быть дополнена аналитическими выражениями, определяющими необходимые и достаточные условия того,   чтобы точка X ;Y была седловой точкой функции Лагранжа, т. е. являлась решением задачи выпуклого программирования: 97  L0  x  0; j  1,2,..., n;  j  0 L0  0; j  1,2,..., n; x j  x j   x 0  0; j  1,2,..., n;  j   L0  0; i  1,2,..., m;  yi   y 0 L0  0; i  1,2,..., m;  i x j   yi0  0; i  1,2,..., m. где L0 L0 и – значения соответствующих частных производных функции x j yi Лагранжа, вычисленных в седловой точке. Процесс нахождения решения задачи выпуклого программирования включает следующие этапы:  проверка принадлежности задачи выпуклому программированию:  составление функции Лагранжа;  составление необходимых и достаточных условий существования седловых точек для функции Лагранжа;  нахождение координаты седловой точки функции Лагранжа и проверка, будет ли она являться точкой максимума, либо установление факта ее отсутствия;  нахождение значения целевой функции при найденном оптимальном решении. 2 Пример. Найти минимум функции F ( x1 , x2 )  x1  x2 при ограничениях  x1  1;  2 2  x1  x 2  10;  x  0.  2 Функция F ( x1 , x2 )  x12  x2 сумму линейной функции является вогнутой, т.к. представляет собой f1   x2 , которую можно считать вогнутой, и 2 квадратичной f 2   x1 , являющейся вогнутой (парабола выпуклостью вверх). 98 Система ограничений образует выпуклую область – это точки внутри окружности x12  x22  10 , ограниченной полуплоскостями x1  1 и x2  0 . Поэтому задача является задачей выпуклого программирования. Решение. Составим функцию Лагранжа.  1( х1 , х2 )  1  х1 ;  2( х1 , х2 )  10  x12  x22 ;  3( х1 , х2 )   х2 ; L X ;Y   x12  х2  y1 1  х1   y 2  10  x12  x22   y3  х2 . Система необходимых и достаточных условий существования седловой точки для функции Лагранжа имеет вид: 2 x1  2 y 2 x1  y1  0 L0  0:  ,  1  2 y x  y  x j 2 2 3   x1 2 x1  2 y 2 x1  y1   0 L x 0j 0  0 :  , x j  x 2  1  2 y 2 x 2  y3   0 x 0j  0; j  1,2; L0  0: y i 1  x1  0  2 2  10  x1  x 2  0 ,  x  0  2  y1 1  x1   0 L  y i0 0  0 :  y 2  10  x12  x 22   0, x j y x  0  3 2 y i0  0; i  1,2. Предположим, что 1  x1  0 - активное ограничение, то есть оптимальное решение лежит на этой прямой. Тогда 1  0 . Подставив х1  1 в систему, получим: 99 2  2 y 2  y1  0,  1  2 y  y  0, 2 3  2  10  1  x 2  0,   x 2  0, 2  2 y  y  0,  2 1   x 2  1  2 y 2 x 2  y 3   0,  y  10  x 2  x 2  0, 1 2  2 (*)  y 3 x 2  0,  y  0, y  0, y  0, 2 3  1  x1  1, x 2  0.   Если предположить, что х2  0 , а y3  0 (в системе это условие помечено звездочкой *), то система упростится еще:  y1  2, 2  y1  0,  1  y  0,  y 3  1, (*) 3   y1  2, 2  y1  0,  y  0, y  0, y  0, 2 3  1  x1  1, x 2  0. Но в этом случае нарушается условие неотрицательности для множителей yi  0 , т.к. y3  1 (условие со звездочкой). Следовательно, предположение, что х2  0 не верно. Пусть теперь х2  0 , т.е. данное ограничение пассивно. Тогда y3  0 . 2  2 y 2  y1  0,  1  2 y  0, 2   10  1  x 22  0,  2  2 y 2  y1  0,   1  2 y 2 x 2  0,  y  9  x 2  0, (*) 2  2  y1  0, y 2  0, y 3  0,  x  1, x  0. 2  1   Предположим, что х2  3, а у2  0 , тогда y1  0, y2  0, y3  0, x1  1, x2  3. Полученное решение не противоречит условиям теоремы, следовательно, является искомым. 100   Ответ: Х  1, 3, Z min Х  2 . Раздел 4. Динамическое программирование Тема 10. Общая остановка задачи динамического программирования Рассмотренные ранее задачи линейного и нелинейного программирования относятся к так называемым одношаговым или одноэтапным задачам. Решение этих задач находилось за один этап. Динамическое программирование (ДП) — метод оптимизации, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги). Такие операции называются многошаговыми. Впервые основные принципы оптимального управления многошаговыми процессами наиболее полно и систематизировано были сформулированы в 50-х годах ХХ века американским математиком Р. Беллманом (Беллман Ричард Эрнест (1920– 1984); американский математик; основные труды по вычислительной математике и теории оптимального управления). К числу задач, для которых может применяться метод ДП, относится большинство задач планирования на несколько периодов времени, тогда шагом в таких задачах является один плановый период. Однако методы ДП успешно применяются и при решении задач, в которых фактор времени не учитывается. Примером такой задачи является распределение дефицитных капитальных вложений между новыми направлениями их использования. Рассмотрим некоторую техническую или экономическую систему, или объект: техническое средство, предприятие, производственное объединение, отрасль промышленности, регион и т.д. Состояние системы – обозначим еѐ через S – в определѐнный момент характеризуется набором параметров, которые могут иметь различный экономический смысл и представлять собой, например, производственные мощности, обеспеченность ресурсами, штат сотрудников, себестоимость продукции, объѐм средств на счѐте предприятия и т.п. Параметр, характеризующий состояние системы, называется переменной состояния, которая может принимать значения из некоторого множества допустимых значений. Состояние управляемой системы S может меняться под влиянием различных факторов. Наиболее важную роль среди них играет воздействие со стороны 101 управляющего субъекта, осуществляемое путѐм выбора им надлежащих значений, называемых управляющими переменными, или просто управлениями. В различных конкретных задачах в качестве управлений могут выступать, например, объем капиталовложений в отдельные предприятия, состав работающего оборудования, режим его эксплуатации, количество потребляемых ресурсов, объѐм подлежащих производству товаров, цены на производимую продукцию, количество принимаемых работников и т.п. В результате управления (в динамическом программировании решение принято называть управлением) система (объект управления) S переводится из  начального состояния s0 в состояние S . Предположим, что управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных – переменную состояния s и переменную управления х. Обозначим через xk управление на k -м шаге ( k = 1,..., n ). Переменные xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми ( xk может быть числом, точкой в n-мерном пространстве, качественным признаком). Пусть Х x1 , x2 ,.., xп  - управление, переводящее систему S из начального  состояния s0 в состояние S = s п . Обозначим через s k состояние системы после k-того шага управления. Получим последовательность состояний s0 , s1 , s2 ,..., sk 1 , s ,..., sn , которую изобразим кружками (рис. 10.1) Рис. 10.1. Схема поэтапного управления 102 Показатель эффективности рассматриваемой управляемой операции – целевая функция – зависит от начального состояния и управления Z  f (s0 , X ) . Задача динамического программирования формулируется следующим образом: требуется определить такое управление Х*, переводящее систему S из начального состояния S 0 в конечное состояние S n , при котором целевая функция принимает наибольшее (наименьшее) значение.   Z  f s0 , X *  extr Особенности математической модели ДП: 1) задача оптимизации формулируется как конечный многошаговый процесс управления; 2) целевая функция Z является аддитивной функцией от показателя эффективности каждого шага (т.е. является суммой целевых функций каждого шага). Таким образом, если обозначить показатель эффективности k- того шага через Z k  f k sk 1 , хk , k  1, 2, ..., n , (10.1) n то Z   f k sk 1 , хk  k 1 3) выбор управления xk на каждом шаге зависит только от состояния системы к этому шагу sk 1 и не влияет на предшествующие шаги (нет обратной связи); 4) состояние системы s k после каждого шага управления зависит только от предшествующего состояния системы sk 1 и управляющего воздействия xk (отсутствие последействия), записывается в виде уравнений Сформулированное положение sk  k sk 1 , X k , k  1,2,..., n (10.2) 5) на каждом шаге управление xk зависит от конечного числа управляющих переменных, а состояние системы s k зависит от конечного числа параметров; 103 6) оптимальное управление представляет собой арифметический вектор X*, определяемый последовательностью оптимальных пошаговых управлений: X * х1* , х2* ,..., хn*  , число которых и определяет количество шагов задачи. Как указывалось ранее, в основе вычислительных алгоритмов динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. 10.1. Принцип оптимальности Беллмана Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию. Беллманом сформулированы и условия, при которых принцип верен. Основное требование – процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги. Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом посредством изменения управляемых параметров на каждом шаге, и, следовательно, позволяет воздействовать на ход процесса, изменяя на каждом шаге состояние системы. Вместе с тем ДП свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо 104 использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний. 10.2. Уравнения Беллмана Вместо исходной задачи с фиксированным числом шагов п и начальным состоянием s0 рассмотрим последовательность задач, полагая последовательно п = 1,2,… при различных состояниях s – одношаговую, двухшаговую и т.д., используя принцип оптимальности. Введем ряд новых обозначений. Рассмотрим п-й шаг: sп1 - состояние системы к началу п-го шага, sп  sˆ конечное состояние; X п - управление на п-ном шаге, а f п sп1 , Х п  - целевая функция (выигрыш) на п-го шага. Согласно принципу оптимальности, X п надо выбирать так, чтобы для любых состояний sп1 получить максимум целевой функции на этом шаге (предполагается, что решаем задачу на максимум). * Обозначим через Z п sп1  - максимум целевой функции, т.е. показателя эффективности, п-го шага при условии, что к началу последнего шага система S была в произвольном состоянии sп1 , а на последнем шаге управление было оптимальным. Z п sп1 *  - называется условным максимумом целевой функции на п-м (последнем) шаге. Очевидно, что Z п sп1   max f n sп1 , X n  * (10.3) Максимизация ведется по всем допустимым управлениям X п . * Решение X п , при котором достигается Z п sп1  , также зависит от sп 1 и называется условным оптимальным управлением на п-м шаге и * обозначается Х п sп1  . 105 Решив одномерную задачу локальной оптимизации по уравнению (4.3), * * найдем для всех возможных состояний sп 1 две функции Z п sп1  и Х п sп1  Рассмотрим теперь двухшаговую задачу: присоединим к п-му шагу (п-1)-й. Для любых состояний sп2 , произвольных управлений X п1 и оптимальном управлении на п-ном шаге значение целевой функции на двух последних шагах равно: f n1 sп2 , X n1   Z п sп1  . * (10.4) Согласно принципу оптимальности для любых sп2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (п-м) шаге приводило бы к максимуму целевой функции на двух последних шагах. Следовательно, нужно найти максимум последней суммы (4.2). Максимум * этой суммы зависит от sп2 , обозначается Z п1 sп2  и называется условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Соответствующее управление на п-1 шаге называется условным оптимальным управлением на п-1 шаге   Z п1 sп2   max f n sп2 , X n1   Z п sп1  * * (10.5) Следует обратить внимание на то, что выражение в фигурных скобках зависит только от sп2 и X п1 , т.к. sп 1 можно найти из уравнения состояний (4,2) при к = п-1: sп 1  п 1 sп  2 , X п 1 , * И подставить в него вместо sп 1 в функцию Z п1 sп2  . В результате максимизации только по одной переменной X п1 согласно уравнению (4.5) вновь получаются две функции: Z п1 sп2 * и Х п1 sп2 * . Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется (п-2)-й и т.д. 106 Z k sk 1  Обозначим через * условный максимум целевой функции, полученный на n-k+1 шагах, начиная с k-ого до конца, при условии, что к началу k-ого шага система находится в состоянии sk 1 . Фактически эта функция равна Z k sk 1   max * n  f s xk ,...,xn  ik Z Тогда * k 1 i i 1 , Xi  n sk  xmax  fi si1, X i  . ,...,x  k n i k 1 Целевая функция на n-k последних шагах при произвольном управлении X k на k-том шаге и оптимальном управлении на последующих шагах равна f k sk 1 , X k   Z k 1 sk * . Согласно принципу оптимальности, X k выбирается из условия максимума этой суммы, т.е.   Z k sk 1   max f k sk 1 , Xk   Z k 1 sk  ; * xk  * k  n  1, n  2, ...2,1 (10.6) Уравнения (4.6) называют уравнениями Беллмана. Это рекуррентные соотношения, позволяющие найти предыдущие значения функции, зная последующие. Процесс решения уравнений (4.5), (4.6) называется условной оптимизацией. Далее следует процесс так называемой обратной прогонки, когда с помощью уравнений состояний и условных оптимальных уравнений находим оптимальное решение задачи ДП X *   X1*, X 2 *,...X n * Подробнее этот процесс продемонстрируем далее на примерах. 10.3. Задача о выборе кратчайшего расстояния Математический аппарат ДП, основанный на методологии пошаговой оптимизации, может быть использован при нахождении кратчайших 107 расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей к поставщикам, повышение производительности транспорта за счет сокращения непроизводительного пробега и др. Пример 1. Пусть транспортная сеть состоит из 10 узлов. На рисунке показаны сеть дорог и стоимость перевозки единицы груза между пунктами сети. Ребра являются вариантами выбора решения. Необходимо определить маршрут доставки груза из пункта 1 в пункт 10, обеспечивающий наименьшие транспортные расходы. Рис.10. 2. Модель транспортной сети Стоимость проезда из пункта i в пункт j равна cij , и элементы этой матрицы занесены в схему. Требуется найти оптимальный маршрут из 1-го пункта в 10-й. В задаче имеется ограничение — двигаться по изображенным на схеме маршрутам можно только слева направо, то есть, попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5-й или 6-й. Эта особенность транспортной сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем считать, что пункт принадлежит к k-му поясу, если из него можно попасть в конечный пункт ровно за k шагов, т.е. с заездом ровно в (k–1)-й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 — ко второму, 2, 3 и 4 — к третьему и 1 — к четвертому. Тогда на k -м шаге будем находить оптимальные маршруты перевозки груза из пунктов k-го пояса до конечного пункта. 108 Оптимизацию будем производить с конца процесса, и потому, дойдя до k-то шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перевозимый из первого пункта. Введем обозначения: k – номер шага (k = 1, 2, 3, 4); i – пункт, из которого осуществляются перевозки (i = 1,2,..., 9); j – пункт, в который доставляется груз (j = 2, 3,..., 10); cij – стоимость перевозки груза из пункта i в пункт j. Fk i  - минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта. Очевидно, что минимум затрат на перевозку груза из пунктов k-то пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номер i пункта, узел, принадлежащий k-му поясу, будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-то пояса, принимается решение о перемещении груза в один из пунктов (k – 1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номер j пункта (k – 1)-го пояса будет переменной управления на k-м шаге. Для первого шага управления (k = 1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. k  1; F1 i   ci ,10 Для последующих шагов затраты складываются из двух слагаемых – стоимости перевозки груза cij из пункта i k-го пояса в пункт j (k – 1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. Fk-1(j). Функцией Беллмана на k-м шаге решения задачи Fk i  назовѐм минимально возможную стоимость проезда из города i (k-гo пояса) до конечного пункта. Таким образом, функциональное уравнение Беллмана будет иметь вид: Fk i   min cij  Fk 1  j  по всем j  j  2,...,10 Минимум затрат достигается на некотором значении j*, которое является оптимальным направлением движения из пункта i в конечный пункт. 109 На четвертом шаге попадаем на 4-й пояс; состояние системы становится определенным i =1. Функция F4(1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k – 1)-м шаге становится определенным. Решим задачу. I этап. Условная оптимизация 1-й шаг. k = l. F1 (i) = сi10 . i/J 7 8 9 2-й шаг. k = 2. F1(i) 7 9 11 10 7 9 11 J* 10 10 10 F2 i   min cij  F1  j  j i/J 8 7 8+7 5+7 5 6 3-й шаг. k = 3. 6+9 9 – – 4+11 J F2 (i) 15 12 7, 8 7 F3 (i) = min cij + F2 (J)} J i/J 2 3 4 4-й шаг. k = 4. 5 4+15 6 – – – 3+12 9+12 J F3(i) 19 15 21 * 5 6 6 F4 i   min cij  F3  j  j i/J 1 2 7+19 3 5+15 4 6+21 II этап. Безусловная оптимизация 110 F3(i) 20 J 3 * * Минимально возможная стоимость проезда из пункта 1 в пункт 10 V = F4(l) = 20. Она достигается, если из 1-го пункта отправиться в 3-й. Попав в него, необходимо, как видно из предыдущей таблицы, двигаться в пункт 6, затем – в пункт 7 и из него – в конечный пункт, т. е. оптимальный маршрут 1→3→ 6 →7→10. Рассмотрим теперь еще один тип задач динамического программирования. 10.4. Задача о распределении средств между несколькими предприятиями Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между п различными предприятиями (объектами, работами и т.д.) так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения. Разобьем процесс оптимизации на n шагов, и на k-м шаге будем оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом, естественно, считать, что в остальные предприятия (с 1го по (k–1)-е) тоже вкладываются некоторые средства, и потому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая сумма меньшая или равная х . Эта величина и будет являться переменной состояния системы. Переменной управления на k-м шаге назовем величину xk средств, вкладываемых в k-е предприятие В качестве функции Беллмана f k  x  на k-м шаге в этой задаче можно выбрать максимально возможную прибыль, которую можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось xk средств. Введем обозначения: xi — количество ресурсов, выделенных i-му предприятию (i = 1, n ); f i xi  — функция полезности, в данном случае это величина дохода от использования ресурса xi, полученного i-м предприятием; Z k s k 1  * — наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий. 111 Прибыль каждого предприятия в зависимости от количества х вложенных средств определяется табл. 1. Как правило, эти табличные данные получены предприятиями экспериментально. Таблица 10.1 f 2 x  f1 x  x x1 f1 x1  f 2 x1  x2 f1  x 2  f 2 x2  … … f1  x т  xт f п x  … … f 2 xт  … f п x1  … … … f п x2  … f п xт  Сформулированную задачу можно записать в математической форме: n Z k x   max  f i xi  i 1 n при ограничениях: x i 1 i  x; xi  0, i  1,2,..., n Рассмотрим конкретную задачу по распределению капиталовложений между предприятиями. Пример. Планируется деятельность четырех промышленных предприятий (системы) на очередной год. На развитие производства выделено 60 млн. ден.ед. Денежные средства выделяются предприятиям в размерах, кратных 20 млн. ден.ед. Каждым предприятием разработаны планы использования этих средств, определена прибыль, которую получит каждое предприятие в результате использования выделенных средств. Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей. Т а б л и ц а 10.2 Выделенные Прибыль предприятий, млн. ден.ед. средства, П1 П2 П3 П4 млн. ден.ед. 20 40 60 112 f1 x  f 2 x  f3 x  f 4 x  9 15 22 10 18 20 6 12 25 12 17 20 Решение В данной задаче в качестве шагов будем рассматривать выделение средств каждому предприятию: шаг 1 – выделение средств предприятию П1, шаг 2 – предприятию П2 и т.д. , всего 4 шага (по числу предприятий). Обозначим: хk - средства, выделенные k -му предприятию (k = 1,2,3,4); f k  x  задаются f k xk  - прибыль от вложения указанных средств (функции таблицей). 4 Z   f k  xk  Суммарная прибыль равна k 1 4 Переменные х удовлетворяют условию x k 1 k  60; xk  0; k  1,2,3,4. Требуется найти переменные x1, x2 , x3 , x4 , удовлетворяющие системе ограничений и обращающие в максимум целевую функцию. Итак: s0  60 - начальные средства (начальное состояние системы);  s  0 - конечное состояние процесса распределения (системы), все средства должны быть вложены в предприятия. х1 х3 х2 х4 s0  60  s1  60  х1  s2  s1  х2  s3  s2  х3  s4  s3  х4  s0 Рис.4.3. Схема распределения инвестиций Уравнения состояний в данной задаче имеют вид: sk  sk 1  xk , k 1,2,3,4 sk - параметр состояния – количество средств, оставшихся к после k -того шага, которые останется распределить между оставшимися 4 - k предприятиями. Ведем в рассмотрение функцию Z k sk 1  - условную оптимальную прибыль, * полученную от k -того, (k – 1)-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства sk 1 0  sk 1  60 113 Допустимое управление на k-м шаге удовлетворяют условию 0  хk  sk 1 (либо ничего не выделяем, либо не более того, что осталось к k -тому шагу. Уравнения Беллмана, приведенные ранее, для произвольного k –того шага:   Z k sk 1   max f k sk 1 , Х k   Z k 1 sk  ; * xk  * k  n  1, n  2, ...2,1 Для данной конкретной задачи уравнения для условных максимумов (уравнения Беллмана) имеют вид: k  4, s4  0;  Z 4 s3   max f 4 x4 , * 0 x4  s3  s   max f x   Z 60  max f x   Z  s , s . Z 3 s2   max f 3 x3   Z 4 s3  , * * 0 x3  s2 Z2 * * Z1 1 * 0 x2  s1 2 2 3 0 x1  60 1 1 2 2 * 1 Последовательно решаем записанные уравнения для каждого шага. Шаг 4. K = 4. Выделение средств предприятию П4 Предприятие П4 – последнее, предполагается, что остальным предприятиям средства уже выделены. Поэтому все оставшиеся средства следует вложить в П4. Определяем все возможные состояния s3 к началу 4 шага, т.е. все возможные значения остатка денежных средств после выделения их предприятиям П1, П2 и П3. Этот остаток составляет s3  0, 20, 40, 60 . s3 = 0 ден.ед., если все средства выделяются предприятиям П1, П2 и П3; s3 = 20 млн, если предприятиям П1, П2 и П3 выделено 40 млн; s3 = 40 млн, если предприятиям П1, П2 и П3 выделено 20 млн; s3 = 60 млн, если остальным предприятиям средства не выделять. * Для возможных значений s3 получим Z4 s3   f 4 s3  u x *4 s3   s3 . Занесем эти данные в табл. 4.3 114 Т а б л и ц а 10.3 * s3 x *4 Z4 20 20 12 40 40 17 60 60 20 Шаг 3. K = 3. Выделение средств предприятиям П3 и П4 Делаем все предположения относительно остатка средств s2 к третьему шагу т.е. после выбора х1 и х 2 . s2 может принимать значения, равные 0, 20, 40, 60 . Например, средства отданы П1 и П2. В зависимости от этого выбираем Все расчеты в табл.10.4.  s2  0 , если все 0  x3  s 2 , …  Z3 s2   max f 3 x3   Z 4 s3  * Расчетная формула 0 x3  s2 * Т а б л и ц а 10.4 s2 х3 f3 x  s3 Z 4 s3  20 20 12 0+12=12 20 6 6+0=6 6 12 40 17 0+17=17 20 12 6+12=18 12+0=12 6 12 25 60 20 0+20=20 40 17 6+17=23 20 12 12+12=24 25+0=25 40 20 40 60 20 40 60 * Z 3 s2  Z 3 s2  * х *3 12 18 20 25 60 Здесь: s2 - возможные денежные средства, распределенные между предприятиями П1 и П2; 115 х3 - возможные варианты выделения средств предприятию П3; f3 x  - прибыль предприятия П3 от выделенных средств (из табл.4.2); s3 - остаток денежных средств после распределения их между предприятиями П1 и П2, т.е. средства, выделяемые для П3; Z 4 s3  - прибыль предприятия П4 от выделенных ему средств в размере s3 ; * Z 3 s2  - суммарная прибыль предприятий П3 и П4; Z 3 s2  - условно оптимальный критерий эффективности для предприятий П3 и П4, * т.е. прибыль, получаемая этими предприятиями в результате решения х3 , х*3 - условно оптимальное решение 3 шага. Шаг 2. К = 2. Выделение средств предприятиям П2, П3 и П4. Все расчеты в табл.4.5.   f 2 x2   Z 3 s2  Расчетная формула Z 2 s1   0max  x s * 2 * 1 Т а б л и ц а 10.5. f 2 x  х2 s1 s2 Z 3 s2  Z 3 s2  Z 3 s2  х* 2 * 20 20 10 20 12 0+12=12 10+0=10 20 40 20 40 60 10 18 10 18 20 40 20 60 40 20 18 12 25 18 12 0+18=18 10+12=22 18+0=18 0+25=25 10+18=28 18+12=30 20+0=20 40 60 * 12 22 20 30 40 Обозначения в табл.: s1 - возможные суммы денежных средств, распределяемые между П2, П3 и П4, т.е. оставшиеся после выделения средств предприятию П1; х2 - возможные варианты выделения средств предприятию П2; 116 f 2 x  - прибыль П2 от выделения средств в размере х2 ; s2 - остаток средств после их выделения предприятиям П1 и П2, т.е. средства, выделяемые П3 и П4 и т.д. Шаг 1. К = 1. Финансирование предприятий П1, П2, П3 и П4.   Z1 60  max f1 x1   Z 2 s1  * Расчетная формула * 0 x1 60 Т а б л и ц а 4.6 60 f1  x  х1 s0 s1 Z 2 s1  Z 2 s1  * 60 30 0+30=30 20 9 40 22 9+22=31 40 16 20 12 16+12=28 60 22 22+0=22 Z 2 s1  х*1 31 20 * Цикл безусловной оптимизации Для первого предприятия П1 получено безусловно оптимальное решение х*1 =20 млн. ден.ед. Для предприятий П2, П3 и П4 остается 40 млн. ден.ед. Таким образом, состояние к началу второго шага s1 =40. Из табл.4.5 для этого состояния * оптимальное решение х 2 =20 (предприятию П2 выделяется 20 млн. ден.ед.) , а для предприятий П3 и П4 остается 20 млн. ден.ед. Состояние в начале третьего шага * ( s2 =20). Из табл.4.4 определяется оптимальное решение х 3 =0 (предприятию П3 средств выделять не надо). Для предприятия остается 20 млн. ден.ед., поэтому x *4 =20. Таким образом, оптимальное решение, следующее: x *1  20, x *2  20, x *3  0, x *4  20 Предприятию П1 следует выделить 20 млн. ден.ед. П2- также 20 млн. ден.ед., П3 – средства не выделять, П4 – выделить 20 млн. ден.ед. Общая прибыль составит 31 млн. ден.ед. 117 ЗАКЛЮЧЕНИЕ В предлагаемом учебном пособии изложен теоретический материал для изучения основ курса «Исследование операций и методы оптимизации», представлена методика практического решения оптимизационных задач. Рассмотренные задачи и их экономико-математические модели имеют прикладное значение для выработки эффективных решений в планировании и управлении производством. Методы решения задач позволяют найти из множества альтернативных вариантов наилучший вариант производства, распределения или потребления. Ограниченные ресурсы при этом будут использованы наиболее эффективным образом для достижения поставленной цели. Данное учебное пособие должно способствовать приобретению существенных навыков использования методов исследования объектов профессиональной деятельности и умения применять их в своей предметной области. Библиографический список 1. Исследование операций в экономике : учебник для вузов / под редакцией Н. Ш. Кремера. — 4-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2020. — 414 с. — (Высшее образование). — ISBN 978-5-534-12800-0. — Текст : электронный // ЭБС Юрайт [сайт]. 2. Исследование операций в экономике [Электронный ресурс]: учебное пособие/ Г.Я. Горбовцов [и др.].— Электрон. текстовые данные.— М.: Евразийский открытый институт, Московский государственный университет экономики, статистики и информатики, 2006.— 118 c.— Режим доступа: http://www.iprbookshop.ru/10690.— ЭБС «IPRbooks». 3. Барабаш, С. Б. Методы оптимальных решений : учебное пособие / С. Б. Барабаш. — Москва : Ай Пи Ар Медиа, 2021. — 354 c. — ISBN 978-5-44971175-5. — Текст : электронный // Электронно-библиотечная система IPR BOOKS : [сайт]. — URL: https://www.iprbookshop.ru/108236.html (дата обращения: 04.06.2021). — Режим доступа: для авторизир. пользователей 4. Лунгу, К.Н. Линейное программирование. Руководство к решению задач [Электронный ресурс]/ Лунгу К.Н.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 132 c.— Режим доступа: http://www.iprbookshop.ru/12905.— ЭБС «IPRbooks». 118 5. Потихонова, В. В. Исследование операций. Курс лекций : учебное пособие / В. В. Потихонова, Л. И. Король. — Санкт-Петербург : Санкт-Петербургский государственный университет промышленных технологий и дизайна, 2017. 119 120