1 Антюхов В.И.

2 Содержание учебного курса «Теория игр и исследование операций» Раздел 1. Исследование операций Тема 1. Применение методов математического программирования (МП) для исследования операций (ИО) Тема 2. Модели ИО Раздел 2. Теория игр Тема 3. Модели матричных, кооперативных и дифференциальных игр Тема 4. Критерии выбора оптимальной стратегии в условиях риска и в условиях неопределённости Раздел 3. Методы теории массового обслуживания (ТМО) Тема 5. Классификация систем массового обслуживания (СМО), их характеристики и показатели Тема 6. Одноканальные и многоканальные СМО с отказами и ожиданиями Всего часов: 72 (50час. - аудиторных, 22час. – СР) Отчётность: экзамен в 8 семестре

3 Список литературы Основная 1.Системный анализ и принятие решений.– СПб.: СПбУГПС, (в печати) 2.Волков И.К. Исследование операций: Учебник для вузов/ И.К.Волков, Е.А.Загоруйко. –М.: Издательство МГТУ им. Н.Э.Баумана, Е.С.Вентцель. Исследование операций. Задачи, принципы, методология. Учеб. пособие для студ. вузов. –М.: Высшая школа, с. Дополнительная 1.Таха Х. Введение в исследование операций: в 2-х книгах/ Пер. с англ. –М.:Мир, Е.С.Вентцель. Исследование операций. –М.: Сов. Радио, с.

4 Тема 1. Применение методов математического программирования (МП) для исследования операций (ИО) Лекция 1. Задачи линейного программирования (ЛП) Учебные вопросы: 1. Введение в исследование операций 2. Общая постановка задачи линейного программирования (ОЗЛП) 3. Графический метод решения задачи линейного программирования 4. Симплекс-метод решения задачи ЛП

5 Лекция 1. Задачи линейного программирования (ЛП) Учебный вопрос 1. Введение в исследование операций

6 Учебный вопрос 1. Введение в исследование операций Исследование операций возникло в годы второй мировой войны из потребностей наилучшей организации боевых действий В дальнейшем исследование операций нашло широкое применение в: - науке (для перспективного и текущего планирования НИР и ОКР); - экономике (для проектирования различных объектов); - социологии; - политике и др.

7 Определение исследования операций Это научное направление, ориентированное на решение практических задач, которые можно корректно описать с помощью математической модели

8 Области применения исследования операций в ГПС МЧС РФ Обоснование программ оснащения Разработка новых образцов специальной техники Разработка планов подготовки спасателей Оперативное управление силами ГПС и др.

9 Предметная область ТИ и ИО Перед людьми постоянно возникают проблемы, связанные с выбором решений о рациональных способах достижения целей при заданных ограничениях на количество используемых ресурсов и времени В простых ситуациях выбор осуществляется человеком на основе личного опыта, знаний и интуиции В более сложных ситуациях выбор рационального решения осуществляется группой лиц

10 Предметная область ТИ и ИО (продолжение) При управлении большими организационно- техническими системами, сложность ситуаций является высокой, а время, отводимое на принятие решения, малым Увеличение числа людей в составе органа управления не приводит к повышению качества и оперативности выбора решений Один из наиболее эффективных путей разрешения данного противоречия связан с: - оснащением органов управления средствами вычислительной техники; - разработкой специальных математических методов и программного обеспечения, позволяющих автоматизировать процесс количественной оценки различных вариантов решений и выбора наилучшего из них

11 Предметная область ТИ и ИО (продолжение) Математические методы количественной оценки возможных вариантов решений и выбора лучшего решения из возможных получили название математических методов исследования операций Математические методы представляют собой важнейшую часть исследования операций

12 Предметная область ТИ и ИО (продолжение) Объектом исследования операций в области ГПС являются: - программы развития специальной техники; - все виды повседневной и боевой деятельности; - все виды обеспечения боевых действий; - подготовка кадров и т.д.

13 Предметная область ТИ и ИО (продолжение) В конфликтных ситуациях, когда две или более оперирующие стороны преследуют несовпадающие цели, значение целевой функции каждой стороны зависит не только решения, выбранного данной стороной, но и от решений, выбранных другими сторонами Раздел исследования операций, ориентированный на разработку методов выбора оптимальных решений учитывающих решения, принимаемые каждой из сторон, участвующих в операции, называется теорией игр

14 Предметная область ТИ и ИО (продолжение) Области приложения теории игр: - экономика; - политика; - военные действия и т. д.

15 Учебный вопрос 1. Введение в исследование операций Как и всякое научное направление, исследование операций имеет свой понятийный аппарат

16 Понятие «операция» Одним из основных понятий теории исследования операций является понятие «операция» Операция - это этап функционирования системы, связанный с достижением конкретной цели Примеры операций: - тушение пожара; - следование к месту проведения аварийно-спасательных работ; - обучение в ВУЗе МЧС и др.

17 Понятие «цель» Цель - это конечный результат, который требуется достичь в результате операции Цель, как правило, является качественным понятием Примеры целей операций: - Цель операции «тушение пожара» – сохранение жизней и материальных средств - Цель следования к месту проведения аварийно- спасательных работ - тренировка личного состава - Цель обучения в ВУЗе МЧС – подготовка специалистов высшей квалификации для МЧС Наряду с целями, фигурирующими в явном виде, на практике, могут иметь место цели, которые непосредственно в постановке задачи исследования операций не отражены

18 Понятие «цель» Сложная операция, как правило, состоит из ряда частных эпизодов, для решения которых привлекаются отдельные группы из состава сил и средств, участвующих в операции Для каждого частного эпизода формулируется своя цель В этом случае говорят о дереве целей Частные цели в общем случае не должны противоречить общей цели операции

