Тема 2. Линейные оптимизационные модели и линейное программирование

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

Общая постановка и различные формы задачи ЛП. Геометрия задач ЛП. Выпуклые множества. Выпуклые оболочки. Вершины многогранного множества. Экстремумы линейной функции на многограннике и многогранном множестве. Алгебра задач ЛП. Базисные и допустимые базисные решения. Связь вершин многогранника допустимых решений и базисных решений. Понятие о симплекс-методе решения задач ЛП.

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

Теория двойственности в ЛП. Взаимно двойственные задачи. Теоремы двойственности. Содержательная интерпретация двойственных переменных. Анализ чувствительности оптимального решения к изменениям параметров задачи.

Литература:

Базовый учебник: [3] (гл. 1-7).

Основная литература: [5] (гл. 1), [8]

Дополнительная литература: [15].

 

Тема 3. Задачи, сводящиеся к линейному программированию. Модели и методы целочисленного линейного программирования.

Задачи дробно-линейного программирования и сведение их к задаче ЛП. Пример - задача об оптимальной рентабельности производства.

Задачи кусочно-линейного программирования, максиминные задачи, методы их решения.

Задачи целочисленного линейного программирования. Метод ветвей и границ. Особенности решения задач с булевыми переменными. Задача об оптимальном наборе инвестиционных проектов. Учет логических условий. Задачи дискретного программирования и их сведение к задаче целочисленного ЛП.

Компьютерные системы линейного программирования.

Литература:

Базовый учебник:[3] (гл. 8).

Основная литература: [11] (гл. 3, 4).

Дополнительная литература: [17]

 

Тема 4. Нелинейные оптимизационные модели и нелинейное программирование

Принятие решений в условиях определенности; детерминированная статическая задача оптимизации. Математическое программирование – аппарат решения оптимизационных задач. Классификации задач математического программирования. Содержательные примеры.

Классические методы оптимизации (повторение). Виды экстремумов. Достаточное условие существования глобального экстремума (теорема Вейерштрасса). Безусловная оптимизация (в отсутствии ограничений). Производная по направлению и градиент. Необходимые и достаточные условия локального экстремума. Задача на условный экстремум, примеры из экономики. Функция Лагранжа. Необходимые и достаточные условия условного экстремума. Интерпретация множителей Лагранжа.

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

Общая задача нелинейного программирования. Функция Лагранжа. Условия локального экстремума в задаче оптимизации на неотрицательном ортанте. Теорема Куна-Таккера в «седловой» и дифференциальной форме. Условие Слейтера и его существенность. Условия дополняющей нежесткости.

Понятие о численных методах решения задач нелинейного программирования. Классификация методов. Безусловная оптимизация: градиентные методы и методы второго порядка. Условная оптимизация, метод штрафных функций.

Компьютерные системы для решения задач нелинейного программирования.

Литература:

Базовый учебник: [1] (темы 3,4), [4] (гл. 2-4), [3] (гл. 10-11,13).

Основная литература: [7], [11] (гл. 5).

Дополнительная литература: [17] (гл. 3).

Тема 5. Многокритериальное принятие решений

 

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

Достаточные условия оптимальности по Парето и Слейтеру в форме свертки критериев в один обобщенный (глобальный, интегральный) критерий (скаляризация). Коэффициенты важности в линейных свертках.

Необходимые условия оптимальности в выпуклом случае. Многокритериальные задачи линейного программирования, необходимые и достаточные условия оптимальности для них. Построение оптимальных по Парето решений в задаче ЛП с использованием линейных сверток.

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

Методы выбора единственного решения из множества Парето-оптимальных решений. Использование линейных и нелинейных функций свертки, ограниченность такого подхода, в частности, применения весовых коэффициентов. Среднеквадратическое решение, решение Нэша. Метод уступок. Целевое программирование.

Литература:

Базовый учебник: [1] (тема 7)

Основная литература: [10] (гл. 1-2), [11] (гл. 7)

Дополнительная литература: [16].

 

Тема 6. Принятие решений в условиях неопределенности

 

