Содержание дисциплины

№ п/п	Наименование разделов и тем дисциплины	Содержание темы
Раздел 1 Проблема математической поддержки управленческих решений
Тема 1	Проблема математической поддержки управленческих решений	Понятие проблемной ситуации. Слабо и хорошо формализуемые ситуации. Типовые управленческие задачи, поддающиеся формализации. Математические проблемы математической поддержки управленческих решений.
Раздел 2 Методы условной оптимизации по одному критерию
Тема 2	Линейное программирование последователь­ностей и функций	Каноническая, стандартная, общая форма задачи линейного программирования. Понятие выпуклого множества. Базисные и небазисные переменные. План задачи. Оптимальный план задачи. Основные теоремы линейного программирования.
Тема 3	Симплекс-метод	Теоретические основы; алгоритм; начальная итерация, признаки неограниченности линейной формы, признаки несовместности условий задачи линейного программирования.
Тема 4	Двойственная задача линейного программирования	Экономическая интерпретация; принцип формирования; теорема двойственности; теорема Данцига\Ордена.
Тема 5	Транспортная задача линейного программирования	Вербальная и формальная постановки задачи; метод потенциалов; правило северо-западного угла; алгоритм расчета потенциалов; расчет характеристических разностей; признаки оптимальности опорного плана; преобразование плана; задача линейного программирования; решение открытой формы транспортной задачи.
Тема 6	Задача динамического программирования	Вербальная и формальная постановки задачи; принцип оптимальности Беллмана; идея сведения общей задачи к задачам оптимизации единственной переменной; вычисления в «прямом времени»; вычисления в «обратном времени».
Раздел 3 Целочисленное программирование
Тема 7	Метод ветвей и границ	Основные понятия. Правила отсечения. Вычислительные проблемы.
Тема 8	Метод Гомори	Алгоритм Гомори: суть, достоинства, проблемы использования.
Раздел 4 Антагонистические игры
Тема 9	Антагонистические игры	. Понятие об игровых моделях, Матричные игры. Максиминная и минимаксная стратегия. Ровновесная ситуация. Седловая точка игры. Решение игр в смешанных стратегиях. Основная теорема матричных игр. Сведение матричной игры к паре двойственных задач линейного программирования. Алгоритм решения матричных игр.
Раздел 5Методы сетевого планирования
Тема 10	Построение сетевого графика	Область применения методов сетевого планирования и управления (СПУ). Основные понятия. Сетевая модель и диаграмма Ганта. Основные действия при использовании методов сетевого планирования. Формальные правила построения сетевого графика. Критическое время комплекса работ: определение, формулы расчета. Резерв времени: определение, формулы расчета, рекомендации по использованию. Критические пути, способы определения. Основные свойства работ сетевого графика. Полный резерв времени. Частный резерв времени второго вида. Независимый резерв времени. Коэффициент напряженности.
Тема 11	Оптимизация сетевого графика	Постановка задачи оптимизации сетевого графика. Оптимизация сетевого графика по времени. Оптимизация сетевого графика по ресурсам. Комплексная оптимизация сетевого графика.

ПЛАНЫ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

ТЕМА 2. Линейное программирование

Занятие 1. Графическое решение задачи линейного програм­мирования

Контрольные вопросы

1.Дайте постановку задачи линейного программирования в общей форме.

2.Дайте определение допустимого и оптимального решения задачи линейного программирования.

3.Сформулируйте задачу линейного программирования в канонической форме.

4.Какие решения задачи называются базисными допусти­мыми решениями?

5.Приведите геометрическую интерпретацию оптимального решения.

Задачи для решения

1. Составить экономико-математическую модель задачи об использовании ресурсов (задача планирования производства).

Для изготовления двух видов продукции П1 и П2 использу­ют четыре вида ресурсов SI, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы про­дукции, приведены в табл. 1.1 (цифры условные).

Таблица 1. 1

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукта
П1	П2
S1
S2
S3
S4

Прибыль, получаемая от единицы продукции П1 и П2, соот­ветственно 20 и 30 тыс. руб.

Необходимо найти план производства, при котором при­быль от её реализации будет максимальной.

2.Выпишите формулы для преобразования следующих огра­ничений к канонической форме:

a_ji x_j £ b_j; х без ограничений.

на дом

a_ji x_i ≥ b_j; х без ограничений.

3. Привести задачу линейного программирования к канони-
ческой форме.

x₁ + х₂ —> max

2 x₁ + х₂ ≥ 1,

x₁ - х₂ £ О,

x₁ ≥0,х₂ ≥0.

на дом

х₁ + х₂ + х₃ —> min

x₁ - х₃ £ 1,

х₂ + х₃ ≥ 1,

х_j ≥ 0.

4. Найти все допустимые базисные решения задачи линейного программирования с ограничениями.

х₁ + х₂ £ 5

1.5 х₁ + х₂ £ 6,

x₁ ≥ 0, х₂ ≥ 0.

на дом

- 2х₁ + х₂ £1,

0 £ x₁ £ 1, х₂ ≥2.

5. Решить задачу линейного программирования, используя
геометрическую интерпретацию.

x₁ + 2х₂ —> max

x₁ — х₂ £ 1,

х₁, х₂≥0

на дом

5x₁ - 10х₂ —> min

-2 х₁+ х₂ £ 1,

- х₁ + х₂ £2,

- З x₁ + х ₂ £ 8,

- 2 x₁ + З х ₂ ≥ -9,

- 4 х ₁ + З х ₂ ≥0,

Занятие 2. Симплекс метод

Контрольные вопросы