19 Понятие «оперирующая сторона» Оперирующая сторона – это совокупность лиц, которые стремятся в данной операции к достижению одной цели Пример оперирующей стороны: личный состав караула пожарной части. В операции могут участвовать одна или несколько оперирующих сторон, преследующих различные несовпадающие цели Несовпадение целей создает конфликтную ситуацию. Подобные операции называются «многосторонними» или «конфликтными» При тушении пожара одна оперирующая сторона - расчет караула, и другая - стихия, имеют различные, обычно противоположные цели

20 Понятие «группа исследования операций» В составе оперирующей стороны целесообразно выделить «группу исследования операций» и «лицо, принимающее решение» (ЛПР) Группа исследования операций проводит количественный анализ различных вариантов решений и вырабатывает рекомендации по выбору лучшего из них. Рекомендации, сформированные этой группой, являются основой для решения, принимаемого ЛПР Выражение «основа для решения» отражает то обстоятельство, что для принятия решения используются не только количественные оценки ЛПР обязан учитывать не только их, но и многие важные факторы, которые невозможно выразить числом: политико-моральное состояние людей, их привычки, обычаи и т.д.

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

22 Понятие «стратегия» Оперирующая сторона управляет операцией, выбирая те или иные способы использования ресурсов – «стратегии» (способы действий, альтернативы, решения, управления) Возможности оперирующей стороны по управлению операцией всегда ограничены, поскольку всегда ограничены ее ресурсы. Этот факт проявляется в наличии ограничений на выбор способа действий оперирующей стороны Стратегии, удовлетворяющие этим ограничениям, называются допустимыми

23 Реализация той или иной стратегии оперирующей стороны обычно приводит к различным исходам операции Чтобы сравнивать между собой качество различных стратегий, нужно иметь возможность оценивать соответствующие исходы операций Исход операции оценивается с помощью критериев эффективности

24 Понятие «критерий эффективности» Критерий эффективности – это математическое выражение, позволяющее количественно оценить степень достижения цели операции Переход от качественного понятия, каким является цель, к количественному понятию – критерий, содержит определенное противоречие Критерий, как правило, отражает только некоторые, наиболее существенные стороны цели операции Формулировка критерия, как можно более полно соответствующего цели операции, является одной из наиболее сложных творческих задач операционного исследования

25 Понятие «оптимальная стратегия» Стратегия, наилучшая в смысле выбранного критерия эффективности, то есть доставляющая ему экстремальное (максимальное или минимальное), значение, называется оптимальной стратегией Оптимальной стратегии вообще не существует Всякая оптимальная стратегия является наилучшей лишь в смысле, определенном выбранным критерием эффективности

26 Понятие «показатель эффективности» В теории исследования операций наряду с понятием критерий эффективности широко используется понятие показатель эффективности Показатель эффективности – это количественная оценку какого-то отдельного свойства изучаемого объекта или явления Свойства технических, экономических, военных объектов и явлений обычно многогранны. Для их количественной оценки используется совокупность многих показателей

27 В зависимости от цели операции тот или иной показатель (или совокупность тех или иных показателей) могут быть выбраны в качестве критерия эффективности, а остальные - вынесены в ограничения Главное условие, необходимое для применения математических методов исследования операций, заключается в принципиальной возможности разработки корректной математической модели изучаемого объекта или явления

28 Понятие «математическая модель» Математическая модель - упрощенное представление характеристик реального процесса в виде совокупности уравнений (алгоритмов). Степень упрощения должна быть такая, чтобы вычисления на модели могли быть проведены с требуемой точностью за время не более заданного В связи с этим возникает необходимость учета в модели не всех, а только существенно значимых (релевантных, доминирующих) свойств моделируемого объекта, явления Среди математических моделей по методам, лежащим в их основе, можно выделить: - аналитические модели; - численные модели; - имитационные модели.

29 Аналитической моделью называется формализованное описание объекта или явления, позволяющее получить соотношения между входными и выходными величинами в явном виде Численная модель характеризуется такой зависимостью между входными и выходными величинами, которая допускает только численные решения для конкретных начальных условий и количественных параметров модели

30 В имитационных моделях зависимости между входными и выходными величинами носят вероятностный характер Для получения достаточно точных и надежных результатов имитационную модель приходится решать с одними и теми же исходными данными неоднократно

31 В слабо формализуемых предметных областях широкое применение находят модели, построенные на базе методов искусственного интеллекта В первую очередь к таким моделям можно отнести: - экспертные системы; - нейрокомпьютерные системы. В соответствии со сложившейся традицией, методы и модели имитационного моделирования, методы и модели систем искусственного интеллекта являются самостоятельными научными дисциплинами, не входящими в состав теории исследования операций

32 Учебный вопрос 1. Введение в исследование операций В исследовании операций решаются как задачи выбора, так и оптимизационные задачи Разнообразные проблемы оптимизации сводятся к математической задаче нахождения наибольшего или наименьшего значения функции многих аргументов В теории оптимизации эту функцию принято называть целевой функцией, так как она всегда выражает цель исследования и отыскание её глобального экстремума означает достижение цели

33 Учебный вопрос 1. Введение в исследование операций Часто аргументы целевой функции подчинены некоторым ограничениям в виде системы равенств или неравенств Задачей условной оптимизации и является отыскание экстремального значения целевой функции при наличии ограничений на аргументы Если ограничений нет, то имеется задача безусловной оптимизации

34 Учебный вопрос 1. Введение в исследование операций Теория и методы решения задач условной и безусловной оптимизации целевой функции являются предметом раздела современной математики – математического программирования Термин «программирование» отражает тот факт, что цель задач оптимизации состоит обычно в нахождении оптимальной программы действий или оптимального плана достижения конечного результата