Задачи оптимизации в условиях неопределенности. Виды неопределенности: вероятностная (статистическая), полная (неустранимая, существенная), комбинированная. Принципы оптимальности (критерии выбора решений) в случае полной неопределенности – Вальда (гарантированного результата, максимина,) Гурвица (пессимизма-оптимизма), Сэвиджа (минимаксного сожаления), Бернулли-Лапласа (недостаточного основания).

Оптимизация в условиях вероятностной неопределенности (при риске). Дисперсия как характеристика риска. Сведение исходной задачи к задаче с двумя критериями – характеристикой среднего значения (математическое ожидание) и характеристикой риска (дисперсия).

Литература:

Базовый учебник: [2], (тема 10).

Дополнительная литература: [17] (гл. 7), [21] (гл. 1).

 

 

Тематика заданий по различным формам текущего контроля

Контрольная работа содержит задачи по следующим темам дисциплины:

- построение моделей по вербальному описанию задачи, линейное программирование, двойственность в ЛП, целочисленное программирование (темы 1, 2, 3);

- домашнее контрольное задание: многокритериальные задачи и их сведение к однокритериальным (тема 5);

- письменный экзамен: нелинейное программирование, численные методы, многокритериальная оптимизация, принятие решений при неопределенности (темы 4, 5,6);

Методические рекомендации преподавателю

Одно из практических занятий по теме 3. «Линейные оптимизационные модели и линейное программирование» целесообразно провести в компьютерном классе.

Методические указания студентам

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

Рекомендации по использованию информационных технологий

Для решения задач линейного программирования можно использовать любую имеющуюся компьютерную программу, которая позволяет проводить анализ чувствительности, в частности, MS Exсel.

 

 

8 Оценочные средства для текущего контроля и аттестации студента

Примерная тематика заданий текущего контроля

Контрольная работа

Темы: «Линейное программирование. Двойственность»

ЗАДАЧА 1. Приведите следующую задачу линейного программирования (ЛП) к стандартному виду (исключением базисных переменных) и к каноническому виду.

 

2 x₁ + 3 x₂ + 4 x₃ -x₄ ≤ 11

x₁ - x₂ + x₃ +x₄ =1

x₁ + x₂ – 2 x₃ + x₅ = 0

x _i≥0 (i=1,…,5)

F= x₁ +x₂ +x₅ àmax

 

ЗАДАЧА 2. Формализуйте приведенную задачу в виде задачи ЛП: введите обозначения, выпишите ВСЕ ограничения и целевую функцию. (РЕШАТЬ полученную задачу не надо).

Бетонный завод может выпускать четыре сорта бетона. При этом используется 3 вида сырья: цемент, песок, щебень, запасы которых известны. Известны также удельные затраты сырья, а также доход от выпуска кубометра каждого вида бетона.

Требуется найти план производства, который обеспечивает максимум дохода.

Задайте конкретные числовые данные и после этого запишите задачу в виде задачи ЛП.

ЗАДАЧА 3. Найти оптимальное решение приведенной задачи ЛП, используя графическое решение двойственной задачи и условия дополняющей нежесткости.

x₁ + x₂ ≥ 1

x₁ + x₃ ≥ 1

x₁, x₂, x₃ ≥ 0

Z = 1,5 x₁ + x₂ + x₃ è min

ЗАДАЧА 4. Найти допустимое базисное решение транспортной задачи с помощью метода наименьшей стоимости северо-западного угла.

	B1	B2	B3	Запасы
A1
A2
A3
Спрос

ЗАДАЧА 5. Дана следующая задача ЛП

3 x₁ +x₂ + 2 x₄ =6

x₃ + 5 x₄ =10

x₁, x₂, x₃, x₄ ≥0

Z = 2 x₁ + 3 x₂ -4 x₃ + 17 x₄ è min

Какой (какие) из следующих наборов, могут быть допустимым базисным решением.

Объясните почему.

	может/нет	Объяснение - почему
(1,0,0,2),
(0,4,5,1),
(0,6,10,0),
(0,0, - 5,3)
(2,0,10,0)

 

Теоретические вопросы.

Какова верхняя оценка максимального числа шагов в симплекс-методе до достижения решения и почему реальное число шагов гораздо меньше этой оценки?

Может ли оптимальное решение замкнутой транспортной задачи с целочисленными условиями (запасами и запросами) быть нецелочисленным?

 

Домашнее контрольное задание