1. Дайте определение симплекс-разности.

2.Сформулируйте условие получения оптимального реше­ния в симплекс-методе.

3.Сформулируйте условие неограниченности целевой функ­ции задачи ЛП.

4.Как производится нахождение первоначального допусти­мого базисного решения?

Задачи для решения

1. Решите задачу линейного программирования симплекс методом.

-2 х ₁ - З х ₂ + 2 х ₄ + З х ₅ —» max

2 х ₁ — х ₂ + х ₃ £12,

x₁ + х ₄ £ 5,

2 х ₁ + 2 х ₂ + х ₃ - 2 х ₅ £20,

х₁ - х₂- 2 х ₃+2 х ₄-2 х ₅£10

-2 x₁ + 2 х ₂ - 2 х ₃ - 2 х ₄ + х ₅ £ 24,

x₁,..., х ₅ ≥0

2.Решить задачу линейного программирования двухфазным симплекс методом.

5х₁+ 6х₂ + 4х₃ + 8х₄ + 9х₅ —> min

х₁+ х₂ + х₃ +-х₄ = 7

2х₁+ 3х₃ +8х₄ = 13,

х₁ + 2х₃ + х₅= 8

х₁,...,х₅ ≥ 0.

Занятие 3. Двойственная задача линейного программирова­ния

Контрольные вопросы

1. Дайте определение симметричной пары двойственных за­дач.

2. Как связаны решения прямой и двойственных задач?.

3. Сформулируйте условия дополняющей нежесткости.

Задачи для решения

1.Определить двойственную задачу к задаче.

с₁х₁ +... + с_пх_п —» max

a_ji x_j £ b_j

x_j< 0,j =1,...,n.

2. Сформулировать и решить двойственную задачу к

Исходной задаче:

f(X) = 3x₁ + 2x₂ + 4x₃ + x₄ max

при условиях

2x₁ + 2x₂ + 4x₃ + 2x₄ ≤ 12,

4x₁ + 6x₂ + x₃ + x₄ ≤ 25,

( j), x_j ≥ 0

Исследовать задачу графическим методом используя пе­реход к двойственной задаче.

ТЕМА 3. Целочисленное программирования

Контрольные вопросы

1. Дайте определение задачи целочисленного программиро­вания.

2. Сформулируйте основную идею метода Гомори.

3. Сформулируйте основную идею решения задачи целочис­ленного программирования методом ветвей и границ.

4. Выпишите основные шаги решения задачи выпуклого программирования.

Задачи для решения

1. Решить задачу целочисленного программирования мето­дом Гомори и методом ветвей и границ.

7x₁ + 9х₂ —> max

x₁ + Зх₂ < 6, 7x₁ + х₂ <35,

x₁,х₂ > 0, x₁,х₂ – целые числа.

на дом

x₁ +1.5х₂ —> max

x₁ + 2х₂ < 8, 2 x₁ + х₂ < 8,

x₁,х₂ >0, x₁,х₂ – целые числа.

ТЕМА 4. Динамическое программирование

Контрольные вопросы

1. Сформулируйте основную идею решения задачи целочис­ленного программирования методом ветвей и границ.

2. Дайте определение задачи о рюкзаке.

3. Сформулируйте основные шаги решения задачи о рюкзаке.

4. Опишите общую схему решения задач методом динами­ческого программирования.

Задачи для решения

1. Решить методом динамического программирования задачу
о рюкзаке.

2х_{ + Зх₂ + х₃ + 2х₄ -» max,

х₁ + 2х₂ + х₃ + 2х₄ < 4, х_к {0,1}, к = 1,2, 3, 4.

2. Решить методом динамического программирования задачу:

при условии

- целые неотрицательные числа

ТЕМА 5. Антагонистические игры двух лиц

Занятие 1

Контрольные вопросы

1. Дайте общее определение игры.

2. Дайте определение антагонистической игры двух лиц.

3. Дайте определение нижней и верхней цены игры, цены игры.

4. Дайте определение максиминной и минимаксной стра­тегий.

Задачи для решения

1. Найти максиминные и минимаксные стратегии, верх­нюю и нижнюю цены антагонистической игры, заданной платеж­ной матрицей:

Занятие 2

Контрольные вопросы

1. Дайте определение седловой точки для матричной игры двух лиц.

2. Сформулируйте как взаимосвязаны масиминная и мини­максная стратегии и седловая точка.

Занятие 3

Контрольные вопросы

1. Дайте определение смешанного расширения матричной игры.

2. Сформулируйте основные свойства функции выигрышей в смешанных стратегиях.

3. Сформулируйте теорему фон Неймана.

4. Дайте определение доминирующей и доминируемой стратегий.

Задачи для решения

'

1. Решить матричную игру в смешанных стратегиях, задан­ную платежной матрицей

Тема. Методы сетевого планирования

1. Рассчитать временные характеристики работ;

2. Определить критические пути;

3. Рассчитать коэффициенты напряженности работ;

4. Расположить работы по зонам напряжённости.

№	Работа	Продолжительность работ (в днях)
1.	(0,1)
2.	(0,3)
3.	(0,5)
4.	(1,2)
5.	(1,3)
6.	(1,4)
7.	(2,7)
8.	(3,4)
9.	(3,5)
10.	(3,6)
11.	(4,6)
12.	(4,7)
13.	(5,6)
14.	(5,8)
15.	(5,9)
16.	(6,7)
17.	(6,8)
18.	(6,9)
19.	(6,10)
20.	(7,10)
21.	(8,9)
22.	(9,10)
23.	(9,11)
24.	(10,11)