35 Учебный вопрос 1. Введение в исследование операций В тех случаях, когда целевая функция и все ограничения представлены линейными выражениями, имеем задачу линейного программирования Если хотя бы одно из этих выражений нелинейно, то получаем задачу нелинейного программирования

36 Лекция 1. Задачи линейного программирования (ЛП) Учебный вопрос 2. Общая постановка задачи линейного программирования (ОЗЛП)

37 Учебный вопрос 2. Общая постановка задачи линейного программирования Большинство задач оптимизации в исследовании операций и моделировании относится к нелинейным Однако решение нелинейных задач - сложная теоретическая и вычислительная проблема Общих методов решения нелинейных задач (нахождения локального и глобального экстремума) не существует Поэтому практически всегда для решения нелинейных задач используются приближенные методы решения

38 Учебный вопрос 2. Общая постановка задачи линейного программирования Сущность приближенных методов решения нелинейных задач состоит в том, что исходная постановка задачи сводится к одной линейной или их совокупности, т.е. к задаче линейного программирования Задачей линейного программирования называется оптимизационная задача, у которой и целевая функция и ограничения являются линейными

39 Учебный вопрос 2. Общая постановка задачи линейного программирования Первые идеи линейного программирования принадлежат французскому математику и физику Жан Батисту Жосефу Фурье ( ) Фурье являлся иностранным почётным членом Петербургской АН (1829) Его научными интересами были алгебра, дифференциальные уравнения, математическая физика «Аналитическая теория тепла» (1822) Ж.Б.Фурье явилась отправным пунктом в создании теории тригонометрических рядов (рядов Фурье)

40 Учебный вопрос 2. Общая постановка задачи линейного программирования Однако осознание важности и утверждение линейного программирования, как самостоятельной дисциплины, произошло лишь в 1940 годах в работах советского математика и экономиста Л.В.Канторовича ), Дж. фон Неймана ( ) и др.

41 Учебный вопрос 2. Общая постановка задачи линейного программирования По мере разработки новых методов решения задач и их представления в виде программ для ЭВМ, по мере совершенствования самих вычислительных машин, линейное программирование становится все более мощным инструментом исследования и оптимизации функционирования систем самой различной природы

42 Учебный вопрос 2. Общая постановка задачи линейного программирования Построение математической модели любой задачи линейного программирования начинается с ответов на следующие вопросы: 1) что взять в качестве управляющих переменных? 2) какие ограничения должны быть наложены на эти переменные? 3) какова цель, для достижения которой решается задача?

43 Постановка ОЗЛП Задачам линейного программирования соответствуют модели, описываемые с помощью линейных соотношений Чтобы пользоваться общими методами и алгоритмами решения, все довольно разнообразные постановки задач линейного программирования сводят к одной так называемой канонической постановке

44 Постановка ОЗЛП Задачу с канонической постановкой принято называть основной или общей задачей линейного программирования (ОЗЛП)

45 Постановка ОЗЛП Найти такой набор значений управляемых параметров X 0 = {x 1,x 2,…,x n }, который обращает в минимум значение целевой функции: U = C 1 x 1 +C 2 x 2 +…+C n x n при ограничениях: a 11 x 1 +a 12 x 2 +…+a 1n x n =b 1 a 21 x 1 +a 22 x 2 +…+a 2n x n =b 2 ………………………………………………… a m1 x 1 +a m2 x 2 +…+a mn x n =b n, x 1,x 2,…,x n0

46 Другие формы записи ОЗЛП Минимизировать U = C j x j при ограничениях: a ij x j = b i, i =1,m; x j 0; j = 1,n Минимизировать U= C x при ограничениях: Ax = b, x 0, где: C=(C 1,C 2,…,C n ) – вектор-строка; x = (x 1,x 2,…,x n ) – вектор-столбец; A - матрица; B = (b 1,b 2,…,b n ) – вектор-столбец; 0 – вектор-столбец нулей

47 Другие формы записи ОЗЛП Минимизировать U= C x при ограничениях: P 1 x 1 +P 2 x 2 +…+P n x n = P 0 x 0, где: P j – столбец j матрицы A, j=1,n

48 Другие формы записи ОЗЛП Первоначальная запись условий задач линейного программирования может отличаться от рассмотренной тем, что: - требуется не минимизировать, а максимизировать целевую функцию; - все или некоторые ограничения имеют форму неравенств; - на часть переменных не наложено требование неотрицательности

49 Задача максимизации функции Например, задача максимизации функции: U = C 1 x 1 +C 2 x 2 +C 3 x 3 +C 4 x 4 при ограничениях: a 11 x 1 +a 12 x 2 +a 13 x 3 = b 1 a 21 x 1 +a 22 x 2 +a 23 x 3 +a 24 x 4 b 2 a 31 x 1 +a 32 x 2 +a 33 x 3 +a 34 x 4 b 3 x 3 0; x 4 0 после сведения к каноническому виду будет записываться так:

50 Задача максимизации функции ( после сведения к каноническому виду ) U=-C 1 (x 7 -x 8 )+C 2 (x 9 -x 10 )+C 3 x 3 +C 4 x 4 +0x 5 -0x 6, при ограничениях: a 11 (x 7 -x 8 )+a 12 (x 9 -x 10 )+a 13 x 3 = b 1 a 21 (x 7 -x 8 )+a 22 (x 9 -x 10 )+a 23 x 3 +a 24 x 4 +x 5 = b 2 a 31 (x 7 -x 8 )+a 32 (x 9 -x 10 )+a 33 x 3 +a 34 x 4 -x 6 = b 3 x 3,x 4,x 5,x 6,x 7,x 8,x 9,x 100

51 Другие формы записи ОЗЛП К общей задаче линейного программирования сводятся многие распределительные задачи, связанные с управлением в государственной противопожарной службе: - определение состава сил и средств; - использование автотранспортных средств; - размещение баз снабжения и др.

52 Пример общей задачи линейного программирования Для технического обслуживания и ремонта трех типов средств пожаротушения имеются четыре мастерских Мастерская типа j (j = 1, 2, 3, 4) может принять одновременно a ij средств пожаротушения типа i (i =1, 2, 3) и произвести их обслуживание и ремонт при стоимости c j Каждый тип средств пожаротушения представлен b i единицами Требуется найти, сколько потребуется мастерских каждого типа, чтобы обслужить все средства пожаротушения за один прием и с минимальными затратами

53 Пример общей задачи линейного программирования Задаче соответствует: - целевая функция: U=C 1 x 1 +C 2 x 2 +C 3 x 3 +C 4 x 4 - и ограничения: a 11 x 1 +a 12 x 2 +a 13 x 3 +a 14 x 4 b 1 a 21 x 1 +a 22 x 2 +a 23 x 3 +a 24 x 4 b 2 a 31 x 1 +a 32 x 2 +a 33 x 3 +a 34 x 4 b 3, x 1, x 2, x 3, x 4 0

54 Пример общей задачи линейного программирования Набор значений управляемых параметров X, удовлетворяющий ограничениям, называется допустимым решением (планом) задачи линейного программирования Допустимое решение, при котором целевая функция обращается в минимум, носит название оптимального решения

55 Условия решения задачи линейного программирования Если число неизвестных параметров n меньше числа независимых ограничений r (n < r), то задача линейного программирования не имеет решения При n = r и определителе системы ограничений, отличном от нуля, имеется единственное решение и задачи оптимизации нет Если n > r, то n - r неизвестным можно придать произвольные значения, а остальные r неизвестных выразить через них и, таким образом найти множество решений. Именно в этом случае возникает задача оптимизации

56 Условия решения задачи линейного программирования Неизвестные, которым могут быть приданы произвольные значения, называют свободными переменными Неизвестные, которые выражаются через свободные переменные (их число r), называются базисными переменными Допустимое решение, в котором все свободные переменные (неизвестные) равны нулю, принято называть базисным

57 Условия решения задачи линейного программирования Если в базисном решении содержится ровно r положительных компонентов, то его называют невырожденным, если меньше - вырожденным В теории линейного программирования показано, что поиск оптимального решения нужно проводить только среди базисных решений

58 Условия решения задачи линейного программирования Таким образом, чтобы решить задачу линейного программирования, необходимо определить: - имеет ли задача допустимые решения; - принимает ли целевая функция экстремум; - каково экстремальное значение целевой функции

59 Условия решения задачи линейного программирования Для решения задач линейного программирования разработан целый ряд методов Наиболее универсальным методом является симплекс-метод

60 Лекция 1. Задачи линейного программирования (ЛП) Учебный вопрос 3. Графический метод решения задачи линейного программирования

61 Учебный вопрос 3. Графический метод решения задачи ЛП В основе решения задачи линейного программирования лежат две теоремы: 1.Теорема о структуре множества допустимых решений задачи линейного программирования 2.Теорема об экстремуме линейной формы задачи линейного программирования

62 Теорема о структуре множества допустимых решений задачи линейного программирования Множество D, определяемое системой ограничений в задаче линейного программирования, есть выпуклое множество Множество D называется выпуклым, если для любых двух точек x i,x i+1 D справедливо соотношение: x i +(1 )x i+1 D, где 0 1 Другими словами, если точки x i,x i+1 D, то и любая точка x, находящаяся на прямой между этими точками также принадлежит D

63 Теорема о структуре множества допустимых решений задачи линейного программирования Множество D, содержащее все свои граничные точки называется замкнутым Точка x D называется граничной, если в любой, сколь угодно малой ее окрестности, существуют точки не принадлежащие D Таким образом, множество решений задачи линейного программирования представляет собой выпуклое замкнутое множество Если это множество к тому же и ограничено, то оно называется выпуклым многогранником

64 Теорема о структуре множества допустимых решений задачи линейного программирования Крайняя точка n мерного многогранника это такая точка, в которой сходятся n его граней Многогранник имеет конечное множество вершин и любая точка x, принадлежащая многограннику, может быть представлена как линейная комбинация множества вершин Это означает, что множество опорных планов полностью определяет структуру множества допустимых решений задачи линейного программирования

65 Теорема об экстремуме линейной формы задачи линейного программирования Линейная форма U = c j x j, j=[1,n], определенная на выпуклом многограннике a ij x j b i, i = [1,m], x i 0 достигает экстремума в вершине этого многогранника На интуитивном уровне доказательство теоремы сводится к следующему:

66 Теорема об экстремуме линейной формы задачи линейного программирования Целевая функция U представляет собой n-1 гиперплоскость (линейная форма) в n пространстве и достигающую экстремума только на границе n мерного многогранника U Если эта форма не является параллельной ни одной из граней или ребер многогранника, то экстремум может находится только в одной из его вершин

67 Теорема об экстремуме линейной формы задачи линейного программирования Таким образом, решение задачи линейного программирования находится на границе допустимого множества и для нахождения решения задачи линейного программирования необходимо перебрать граничные точки допустимого множества Значения переменных на границе, соответствующие максимальному значению целевой функции, и будут является решением Очевидно, что задача максимизации U при каких-либо ограничениях эквивалентна задаче минимизации функции – U При этом: max U = min(- U)

68 Графический метод решения задачи линейного программирования В некоторых простейших случаях задачи линейного программирования допускают графический метод решения, который позволяет также глубже понять структуру задачи и методы ее решения

69 Графический метод решения задачи линейного программирования Графический метод решения задачи линейного программирования возможен если удовлетворяются следующие условия. 1. Число неизвестных переменных в задаче не больше трех (n < 3). В этом случае целевая функция и область допустимых решений могут быть изображены на плоскости - для задачи с двумя неизвестными, либо в пространстве - для задачи с тремя неизвестными (ограничения могут быть как равенствами так и неравенствами)

70 Графический метод решения задачи линейного программирования 2. Когда число переменных на два или три больше чем число ограничений В первом случае имеет место двумерная, а во втором трехмерная интерпретация задачи линейного программирования (ограничения задаются только в виде равенств)

71 Графический метод решения задачи линейного программирования Вторая графическая интерпретация позволяет преобразовать n-мерную область допустимых решений, где n - число неизвестных, в двумерную выпуклую область с n гранями и найти оптимум целевой функции в этой области В графических примерах удобно пользоваться понятием «Градиент» и «Линия уровня»

72 Графический метод решения задачи линейного программирования Линией уровня линейного выражения называют место точек, удовлетворяющих заданному значению правой части В пространстве R 2 линия уровня - это прямая, в трехмерном R 3 - плоскость, в n- мерном R n - (n 1)-мерная гиперплоскость Все линии уровня задачи линейного программирования параллельны

73 Графический метод решения задачи линейного программирования Градиент линейного выражения - это вектор из коэффициентов при неизвестных в левой части Например, градиент выражения Z=2X 1 +3X 2 равен (2,3) Все градиенты перпендикулярны к своим линиям уровня. Будучи, изображенными в виде векторов, они указывают направление наиболее быстрого увеличения правой части

74 Пример для графического решения задачи линейного программирования Предприятие готовится к выпуску двух различных модификаций средств пожаротушения, предназначенных для тушения пожаров в однотипных зданиях При производстве каждого средства пожаротушения используется набор из пяти типов комплектующих Расход комплектующих на производство средств пожаротушения каждой модификации показан в таблице на следующем слайде

75 Пример для графического решения задачи линейного программирования Модифи- кация Тип комплектующих

76 Пример для графического решения задачи линейного программирования Количество комплектующих каждого типа, выделенных на производство средств пожаротушения обоих модификаций, равно 250, 300, 250, 110 и 110 единиц соответственно Известно, что средство пожаротушения первой модификации способно эффективно действовать на пожаре с вероятностью равной 0.4, а средство пожаротушения первой модификации - с вероятностью равной 0.6

77 Пример для графического решения задачи линейного программирования Необходимо определить объемы производства средств пожаротушения обоих модификаций, обеспечивающих эффективное тушение пожара В качестве управляемых переменных X j возьмем число средств пожаротушения j й модификации, которое должно выпустить предприятие

78 Пример для графического решения задачи линейного программирования Для производства X 1 систем первой модификации требуется 2X 1 комплектующих первого типа Для производства X 2 систем второй модификации требуется X 2 комплектующих того же типа (см. введенную выше таблицу с исходными данными) Отсюда следует ограничивающее неравенство: 2X 1 +X Рассуждая аналогично для комплектующих второго типа получим ограничивающее неравенство: 2X 1 + 2X Для комплектующих третьего типа ограничивающее неравенство имеет вид: X 1 +2X Количество комплектующих четвертого и пятого типов ограничено величиной 110 единиц

79 Пример для графического решения задачи линейного программирования Из постановки задачи следует, что цель производства средств пожаротушения заключается в создании потенциальных возможностей для более эффективного тушения пожаров Поскольку средство пожаротушения первой модификации способно эффективно действовать на пожаре с вероятностью равной 0.4, а второй - с вероятностью 0.6, целевая функция задачи задается выражением: maxU = 0.4X X 2

80 Пример для графического решения задачи линейного программирования Исходя из условий задачи можно записать: X 1 110, X На переменные накладываются также ограничения X 1, X 2 0

81 Пример для графического решения задачи линейного программирования С учетом вышеизложенного, исходная задача в терминах линейного программирования имеет вид: Целевая функция U =0.4X X 2, Ограничения.

82 Пример для графического решения задачи линейного программирования Требуется найти X 1 *,X 2 * при которых целевая функция достигает максимума

83 Пример для графического решения задачи линейного программирования Первый шаг при использовании графического метода связан с построением области допустимых решений Область допустимых решений находится по направлению, совпадающему с градиентом линии уровня соответствующего ограничения, если оно имеет знак больше или равно ( ), по противоположному направлению, если ограничение имеет знак меньше или равно ( )

84 Пример для графического решения задачи линейного программирования Условия неотрицательности переменных ограничивают данную область положительным квадрантом системы прямоугольных координат X 1, X 2 Остальные границы пространства решений отображаются линиями уровня, построенными по уравнениям, которые получаются при замене знака меньше или «равно» на знак «равно» в ограничениях исходной задачи Выполнив указанные преобразования и отобразив их результаты графически, получим область допустимых решений

85 Пример для графического решения задачи линейного программирования Для рассматриваемого примера эта область отображена на рис.1. (область АВСДЕFG) Цифры в кружках на рисунке указывают номер ограничения задачи, отображаемого соответствующей прямой Как видно из рис.1a. она представляет собой выпуклый многоугольник Ограничения можно строить просто используя метод построения прямой по отрезкам

86 Пример для графического решения задачи линейного программирования Приравнивая x 1 =0 в первом ограничении находим x 2 =250 Затем принимаем x 2 =0, и находим x 1 =125 Отложив по осям точки x 1,x 2 соответственно 125 и 250, соединим их В результате получаем отрезок, соответствующий первому ограничению

87 Пример для графического решения задачи линейного программирования Так как ограничение имеет вид « », то штриховка направлена левее отрезка Аналогично можно построить и другие ограничения (на рис.1а линии ограничений пронумерованы в соответствии с их порядком в системе ограничений)

88 Пример для графического решения задачи линейного программирования Целевая функция задачи линейного программирования для случая двух переменных отображается на графике семейством параллельных прямых (ее построение показано на рис.1b) Для того, чтобы определить точку оптимума задачи необходимо знать угол наклона этого семейства к осям координат и направление возрастания (убывания) целевой функции Для выяснения первого вопроса (определение точки оптимума) зададим целевой функции произвольные значения, например Z 1 =24 и построим прямую 0.4X X 2 =24 (построить целевую функцию можно также используя метод построения прямой по отрезкам)

89 Пример для графического решения задачи линейного программирования Для ответа на второй вопрос (направление возрастания (убывания) целевой функции) найдем градиент Он равен (0.4,0.6) Отобразим его на линии уровня целевой функции стрелкой. Теперь становится очевидным, что целевая функция растет при ее приближении к точке D области допустимых решений и именно в этой точке находится оптимальное решение задачи Точка D есть крайняя точка, в которой область допустимых значений пересекается с целевой функцией при возрастании последней Осталось определить координаты точки D и величину целевой функции в этой точке

90 Пример для графического решения задачи линейного программирования На рис.1б видно, что из пяти неравенств задачи два, а именно второе и третье превращаются в точке D в равенства Воспользуемся этим фактом для решения задачи, рассчитав величину переменных X 1 и X 2 из системы линейных уравнений:

91 Пример для графического решения задачи линейного программирования В результате решения этой системы получили X 1 =50, X 2 =100 Теперь можно рассчитать и величину целевой функции в точке D Она оказывается равной 80 Таким образом, используя выделенное количество комплектующих каждого из пяти типов, можно построить 50 средств пожаротушения первой модификации и 100 единиц второй Это количество средств пожаротушения окажется эффективным для тушения 80 пожаров

92 Пример для графического решения задачи линейного программирования Любое другое соотношение между производством средств пожаротушения первой и второй модификации в рамках заданных ограничений окажется хуже в том смысле, что количество потенциально возникающих пожаров будет меньше

93 Пример для графического решения задачи линейного программирования Таким образом алгоритм решения задачи графическим способом в случае когда число переменных не больше трех следующий: 1. На основании ограничений строится область допустимых решений D. Причем если имеет место знак «+» то штриховка левее (ниже) прямой, в противном случае - правее (выше), а если ограничение имеет вид равенства, то штриховка отсутствует 2. Строится прямая в координатах переменных задачи линейного программирования, соответствующая целевой функции Z (для этого выбирается произвольное значение целевой функции)

94 Пример для графического решения задачи линейного программирования 3. Строится вектор нормали N к целевой функции Z. Вектор нормали указывает направление возрастания целевой функции 4. Перемещаем прямую Z = const в направлении N так, что бы она оставалась перпендикулярной N до тех пор, пока эта прямая не выйдет на границу множества D

95 Пример для графического решения задачи линейного программирования Таким образом, обобщенный графический метод решения задач линейного программирования заключается в выполнении следующего алгоритма: 1. Представляем задачу линейного программирования в стандартной канонической форме (предварительно проверяется условие n k 3) 2. Определяются координатные переменные (основное условие для их выбора линейная независимость) 3. Некоординатные переменные выражаются через координатные 4. Из условий неотрицательности некоординатных переменных получаем систему ограничений неравенств, содержащих только координатные переменные

96 Пример для графического решения задачи линейного программирования 5. В системе координатах переменных строим допустимое множество решений D, определяемое полученными ограничениями 6. Выражаем целевую функцию в координатных переменных 7. Строим целевую функцию Z 8. Строим вектор нормали N к целевой функции Z 9. Двигая целевую функцию в направлении вектора нормали, находим оптимальное решение как граничную точку допустимого множества

97 Лекция 1. Задачи линейного программирования (ЛП) Учебный вопрос 4. Симплекс-метод решения задачи ЛП

98 Симплекс-метод Согласно симплекс-методу оптимальный план достигается направленным перебором наборов базисных и свободных переменных Определяется начальный набор Затем каждый раз в наборе производится замена одной базисной переменной на свободную переменную, приводящую к улучшению плана Заменяемые переменные не повторяются

99 Симплекс-метод Так как число возможных наборов базисов ограничено (не более C n m ), то итерационный процесс конечен Опытным путем установлено, что для большей части задач число итераций составляет от 1,5m до 3m (где m – число уравнений-ограничений)

100 Симплекс-метод Все преобразования, реализующие симплекс-метод, проводятся не с самими уравнениями и целевой функцией, а с таблицами, составленными из коэффициентов при переменных и из свободных членов (см. таблицу на следующем слайде)

101 Симплекс-метод i j012…n 0Uc1c1 c2c2 …cncn 1b1b1 a 11 a 12 …a 1n 2b2b2 a 21 a 22 …a2na2n ……………… mbmbm am1am1 am2am2 …a mn

102 Алгоритм решения задачи на основе симплекс- метода Алгоритм решения задачи на основе симплекс-метода представляется последовательностью следующих шагов: Шаг 1. Приведение задачи к каноническому виду Шаг 2. Построение начального плана Шаг 3. Проверка оптимальности плана: 1. Если «да», то возможны два варианта: а) получен оптимальный план и в этом случае - «Оформление полученных результатов» и конец алгоритма; б) задача не имеет решения и выдача сообщения «Задача не имеет решения»; 2. Если «нет» (то есть некоторые коэффициенты имеют отрицательные значения) – переход на шаг 4.

103 Алгоритм решения задачи на основе симплекс- метода Шаг 4. Проверка «Разрешающий элемент выбран?»: - если «да» - переход на шаг 5; - если «нет» - выдача сообщения: «Целевая функция не ограничена» и конец алгоритма Шаг 5. Выполнение процедуры полного исключения с выбранным разрешающим элементом и переход на шаг 3

104 Алгоритм решения задачи на основе симплекс- метода Рассмотрим выполнение этих шагов алгоритма симплекс-метода на примере следующей постановки задачи.

105 Постановка задачи Для технического обслуживания и ремонта трех типов средств пожаротушения имеются четыре мастерских Мастерская типа j (j = 1, 2, 3, 4) может принять одновременно a ij средств пожаротушения типа i (i =1, 2, 3) и произвести их обслуживание и ремонт при стоимости c ij Каждый тип средств пожаротушения представлен b ij единицами Требуется найти, сколько потребуется мастерских каждого типа, чтобы обслужить все средства пожаротушения за один прием и с минимальными затратами Исходные данные к задаче приведены в таблице на следующем слайде

106 Постановка задачи i j U

107 Решение задачи Шаг 1. Приведение задачи к каноническому виду В зависимости от того, какой начальный вид имеет задача, применяют те или иные рассмотренные ранее преобразования В рассматриваемой задаче необходимо избавиться от неравенств Введем дополнительные переменные x 5, x 6 и x 7 Целевая функция и ограничения примут следующий вид: U = 4x 1 + 4x 2 +3x 3 +2x 4 +0x 5 +0x 6 + 0x 7 1x 1 + 2x 2 +4x 3 +0x 4 -1x 5 -0x 6 + 0x 7 = 24 3x 1 + 2x 2 +0x 3 +2x 4 +0x 5 -1x 6 + 0x 7 = 18 0x 1 + 4x 2 +3x 3 +1x 4 +0x 5 +0x 6 - 1x 7 = 18 x 1 0, x 2 0, x 3 0, x 4 0 Каждой дополнительной переменной можно придать смысл числа мастерских фиктивного типа, которые обслуживают средства пожаротушения, создающие превышение над заданным числом b i

108 Решение задачи Шаг 2. Построение начального плана Для построения начального плана систему уравнений необходимо преобразовать так, чтобы базисные переменные остались по одной в каждом уравнении, а коэффициенты при них стали равны единице Тогда после приравнивания остальных (свободных) переменных нулю сразу получим начальный план: X (1) = (x (1) 1, x (1) 2, …, x (1) j,…, x (1) m, 0, 0,…, 0), где x (1) 1 = β (1) 1, x (1) 2 = β (1) 2,…, x (1) m = β (1) m ; β (1) i – значения преобразованных свободных членов b i ; j / - порядковый номер базисной переменной в плане

109 Решение задачи Этому плану будет соответствовать значение целевой функции:

110 Решение задачи Начальный план (базис) может строиться различными способами Одним из общих способов является введение искусственных переменных В каждое уравнение ограничений, где нет базисной переменной, вводится искусственная переменная x n+k (k = 1, 2,…, m) с единичным коэффициентом К целевой функции все искусственные переменные x n+k присоединяются с общим коэффициентом М, значение которого выбирается достаточно большим (M >> max c j )

111 Решение задачи Доказано, что такой прием правомочен Если существует хотя бы одно допустимое решение, то в процессе оптимизации каждая из введенных переменных x n+k обратится в нуль Если же допустимых решений нет, то симплексные преобразования закончатся на решении, содержащем по меньшей мере одну искусственную переменную Наша задача не содержит в явном виде единичный базис

112 Решение задачи Введем искусственные переменные x 8, x 9 и x 10 Модель примет вид: U = 4x 1 + 4x 2 +3x 3 +2x 4 +0x 5 +0x x 7 +Мx 8 +Мx 9 +Мx 10 x 1 +2x 2 +4x 3 +0x 4 -1x 5 -0x 6 +0x 7 +1x 8 +0x 9 +0x 10 = 24 3x 1 +2x 2 +0x 3 +2x 4 +0x 5 -x 6 +0x 7 +0x 8 +1x 9 +0x 10 = =18 0x 1 +4x 2 +3x 3 +1x 4 +0x 5 +0x 6 -1x 7 +0x 8 +0x 9 +1x 10 = = 18 x j =0, j = 1, 2,…, 10

113 Решение задачи При записи начальной симплекс-таблицы, соответствующей этой модели, производят исключение искусственных переменных в целевой функции Для этого необходимо выразить каждую базисную переменную в уравнениях- ограничениях через свободные переменные, подставить в целевую функцию и привести подобные члены

114 Решение задачи Более просто данная процедура реализуется путем вычитания из целевой функции уравнений-ограничений, обе части которых предварительно умножаются на М Новые значения коэффициентов целевой функции находятся как

115 Решение задачи В дальнейшем по ним оценивается построенный план Левый элемент нулевой строки содержит значение целевой функции (U = 60M) Столбец свободных членов содержит значения базисных неизвестных

116 Решение задачи j i U- 60M 4-4M4-8M3-7M2-3MMMM

117 Решение задачи Приравняв небазисные переменные x 1, x 2, x 3, x 4, x 5, x 6 и x 7 нулю, получим значения базисных составляющих начального плана x 8 = 24, x 9 = 18 и x 10 = 18 План обеспечивает значение целевой функции U = 60M

118 Решение задачи Шаг 3. Проверка оптимальности плана Чтобы проверить, является ли полученный план оптимальным или нет, необходимо произвести анализ значений коэффициентов при свободных переменных в целевой функции (в строке 0 симплексной таблицы). Каждый коэффициент в строке 0 определяет положительное (если его значение больше нуля) или отрицательное (если его значение меньше нуля) приращение целевой функции U при увеличении на единицу соответствующей ему небазисной переменной

119 Решение задачи Если значения коэффициентов положительны, то, увеличивая какую-то свободную переменную сверх нуля (вводя ее в базисные переменные), мы не сможем уменьшить значение целевой функции Следовательно, либо получен оптимальный план и нужно переходить на шаг 6 (при отсутствии искусственных переменных в плане), либо задача не имеет решения (при наличии искусственных переменных в плане)

120 Решение задачи Если же некоторые коэффициенты имеют отрицательные значения, то при увеличении одной из соответствующих им свободных переменных можно добиться улучшения плана План x (1) не является оптимальным (γ 1, γ 2, γ 3 и γ 4 < 0)

121 Решение задачи Шаг 4. Выбор разрешающего элемента для улучшения плана Включению в план подлежит та из свободных переменных x s, для которой оценка γ s отрицательна и имеет наибольшее абсолютное значение: γ s < 0, γ s = max j | γ j |. Это обеспечивает (но не всегда) сокращение числа итераций

122 Решение задачи Теперь остается выяснить, какая базисная переменная должна исключаться из плана Тем самым мы определим, с каким значением будет введена свободная переменная Чем больше значение x s, тем меньше значение U Однако нельзя забывать об ограничениях

123 Решение задачи Из ограничений следует, что необходимо выводить ту переменную x r, у которой минимальное положительное значение отношения свободного члена к коэффициенту при переменной в столбце s:

124 Решение задачи Величина β i /α is определяет максимально допустимое значение базисной переменной x s в каждом ограничении Так, по условиям рассматриваемой задачи (s = 2): - исходя из возможностей обслуживания средств пожаротушения первого типа, можно взять x 1 = 24/2 = 12; - исходя из возможностей обслуживания средств пожаротушения второго типа x 2 = 18/2 = 9; - исходя из возможностей обслуживания средств пожаротушения третьего типа x 3 = 18/4 = 4,5. В целом максимально допустимым значением, очевидно, может быть x 3 = 4,5 (это узкое место).

125 Решение задачи Если для столбца S не окажется ни одной базисной переменной с положительным значением отношения β i /α is, то, значит, целевая функция не ограничена снизу Строку r, столбец s и элемент a rs принято называть разрешающими В рассматриваемой задаче разрешающим элементом будет элемент a 32 Для элемента a 32: γ 2 = 4 – 8M, β 3 /α 32 = 4,5

126 Решение задачи Шаг 5. Выполнение процедуры полного исключения с разрешающим элементом α rs Переход к новой симплекс-таблице обеспечивается выполнением процедуры полного исключения, широко используемой при решении систем линейных уравнений Все элементы разрешающей строки s делятся на значение разрешающего элемента α rs

127 Решение задачи Чтобы исключить переменную, которой соответствует коэффициент α rs, в остальных строках i (i = 0, 1, 2,…, m, i r), вычитают из каждой из них строку с α rs, умноженную на значение коэффициента α is

128 Решение задачи В результате получится новая таблица со значениями элементов: α rs / = 1; α rj / = α rj / α rs ; α ij / = α ij -(α rj / α rs )* α is, i = 0, 1, 2,…, m; j = 0, 1, 2,…, n; i r; i s.

129 Решение задачи Целевая функция подвергается тем же самым преобразованиям, что и ограничения задачи Поэтому целевая функция оказывается всегда выраженной через свободные переменные Реализация шагов 3, 4 и 5 представляет собой одну итерацию по улучшению плана Далее, начиная с шага 3, должна выполняться следующая итерация

130 Решение задачи Так как вводить искусственные переменные, исключенные из базиса на очередной итерации, в какой-то из последующих базисов не имеет смысла, то преобразование соответствующих им столбцов излишне Результаты первой итерации для рассматриваемой задачи представлены в таблице на следующем слайде

131 Решение задачи j i U- 24M M0-M-M1-M1-MMM1-M002М /2-1/201/210-1/ /2101/201-1/ /41/400-1/4001/4

132 Решение задачи Значение целевой функции при полученном плане уменьшилось до U (2) = -24M-18 После трех итераций все искусственные переменные (x 8, x 9 и x 10 ) окажутся исключенными из плана (см. таблицу на очередном слайде) Целевая функция примет значение U (4) = 38

133 Решение задачи j i U М011/32/310/913/ /9(4/3 )М /3 1/ /3-1/6-5/182/ /21/4-1/12-1/3

134 Решение задачи Но план не оптимален Для получения оптимального плана потребуется еще две итерации Последней итерации соответствует таблица на следующем слайде

135 Решение задачи j i U-361/41/2009/1235/ /4-3/200-3/4-1/21 293/ / /41/210-1/1200

136 Решение задачи Шаг 6. Оформление полученных результатов Полученные результаты представляются обычно в табличном виде (см. таблицу) Номер j Элементы решения x j Оценки c j

137 Решение задачи Эффективность оптимального решения равна 36 единиц Как следует из таблицы, оптимальным для решаемой задачи будет план: x (6) = {x 1 = 0, x 2 = 0, x 3 = 6, x 4 = 9} При этом затраты составят U (6) = 36 единиц и дополнительно еще может быть обслужено 9 средств пожаротушения, так как x 7 = 9

138 Решение задачи Даже для таких простых исходных данных, как в рассматриваемом примере, оптимальное решение не было сначала очевидным С увеличением размерности симплекс- таблицы об угадывании решения и говорить не приходится – его можно найти только, применяя математические методы