Консультация_к_экзамену-1

1.

НИУ ВШЭ · ВЫСШАЯ ШКОЛА БИЗНЕСА · ОП «УПРАВЛЕНИЕ БИЗНЕСОМ»
Исследование операций
и методы оптимизации
Консультация к экзамену
Все темы экзамена и разбор примера экзаменационных заданий
1 модуль 2026/2027

2.

ТЕМА 1
Линейное программирование
Модель → графический метод → симплекс-метод
Задание 1 из примера

3.

ЗАДАНИЕ 1 · УСЛОВИЕ
Предприятие: сырьё и рабочая сила
Предприятие располагает ресурсами сырья и рабочей силы для производства двух видов продукции. Затраты
ресурсов на 1 т продукта, прибыль от реализации 1 т и запасы ресурсов — в таблице. Напишите математическую
модель. Задачу не решая, ответьте: какими методами её можно решить и почему.
Продукт 1
Продукт 2
Запас
Сырьё, т
3
5
120
Дано / обозначим / найти
Трудозатраты, ч
14
12
400
Ресурсы: сырьё 120 т, труд 400 ч.
Прибыль, тыс. руб./т
30
35
—
x1 — сколько тонн продукта 1 выпустить;
x2 — сколько тонн продукта 2 выпустить.
Найти план (x1; x2) с максимальной
прибылью F.
Переменные — всегда с единицами измерения:
«тонн продукта», а не просто «продукт».
Где посмотреть: семинар 1 (Семинар_1_НОВЫЙ_задачи_лекции.pptx), лекция 2–3.

4.

ЗАДАНИЕ 1 · МОДЕЛЬ
Математическая модель задачи
F = 30x1 + 35x2 → max
прибыль, тыс. руб.
3x1 + 5x2 ≤ 120
сырьё, т: расход не больше запаса
14x1 + 12x2 ≤ 400
Как составлять модель — 4 шага
1. Переменные: что решает менеджер, в каких
единицах.
2. Целевая функция: что максимизируем или
минимизируем (прибыль, затраты).
трудозатраты, ч
3. Ограничения: для каждого ресурса «расход ≤
запас»; для спроса — «≥» или «≤».
x1 ≥ 0, x2 ≥ 0
4. Неотрицательность (и целочисленность, если
штуки неделимы).
выпуск не может быть отрицательным
Смысл каждого ограничения подписываем словами —
это часть ответа.

5.

ЗАДАНИЕ 1 · ОТВЕТ НА ВОПРОС
Какими методами можно решить и почему
Графический метод
Симплекс-метод
Чего не нужно
Переменных две (x1, x2) —
область допустимых решений
рисуется на плоскости.
Задача на максимум, все
ограничения «≤» с
неотрицательными правыми
частями.
Целочисленность не требуется
(тонны делимы) — метод
Гомори не нужен.
Оптимум — в вершине
многоугольника; находим её по
линии уровня F или перебором
вершин.
Добавляем дополнительные
переменные x3, x4 — они дают
начальный базис,
искусственный базис не нужен.
Функция и ограничения линейны
— это ЛП, а не нелинейное
программирование (не метод
Лагранжа).
Формулировка ответа. Задача ЛП с двумя переменными: решается графически; в общем случае — симплексметодом, начальный базис — дополнительные переменные, так как все ограничения «≤», b ≥ 0.

6.

ЗАДАНИЕ 1 · ГРАФИЧЕСКИЙ МЕТОД
Строим область допустимых решений
x2, т
Порядок
30
1. Каждое ограничение → прямая по двум
точкам:
3x1 + 5x2 = 120: (0; 24) и (40; 0);
14x1 + 12x2 = 400: (0; 33,3) и (28,6; 0).
(2) труд
C
2. Знак «≤» → полуплоскость к началу
координат (проверка точкой (0; 0): 0 ≤ 120 —
верно).
20
3. Пересечение полуплоскостей и x ≥ 0 —
ОДР (OABC).
B
4. Вектор (30; 35) — направление роста F.
Двигаем линию уровня до последней точки
ОДР — это B.
рост F (30; 35)
10
O
0
0
A
10
20
30
(1) сырьё
40
x1, т

7.

ЗАДАНИЕ 1 · ГРАФИЧЕСКИЙ МЕТОД
Координаты точки B и проверка вершин
Вершина
x1
x2
F = 30x1 + 35x2
B — пересечение прямых (1) и (2)
O
0
0
0
3x1 + 5x2 = 120
14x1 + 12x2 = 400
A
28,57
0
857,1
B
16,47
14,12
988,2
Из первого: x1 = (120 − 5x2) / 3. Подставим во второе:
14(120 − 5x2)/3 + 12x2 = 400 | · 3
1680 − 70x2 + 36x2 = 1200 → 34x2 = 480
C
0
24
840
x2 = 240/17 ≈ 14,12 т
x1 = (120 − 5 · 240/17) / 3 = 280/17 ≈ 16,47 т
Ответ
x1 = 280/17 ≈ 16,47 т; x2 = 240/17 ≈ 14,12 т
Fmax = 16 800/17 ≈ 988,24 тыс. руб.
Оба ресурса израсходованы полностью (обе прямые
проходят через B).

8.

ЗАДАНИЕ 1 · СИМПЛЕКС-МЕТОД
Каноническая форма и начальная таблица
БП
x1
x2
x3
x4
b
b / aiₛ
Каноническая форма
F
−30
−35
0
0
0
—
3x1 + 5x2 + x3 = 120
14x1 + 12x2 + x4 = 400
x3
3
5
1
0
120
24
x4
14
12
0
1
400
100/3
F = 30x1 + 35x2 + 0x3 + 0x4 → max
x3, x4 — остатки сырья и часов.
Начальный план
Правила выбора (max)
x1 = x2 = 0 (ничего не выпускаем), x3 = 120, x4 = 400, F = 0.
Строка F: Δj = −cj (−30, −35).
Столбец — наибольший по модулю
отрицательный Δj: x2.
Строка — min b / aiₛ при aiₛ > 0: min(24; 33,3) → x3.
Ведущий элемент — 5.
В строке F есть отрицательные Δ → план можно улучшить.
Вводим в базис x2 (самый «выгодный» на единицу), выводим
x3: сырьё кончится раньше труда.

9.

ЗАДАНИЕ 1 · ИТЕРАЦИЯ 1
x2 входит в базис, x3 выходит
Пересчёт строк
Новая строка x2 = строка x3 / 5:
(3/5; 1; 1/5; 0 | 24)
Строка x4 − 12 · (новая x2):
БП
x1
x2
x3
x4
b
b / aiₛ
F
−9
0
7
0
840
—
x2
3/5
1
1/5
0
24
40
x4
34/5
0
−12/5
1
112
280/17
400 − 12·24 = 112; 14 − 12·3/5 = 34/5
0 − 12·1/5 = −12/5; 1 − 0 = 1
Строка F + 35 · (новая x2):
0 + 35·24 = 840; −30 + 35·3/5 = −9
0 + 35·1/5 = 7
Правило: из каждой строки вычитаем ведущую
строку, умноженную на элемент этой строки в
ведущем столбце.
Что получилось
План: x2 = 24, x4 = 112 (остаток часов), F = 840 — это точка C
графика.
Δ1 = −9 < 0 → вводим x1.
Отношения: 24 : 3/5 = 40; 112 : 34/5 = 280/17 ≈ 16,5 → выводим
x4.

10.

ЗАДАНИЕ 1 · ИТЕРАЦИЯ 2
x1 входит в базис — план оптимален
БП
x1
x2
x3
x4
b
Пересчёт строк
F
0
0
65/17
45/34
16800/17
Новая строка x1 = строка x4 : 34/5 (умножаем на
5/34):
x2
0
1
7/17
−3/34
240/17
(1; 0; −6/17; 5/34 | 280/17)
x1
1
0
−6/17
5/34
280/17
Строка x2 − 3/5 · (новая x1):
24 − 3/5·280/17 = 240/17
1/5 + 3/5·6/17 = 7/17; 0 − 3/5·5/34 = −3/34
Строка F + 9 · (новая x1):
840 + 9·280/17 = 16 800/17
7 − 9·6/17 = 65/17; 0 + 9·5/34 = 45/34
Оптимум
Все Δj ≥ 0 → план оптимален (точка B графика).
x1 = 280/17 ≈ 16,47 т; x2 = 240/17 ≈ 14,12 т
Fmax = 16 800/17 ≈ 988,24 тыс. руб.
x3 = x4 = 0: сырьё и труд израсходованы полностью.
Совпадает с графическим решением — так и проверяем.

11.

ТЕМА 2 · ДВОЙСТВЕННАЯ ЗАДАЧА
Алгоритм составления двойственной задачи (лекция 4)
Смысл пары задач
Алгоритм (лекция 4, сл. 6)
Прямая: план выпуска X, при котором прибыль
максимальна, а расход ресурсов не превышает
запасов.
1. Стандартный вид: в задаче на max все неравенства
«≤», на min — «≥». Неподходящие умножаем на −1.
Двойственная: оценки (цены) ресурсов Y, при которых
общая стоимость ресурсов минимальна, а затраты
ресурсов на каждый продукт не меньше прибыли от
него.
Лекция 4, сл. 4.
2. Расширенная матрица A1: коэффициенты A, справа
столбец свободных членов b, снизу строка
коэффициентов целевой функции c.
3. Транспонируем A1 (строки
столбцы).
4. Читаем двойственную: max
min; последний
столбец A1ᵀ — правые части, последняя строка —
коэффициенты новой функции; «≤» → «≥»; все yi ≥ 0.
Где посмотреть: лекция 4, сл. 2–8 (на семинарах двойственность не разбирали — материал лекции).

12.

ТЕМА 2 · ПРИМЕР ЛЕКЦИИ · ШАГ 1
Стандартный вид: все неравенства «≤»
Исходная задача
Стандартный вид
F = −x1 + 2x2 → max
Задача на max → нужны «≤». Первое и четвёртое
неравенства умножаем на −1:
2x1 − x2 ≥ 1
−x1 + 4x2 ≤ 24
x1 − x2 ≤ 3
x1 + x2 ≥ 5
x1 ≥ 0, x2 ≥ 0
Лекция 4, сл. 7.
−2x1 + x2 ≤ −1
−x1 + 4x2 ≤ 24
x1 − x2 ≤ 3
−x1 − x2 ≤ −5
Знак неравенства при умножении на −1 меняется, правая
часть может стать отрицательной — это нормально.

13.

ТЕМА 2 · ПРИМЕР ЛЕКЦИИ · ШАГИ 2–4
Матрица, транспонирование, двойственная задача
A1
x1
x2
b
A1ᵀ
y1
y2
y3
y4
c
y1
−2
1
−1
x1
−2
−1
1
−1
−1
y2
−1
4
24
x2
1
4
−1
−1
2
y3
1
−1
3
b
−1
24
3
−5
Z
y4
−1
−1
−5
c
−1
2
F
Двойственная задача
A1 — коэффициенты стандартного вида,
справа b, снизу c. Каждому ограничению
прямой — своя переменная yi.
Z = −y1 + 24y2 + 3y3 − 5y4 → min
A1ᵀ — та же матрица, повёрнутая:
столбец x1 стал строкой.
y1 + 4y2 − y3 − y4 ≥ 2
−2y1 − y2 + y3 − y4 ≥ −1
y1, y2, y3, y4 ≥ 0
Строки A1ᵀ — ограничения; последняя строка (b) — коэффициенты Z; последний столбец
(c) — правые части.

14.

ТЕМА 3
Транспортная задача
Баланс → наименьший тариф (как на семинаре) → метод Фогеля → потенциалы
Задание 2 из примера

15.

ЗАДАНИЕ 2 · УСЛОВИЕ
Руда: четыре карьера, три фабрики
Четыре карьера C1–C4 добывают 170, 150, 190 и 200 тыс. т руды в месяц. Обогатительные фабрики S1–S3 могут
принять 250, 150 и 270 тыс. т. Затраты на перевозку 1 тыс. т (тыс. руб.) — в таблице. Определите опорный план
перевозок по методу Фогеля, обеспечивающий минимальные издержки.
Карьер \ Фабрика
S1
S2
S3
Добыча
C1
7
3
8
170
Шаг 0. Баланс
C2
5
4
6
150
Добыча: 170 + 150 + 190 + 200 = 710 тыс. т.
C3
4
5
9
190
C4
6
2
5
200
Мощность
250
150
270
Мощность фабрик: 250 + 150 + 270 = 670 тыс. т.
710 > 670 — задача открытая
Добавляем фиктивную фабрику S4 с мощностью
710 − 670 = 40 тыс. т и нулевыми тарифами.
Перевозка «на S4» = руда, которая остаётся на
карьере.
Где посмотреть: семинар 3 (транспортная задача: баланс, опорный план, потенциалы), лекция 5, ДЗ 2.

16.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ
Сначала — как на семинаре: метод наименьшего тарифа
Тариф
Клетки
Алгоритм
2
C4–S2
1. Среди невычеркнутых клеток выбираем клетку с
наименьшим тарифом.
3
C1–S2
4
C2–S2, C3–S1
5
C2–S1, C3–S2, C4–S3
6
C2–S3, C4–S1
7
C1–S1
8
C1–S3
9
C3–S3
0
S4: C1–S4 … C4–S4 — в конце
2. Ставим туда максимум возможного: min(остаток карьера;
остаток фабрики).
3. Вычёркиваем исчерпанную строку или столбец.
4. Повторяем, пока всё не распределим. Занятых клеток
должно быть m + n − 1.
Фиктивную фабрику S4 заполняем последней: её
нулевые тарифы — не настоящие перевозки.
На семинаре 3 — «метод минимального элемента» (лекция 5, сл.
8). При равных тарифах можно брать любую клетку — здесь
берём верхнюю.
Идём по списку сверху вниз; клетки в уже вычеркнутых строках и
столбцах пропускаем.
Где посмотреть: семинар 3 (опорный план: северо-западный угол и минимальный элемент), лекция 5, сл. 8.

17.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 1 ИЗ 7
Клетка C4–S2: перевозим 150 тыс. т
S1
C1
C2
C3
C4
остаток
7
S2
3
5
8
4
4
250
150
150
0
5
190
0
270
остаток
170
0
9
2
S4*
0
6
5
6
S3
200
40
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
Выбор клетки
Клетка C4–S2: наименьший из доступных тарифов
— 2.
Перевозка
x = min(200; 150) = 150
S2 заполнена — вычёркиваем столбец S2; у C4
осталось 50.

18.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 2 ИЗ 7
Клетка C3–S1: перевозим 190 тыс. т
S1
C1
C2
C3
C4
остаток
7
S2
3
5
8
4
4
2
250
0
0
5
0
270
остаток
170
0
9
150
S4*
0
6
5
6
S3
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
Пропускаем C1–S2 (3); C2–S2 (4): строка или
столбец уже вычеркнуты.
150
Клетка C3–S1: наименьший из доступных тарифов
— 4.
190
Перевозка
50
40
Выбор клетки
x = min(190; 250) = 190
C3 вывез всё — вычёркиваем строку C3; S1
осталось принять 60.

19.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 3 ИЗ 7
Клетка C2–S1: перевозим 60 тыс. т
S1
C1
C2
C3
C4
остаток
7
3
5
4
S2
8
4
190
6
60
S3
S4*
0
6
9
0
2
5
0
150
0
170
0
5
270
остаток
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
Клетка C2–S1: наименьший из доступных тарифов
— 5.
150
Тот же тариф у C4–S3. При равенстве берём верхнюю
клетку; план здесь от этого не меняется.
0
Перевозка
50
40
Выбор клетки
x = min(150; 60) = 60
S1 заполнена — вычёркиваем столбец S1; у C2
осталось 90.

20.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 4 ИЗ 7
Клетка C4–S3: перевозим 50 тыс. т
S1
C1
C2
C3
C4
остаток
7
5
4
S2
3
60
190
6
0
8
4
0
0
5
0
270
остаток
170
0
9
150
S4*
0
6
5
2
S3
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
Пропускаем C3–S2 (5): строка или столбец уже
вычеркнуты.
90
Клетка C4–S3: наименьший из доступных тарифов
— 5.
0
Перевозка
50
40
Выбор клетки
x = min(50; 270) = 50
C4 вывез всё — вычёркиваем строку C4; S3
осталось принять 220.

21.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 5 ИЗ 7
Клетка C2–S3: перевозим 90 тыс. т
S1
C1
C2
C3
C4
остаток
7
5
4
S2
3
60
190
6
0
8
4
150
0
90
0
50
220
остаток
170
0
9
5
S4*
0
6
5
2
S3
0
0
0
40
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
Выбор клетки
Клетка C2–S3: наименьший из доступных тарифов
— 6.
Перевозка
x = min(90; 220) = 90
C2 вывез всё — вычёркиваем строку C2; S3
осталось принять 130.

22.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 6 ИЗ 7
Клетка C1–S3: перевозим 130 тыс. т
S1
C1
C2
C3
C4
остаток
7
5
4
S2
3
60
190
6
0
8
4
6
5
2
S3
0
90
9
150
0
5
S4*
170
0
0
50
130
остаток
0
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
Пропускаем C4–S1 (6); C1–S1 (7): строка или
столбец уже вычеркнуты.
0
Клетка C1–S3: наименьший из доступных тарифов
— 8.
0
Перевозка
0
40
Выбор клетки
x = min(170; 130) = 130
S3 заполнена — вычёркиваем столбец S3; у C1
осталось 40.

23.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ШАГ 7 ИЗ 7
Клетка C1–S4: перевозим 40 тыс. т
S1
C1
C2
C3
C4
остаток
7
5
4
S2
3
60
190
6
0
S3
8
4
6
130
90
S4*
0
9
0
2
5
0
150
0
50
0
40
0
5
остаток
0
0
Выбор клетки
Пропускаем C3–S3 (9): строка или столбец уже
вычеркнуты.
Настоящие тарифы закончились — остаток C1
уходит на фиктивную фабрику S4 (руда остаётся на
карьере).
Перевозка
0
40
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое —
вычеркнуто. S4* — фиктивная фабрика.
x = min(40; 40) = 40
C1 вывез всё, S4 заполнена — план готов.

24.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ОПОРНЫЙ ПЛАН
Опорный план: затраты 3190 тыс. руб.
S1
C1
C2
C3
C4
спрос
7
5
4
S2
3
60
190
6
250
S3
8
130
0
4
6
5
9
0
2
5
0
150
150
90
50
270
S4*
запас
40
170
0
150
Все карьеры вывезли руду, все фабрики
загружены — суммы по строкам и столбцам
сходятся.
190
Занятых клеток 7 = m + n − 1 = 4 + 4 − 1 = 7 —
план невырожденный.
200
40
Проверки
Стоимость
8·130 + 0·40 + 5·60 + 6·90 + 4·190 + 2·150 +
5·50
= 3190 тыс. руб. в месяц
Это только стартовый план. Оптимален ли он —
проверяем методом потенциалов.

25.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ПОТЕНЦИАЛЫ
Одна оценка отрицательная — план можно улучшить
S1
C1
C2
C3
C4
7
S2
3
Δ=0
5
4
60
190
6
S3
8
Δ = −2
4
6
Δ=1
5
90
9
Δ=3
2
130
0
запас
40
170
u1 = 0
Δ=2
150
u2 = −2
C1S3: v3 = 8; C1S4: v4 = 0; C2S3: u2 = 6 − 8 =
−2; C2S1: v1 = 7; C3S1: u3 = −3; C4S3: u4 = −3;
C4S2: v2 = 5.
Δ=3
190
u3 = −3
Оценки свободных клеток
u4 = −3
Δij = cij − (ui + vj). Например, C2S2: 4 − (−2 +
5) = 1.
0
0
Δ=4
5
S4*
50
0
200
u
Потенциалы
Для занятых клеток: ui + vj = cij; u1 = 0.
Δ=2
150
спрос
250
150
270
40
Δ(C1S2) = 3 − (0 + 5) = −2 < 0
v
v1 = 7
v2 = 5
v3 = 8
v4 = 0
Остальные Δ ≥ 0. Перевозка по C1S2 снизит
затраты на 2 за каждую тысячу тонн.
Δ=3

26.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ЦИКЛ
Переносим 130 тыс. т по циклу — затраты 2930
S1
C1
C2
C3
C4
спрос
7
5
4
S2
+ 8
3
60
190
6
4
250
6
5
2
S3
130
90
9
150
150
− 5
− 0
S4*
запас
40
170
0
0
50
270
+ 0
40
Цикл
C1S2 (+) → C1S3 (−) → C4S3 (+) → C4S2 (−) →
назад.
150
θ = минимум среди клеток с «−»: min(130;
150) = 130.
190
Новые перевозки
200
C1S2: 0 + 130 = 130; C1S3: 130 − 130 = 0
(выходит);
C4S3: 50 + 130 = 180; C4S2: 150 − 130 = 20.
Затраты: 3190 − 2 · 130 = 2930
Смысл: C1 везёт руду на S2 по 3 вместо S3 по 8;
C4 уступает ему S2 и догружает S3.

27.

ЗАДАНИЕ 2 · НАИМЕНЬШИЙ ТАРИФ · ОПТИМУМ
Оптимальный план: 2930 тыс. руб. за одну итерацию
S1
C1
C2
C3
C4
7
S2
3
Δ=2
5
4
60
190
6
130
4
S3
8
Δ=2
6
Δ=1
5
90
9
Δ=3
2
0
запас
40
170
u1 = 0
Δ=0
150
u2 = 0
Все Δ ≥ 0 → план оптимален. Δ(C2S4) = 0 —
оптимальный план не единственный.
Δ=1
190
u3 = −1
Ответ словами
u4 = −1
C1 → S2: 130; C2 → S1: 60, C2 → S3: 90; C3 →
S1: 190; C4 → S2: 20, C4 → S3: 180.
0
0
Δ=4
5
S4*
180
0
Δ=2
20
спрос
250
150
270
40
v
v1 = 5
v2 = 3
v3 = 6
v4 = 0
Δ=1
200
u
Проверка
Новые потенциалы: u = (0; 0; −1; −1), v = (5;
3; 6; 0).
На карьере C1 остаётся 40 тыс. т.
Минимальные затраты 2930 тыс. руб.
(опорный план — 3190).

28.

ЗАДАНИЕ 2 · МЕТОД ФОГЕЛЯ
Как работает метод Фогеля (метод штрафов)
Алгоритм
Зачем штраф
1. Для каждой строки и каждого столбца — штраф: разность двух
наименьших тарифов (среди ещё не вычеркнутых клеток).
Штраф — цена ошибки: сколько мы
переплатим, если эту строку не загрузим
по её самому дешёвому маршруту и
придётся брать следующий.
2. Среди всех строк и всех столбцов сразу выбираем одну линию с
наибольшим штрафом.
3. В этой линии — клетку с наименьшим тарифом (штрафы других
линий уже не смотрим); ставим туда максимум возможного:
min(остаток поставщика; остаток потребителя).
4. Вычёркиваем исчерпанную строку или столбец.
5. Пересчитываем штрафы и повторяем, пока не распределим всё.
Фиктивная S4 — обычный столбец с нулевыми тарифами: её
нули участвуют в штрафах наравне с другими.
При равных штрафах берём линию, где наименьший тариф меньше; если и
он равен — первую по порядку (сначала строки, сверху вниз).
Поэтому сначала обслуживаем линии,
где ошибка дороже всего.
Фогель обычно даёт план ближе к оптимуму,
чем северо-западный угол и наименьший
тариф. Но опорный план всё равно
проверяем потенциалами.

29.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШТРАФЫ
Откуда берутся штрафы: первый шаг целиком
Строка
Тарифы
Два наименьших
Штраф
C1
7, 3, 8, 0
0и3
3−0=3
C2
5, 4, 6, 0
0и4
4−0=4
C3
4, 5, 9, 0
0и4
4−0=4
C4
6, 2, 5, 0
0и2
2−0=2
Столбе
ц
Тарифы
Два наименьших
Штраф
S1
7, 5, 4, 6
4и5
5−4=1
S2
3, 4, 5, 2
2и3
3−2=1
S3
8, 6, 9, 5
5и6
6−5=1
S4*
0, 0, 0, 0
0и0
0−0=0
Как считаем
Штраф линии = разность двух наименьших тарифов в ней (среди ещё не вычеркнутых клеток).
Нули фиктивной фабрики S4 тоже участвуют: поэтому у строк на первом шаге штрафы большие, а у столбца S4 штраф
0 — все его тарифы равны.
Наибольший штраф — 4, у строк C2 и C3. Наименьший тариф в обеих — 0, поэтому берём верхнюю, C2.
В строке C2 самый дешёвый тариф — 0 (C2–S4): x = min(150; 40) = 40.
Смысл: если C2 не загрузить по самому дешёвому маршруту, каждая тысяча тонн обойдётся минимум на 4 дороже.

30.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 1 ИЗ 7
Клетка C2–S4: перевозим 40 тыс. т
S1
C1
C2
C3
C4
7
S2
3
5
S3
8
4
S4*
0
6
0
4
5
9
0
6
2
5
0
остаток
250
150
270
40
штраф
1
1
1
0
остаток
штраф
170
3
150
4
190
4
200
2
Штрафы
Строки: C1: 3, C2: 4, C3: 4, C4: 2.
Столбцы: S1: 1, S2: 1, S3: 1, S4: 0.
Наибольший штраф — 4: строка C2 (такой
же штраф у C3; наименьший тариф там
тоже 0 — берём первую по порядку:
сначала строки, сверху вниз).
Штраф = разность двух наименьших тарифов
линии; расчёт каждого — на предыдущем
слайде.
Перевозка
Наименьший тариф в выбранной линии — 0
(C2–S4).
x = min(150; 40) = 40
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.
S4 заполнена — вычёркиваем столбец S4; у
C2 осталось 110.

31.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 2 ИЗ 7
Клетка C1–S2: перевозим 150 тыс. т
S1
C1
C2
C3
C4
7
S2
3
5
S3
8
4
S4*
0
6
0
4
5
9
0
6
2
5
0
40
остаток
штраф
Штрафы
170
4
110
1
190
1
Перевозка
3
Наименьший тариф в выбранной линии — 3
(C1–S2).
200
Строки: C1: 4, C2: 1, C3: 1, C4: 3.
Столбцы: S1: 1, S2: 1, S3: 1.
Наибольший штраф — 4: строка C1.
x = min(170; 150) = 150
остаток
250
150
270
штраф
1
1
1
0
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.
S2 заполнена — вычёркиваем столбец S2; у
C1 осталось 20.

32.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 3 ИЗ 7
Клетка C3–S1: перевозим 190 тыс. т
S1
C1
C2
C3
C4
7
S2
3
5
150
4
S3
8
S4*
0
6
0
4
5
9
0
6
2
5
0
40
остаток
штраф
Штрафы
20
1
110
1
190
5
Перевозка
1
Наименьший тариф в выбранной линии — 4
(C3–S1).
200
Строки: C1: 1, C2: 1, C3: 5, C4: 1.
Столбцы: S1: 1, S3: 1.
Наибольший штраф — 5: строка C3.
x = min(190; 250) = 190
остаток
250
штраф
1
0
270
0
1
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.
C3 вывез всё — вычёркиваем строку C3.

33.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 4 ИЗ 7
Клетка C2–S1: перевозим 60 тыс. т
S1
C1
C2
C3
C4
7
3
5
4
S2
150
4
190
6
остаток
60
штраф
1
S3
8
S4*
0
6
0
5
9
0
2
5
0
0
270
40
остаток
штраф
20
1
110
1
0
200
1
0
1
Штрафы
Строки: C1: 1, C2: 1, C4: 1.
Столбцы: S1: 1, S3: 1.
Наибольший штраф — 1: строка C2 (такой
же штраф у C1, C4, S1, S3; наименьший
тариф 5 ещё у C4, S1, S3 — берём первую
по порядку: сначала строки, сверху вниз).
Перевозка
Наименьший тариф в выбранной линии — 5
(C2–S1).
x = min(110; 60) = 60
S1 заполнена — вычёркиваем столбец S1; у
C2 осталось 50.
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.

34.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 5 ИЗ 7
Клетка C1–S3: перевозим 20 тыс. т
S1
C1
C2
C3
C4
остаток
штраф
7
5
4
S2
3
60
190
6
150
4
S3
8
S4*
0
6
0
5
9
0
2
5
0
40
остаток
штраф
20
8
50
6
Штрафы
Строки: C1: 8, C2: 6, C4: 5.
Столбцы: S3: 1.
Наибольший штраф — 8: строка C1.
0
Перевозка
200
Наименьший тариф в выбранной линии — 8
(C1–S3).
5
x = min(20; 270) = 20
0
0
270
0
1
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.
C1 вывез всё — вычёркиваем строку C1.

35.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 6 ИЗ 7
Клетка C2–S3: перевозим 50 тыс. т
S1
C1
C2
C3
C4
остаток
штраф
7
5
4
S2
3
60
190
6
150
4
S3
8
20
6
S4*
0
0
5
9
0
2
5
0
остаток
штраф
Штрафы
0
40
50
6
Строки: C2: 6, C4: 5.
Столбцы: S3: 1.
Наибольший штраф — 6: строка C2.
0
Перевозка
200
Наименьший тариф в выбранной линии — 6
(C2–S3).
5
x = min(50; 250) = 50
0
0
250
0
1
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.
C2 вывез всё — вычёркиваем строку C2.

36.

ЗАДАНИЕ 2 · ФОГЕЛЬ · ШАГ 7 ИЗ 7
Клетка C4–S3: перевозим 200 тыс. т
S1
C1
C2
C3
C4
остаток
штраф
7
5
4
S2
3
60
190
6
0
150
4
S3
8
6
20
50
S4*
0
0
5
9
0
2
5
0
0
200
остаток
штраф
Штрафы
0
40
Строки: C4: 5.
Столбцы: S3: 5.
0
Наибольший штраф — 5: строка C4 (такой
же штраф у S3; наименьший тариф там
тоже 5 — берём первую по порядку:
сначала строки, сверху вниз).
0
200
5
0
5
Перевозка
Наименьший тариф в выбранной линии — 5
(C4–S3).
x = min(200; 200) = 200
C4 вывез всё — вычёркиваем строку C4.
Осталась одна клетка — штраф считать не
нужно.
Тариф — маленькое число в углу клетки, перевозка — крупное. Серое — вычеркнуто. S4* —
фиктивная фабрика.

37.

ЗАДАНИЕ 2 · ОПОРНЫЙ ПЛАН ФОГЕЛЯ
Опорный план: затраты 2970 тыс. руб.
S1
C1
C2
C3
C4
спрос
7
5
4
S2
3
60
190
6
250
150
S3
8
20
S4*
0
4
6
5
9
0
2
5
0
150
50
200
270
0
запас
170
40
150
Все карьеры вывезли руду, все фабрики
загружены — суммы по строкам и столбцам
сходятся.
190
Занятых клеток 7 = m + n − 1 = 4 + 4 − 1 = 7 —
план невырожденный.
200
40
Проверки
Стоимость
3·150 + 8·20 + 5·60 + 6·50 + 0·40 + 4·190 +
5·200
= 2970 тыс. руб. в месяц
Вопрос задания — опорный план Фогеля. Но
«минимальные издержки» нужно проверить методом
потенциалов — делаем это дальше.

38.

ЗАДАНИЕ 2 · ПРОВЕРКА ПОТЕНЦИАЛАМИ
Одна оценка отрицательная — план можно улучшить
S1
C1
C2
C3
C4
7
S2
3
Δ=0
5
4
60
190
6
150
4
S3
8
6
Δ=3
5
20
50
9
Δ=5
2
запас
Δ = −2
170
u1 = 0
40
150
u2 = −2
C1S2: v2 = 3; C1S3: v3 = 8; C2S3: u2 = −2; C2S1:
v1 = 7; C2S4: v4 = 2; C3S1: u3 = −3; C4S3: u4 =
−3.
Δ=1
190
u3 = −3
Оценки свободных клеток
0
0
0
Δ=4
5
S4*
0
Δ=2
Δ=2
200
спрос
250
150
270
40
v
v1 = 7
v2 = 3
v3 = 8
v4 = 2
Δ=1
200
u
Потенциалы
u4 = −3
Для занятых клеток: ui + vj = cij; u1 = 0.
Δij = cij − (ui + vj).
Δ(C1S4) = 0 − (0 + 2) = −2 < 0
Остальные Δ ≥ 0. Значит, перевозка в C1S4
снизит затраты на 2 за каждую тысячу тонн.

39.

ЗАДАНИЕ 2 · ЦИКЛ ПЕРЕСЧЁТА
Переносим 20 тыс. т по циклу — затраты 2930
S1
C1
C2
C3
C4
спрос
7
5
4
S2
3
60
190
6
150
4
8
6
5
20
50
9
2
250
S3
5
150
S4*
− 0
+ 0
+
40
0
200
270
запас
0
40
−
170
Цикл
C1S4 (+) → C2S4 (−) → C2S3 (+) → C1S3 (−) →
назад.
150
θ = минимум среди клеток с «−»: min(40; 20)
= 20.
190
Новые перевозки
200
C1S4: 0 + 20 = 20; C2S4: 40 − 20 = 20;
C2S3: 50 + 20 = 70; C1S3: 20 − 20 = 0
(выходит).
Затраты: 2970 − 2 · 20 = 2930
Смысл: C1 перестаёт возить на S3 по 8 и
оставляет 20 тыс. т у себя; S3 получает их с C2
по 6, а C2 меньше оставляет на месте.

40.

ЗАДАНИЕ 2 · ОТВЕТ
Оптимальный план: 2930 тыс. руб. в месяц
S1
C1
C2
C3
C4
7
S2
3
Δ=2
5
4
60
190
6
150
4
S3
8
Δ=2
6
Δ=1
5
0
70
9
Δ=3
2
0
запас
20
170
u1 = 0
20
150
u2 = 0
Все Δ ≥ 0 → план оптимален (Δ = 0 в C4S2 —
есть альтернативный оптимум).
Δ=1
190
u3 = −1
Ответ словами
u4 = −1
C1 → S2: 150; C2 → S1: 60, C2 → S3: 70; C3 →
S1: 190; C4 → S3: 200.
0
Δ=4
5
S4*
0
Δ=2
Δ=0
200
спрос
250
150
270
40
v
v1 = 5
v2 = 3
v3 = 6
v4 = 0
Δ=1
200
u
Проверка
Новые потенциалы: u = (0; 0; −1; −1), v = (5;
3; 6; 0).
Недогружены: C1 и C2 — по 20 тыс. т
остаются на карьерах.
Минимальные затраты 2930 тыс. руб.
(опорный план Фогеля — 2970).

41.

ЗАДАНИЕ 2 · СРАВНЕНИЕ
Наименьший тариф или метод Фогеля?
Наименьший тариф
Метод Фогеля
3190
2970
Итераций метода потенциалов
1
1
Минимальные затраты, тыс. руб.
2930
2930
C4 → S2: 20; на C1 остаётся 40
C4 → S3: 200; на C1 и C2 — по 20
Опорный план, тыс. руб.
Оптимальный план
Выводы
Оба способа приводят к одним и тем же минимальным затратам 2930: опорный план — только старт.
Фогель стартует на 220 тыс. руб. ближе к оптимуму: штраф учитывает, сколько потеряем, если не возьмём дешёвый
маршрут.
Оптимальные планы разные, затраты одинаковые: Δ = 0 в свободной клетке — оптимум не единственный.
На экзамене опорный план строим тем методом, который указан в задании (здесь — Фогель).

42.

ЗАДАНИЕ 3 · НАЗНАЧЕНИЯ
Две работы, три рабочих: балансируем матрицу
Имеются две работы r1, r2 и трое рабочих L1, L2, L3; каждый может выполнить любую работу. aij — время рабочего i
на работу j. Решите задачу о назначениях. Чему равно минимальное время выполнения двух работ?
r1
r2
r1
r2
r3*
L1
5
6
L1
5
6
0
L2
2
3
L2
2
3
0
L3
4
7
L3
4
7
0
Шаг 0. Квадратная матрица
Рабочих 3, работ 2 → добавляем фиктивную работу r3 с нулевым
временем.
Рабочий, получивший r3, на деле остаётся без работы.
Где посмотреть: семинар 3, часть 2 (венгерский алгоритм); лекция 5, сл. 29–34; ДЗ 2, задачи 3–5.
Венгерский метод (min)
1. Вычесть минимум каждой строки.
2. Вычесть минимум каждого столбца.
3. Покрыть нули минимумом линий. Линий
= n → назначение по нулям.
4. Иначе: минимум непокрытых вычесть
из непокрытых, прибавить к пересечениям
линий; к шагу 3.
Задача на max: сначала заменить aij на (max −
aij).

43.

ЗАДАНИЕ 3 · РЕШЕНИЕ
Редукция, линии и назначение
шаг 2
r1
r2
r3
шаг 4
r1
r2
r3
L1
3
3
0
L1
1
1
0
Ответ
L2
0
0
0
L2
0
0
2
L3
2
4
0
L3
0
2
0
L3 → r1 (4), L2 → r2 (3), L1 → r3* —
без работы.
Шаг 1 (строки): минимумы строк — 0 (столбец
r3), матрица не меняется.
Шаг 2 (столбцы): вычли 2 из r1, 3 из r2.
Линии: строка L2 и столбец r3 (подсвечены) —
2 < 3.
Минимум непокрытых чисел (3, 3, 2, 4) — 2:
вычли из непокрытых, прибавили к
пересечению (L2, r3).
Теперь независимых нулей 3 (оранжевые).
Почему нельзя «каждой работе — самого быстрого»
Самый быстрый на обеих работах — L2 (2 и 3), но он один. Жадный выбор «L2
на r1» даёт 2 + 6 = 8 или 2 + 7 = 9, а оптимум — отдать L2 работу r2, где разрыв
с другими больше.
Минимальное время: 4 + 3
=7
Проверка перебором
Пар «кто r1, кто r2» всего 6: L1L2 = 8,
L2L1 = 8, L1L3 = 12, L3L1 = 10, L2L3 =
9, L3L2 = 7.
Минимум 7 — совпало.

44.

ТЕМА 4
Целочисленное программирование
Метод Гомори: дробные части и отсечение
Задание 4 из примера

45.

ТЕМА 4 · АЛГОРИТМ ГОМОРИ
Алгоритм — коротко
1. ЛП без
целочисленности
Решаем симплекс-методом как
обычную задачу ЛП.
Если все базисные переменные
целые — готово.
2. Отсечение
Берём строку с наибольшей
дробной частью свободного
члена bi.
Дробные части коэффициентов
при свободных переменных:
Σ{aij}xj ≥ {bi}.
3. Двойственный
симплекс
Отсечение в канонической
форме — новая строка с
отрицательным b.
Ведущая строка — отсечение;
столбец — min Δj / |aj| при aj < 0.
Повторяем с шага 1.
Дробная часть. {a} = a − [a], где [a] — наибольшее целое, не превосходящее a. Всегда 0 ≤ {a} < 1. Для отрицательных:
{−1/2} = −1/2 − (−1) = 1/2; {−8/5} = −8/5 − (−2) = 2/5.
Где посмотреть: Семинар_4_НОВЫЙ_целочисленное_программирование.pptx; лекция 6; ДЗ 3 (фермер: (2; 7), F = 25).

46.

ЗАДАНИЕ 4 · УСЛОВИЕ
Найдено оптимальное нецелочисленное решение
БП
x1
x2
x3
x4
x5
b
Fmax
0
0
1
0
4/5
364/5
x1
1
0
1/2
0
−8/5
72/5
x4
0
0
−1/2
1
8/5
28/5
x2
0
1
0
0
1
11
Что требуется
Описать поиск уравнения отсечения по
Гомори, записать его в каноническом виде и
показать симплекс-таблицу с отсечением.
Решение не проводить!
Сначала — что видим в таблице
Базис: x1 = 72/5 = 14,4; x4 = 28/5 = 5,6; x2 = 11.
Свободные (небазисные) переменные: x3, x5 — в строках у них стоят «рабочие» коэффициенты.
Все оценки в строке F ≥ 0 → решение оптимально для ЛП, но x1 и x4 дробные → нужно отсечение.
Оптимальность уже есть, поэтому сразу переходим к шагу 2 алгоритма.

47.

ЗАДАНИЕ 4 · ШАГ 1
Выбираем строку: наибольшая дробная часть b
Строка
b
[b]
{b} = b − [b]
x1
72/5 = 14,4
14
2/5 = 0,4
Вывод
x4
28/5 = 5,6
5
3/5 = 0,6
Наибольшая дробная часть 3/5 — у x4
x2
11
11
0
Отсечение строим по строке x4.
Строка x4 как уравнение
x4 − 1/2 x3 + 8/5 x5 = 28/5
В уравнение входят только базисная x4 и свободные x3, x5 (коэффициенты при x1, x2 — нули).
Если у двух строк одинаковая наибольшая дробная часть — можно взять любую.

48.

ЗАДАНИЕ 4 · ШАГ 2
Уравнение отсечения и канонический вид
Коэффициент в строке x4
x3: −1/2
x5: 8/5
b: 28/5
Целая часть [a]
−1
1
5
Дробная часть {a}
−1/2 − (−1) = 1/2
8/5 − 1 = 3/5
28/5 − 5 = 3/5
Отсечение
Смысл
Σ {aj} xj ≥ {b}:
Отсечение отрезает текущую дробную вершину (при
x3 = x5 = 0 получаем 0 ≥ 3/5 — неверно), но не
отрезает ни одной целой точки.
1/2 x3 + 3/5 x5 ≥ 3/5
Канонический вид — вводим новую переменную x6 ≥ 0
и умножаем на −1:
−1/2 x3 − 3/5 x5 + x6 = −3/5
x6 — новая базисная переменная, x6 = −3/5 < 0: план
недопустим → дальше двойственный симплексметод.

49.

ЗАДАНИЕ 4 · ШАГ 3
Симплекс-таблица с уравнением отсечения
БП
x1
x2
x3
x4
x5
x6
b
Fmax
0
0
1
0
4/5
0
364/5
x1
1
0
1/2
0
−8/5
0
72/5
x4
0
0
−1/2
1
8/5
0
28/5
x2
0
1
0
0
1
0
11
x6
0
0
−1/2
0
−3/5
1
−3/5
Общий вид таблицы
Добавили столбец x6 (у старых строк — нули) и строку отсечения x6 — последней строкой таблицы.
В строке F под x6 — 0. Значение F не меняется: 364/5.
Так выглядит ответ на задание 4. Решение (двойственный симплекс) по условию не проводим — оно доведено до
конца в разделе «Повышенная сложность».

50.

ТЕМА 5
Нелинейное программирование
Метод множителей Лагранжа на простейших примерах

51.

ТЕМА 5 · МЕТОД ЛАГРАНЖА
Условный экстремум: ограничения-равенства
Когда применяем
Алгоритм
Целевая функция нелинейная (есть x², xy, …),
ограничения — равенства gi(x) = bi.
1. Функция Лагранжа:
L = f(x1, x2) + λ·(g(x1, x2) − b)
Типичный сюжет: распределить заданный объём
(5000 кг, 200 машин) между способами, у которых
затраты растут быстрее, чем объём.
2. Частные производные по x1, x2, λ приравниваем к
нулю:
Линейную задачу так решать нельзя — производные
постоянны, система не имеет смысла.
(последнее — это само ограничение).
∂L/∂x1 = 0, ∂L/∂x2 = 0, ∂L/∂λ = 0
3. Решаем систему → точка (x1; x2) и λ.
4. Проверяем характер экстремума: сдвигаем x1 на ±1
вдоль ограничения и сравниваем f.
Где посмотреть: лекция 9, сл. 17–23; ДЗ 5 (метод Лагранжа).

52.

ТЕМА 5 · ПРИМЕР ЛЕКЦИИ
Мука: магазин и торговые агенты
Комбинат продаёт муку в розницу через магазин и оптом через агентов. Продажа x1 кг через магазин стоит x1² ден.
ед., через агентов x2 кг — x2² ден. ед. В сутки продают 5000 кг. Как распределить, чтобы затраты были
минимальными?
Модель и функция Лагранжа
Решение
f = x1² + x2² → min
∂L/∂x1 = 2x1 + λ = 0
∂L/∂x2 = 2x2 + λ = 0
∂L/∂λ = x1 + x2 − 5000 = 0
x1 + x2 = 5000
L = x1² + x2² + λ(x1 + x2 − 5000)
x1, x2 — кг муки через магазин и через агентов.
Из первых двух: x1 = x2 = −λ/2 → 2x1 = 5000.
x1 = x2 = 2500 кг; λ = −5000; f = 12 500 000
Проверка: x1 = 2501, x2 = 2499 → f = 12 500 002 > 12 500 000
— это минимум.

53.

ТЕМА 5 · ДЗ 5
Автомобили: розница и опт
Фирма продаёт автомобили в розницу и оптом. Продажа x1 машин в розницу стоит 4x1 + x1² р., x2 машин оптом —
x2² р. Всего нужно продать 200 машин. Найти способ, минимизирующий расходы.
Модель
Решение системы
f = 4x1 + x1² + x2² → min
Из первых двух: 4 + 2x1 = 2x2 → x2 = x1 + 2.
x1 + x2 = 200; x1, x2 ≥ 0
Подставим: x1 + x1 + 2 = 200 → x1 = 99.
L = 4x1 + x1² + x2² + λ(x1 + x2 − 200)
x1 = 99, x2 = 101, λ = −202
∂L/∂x1 = 4 + 2x1 + λ = 0
∂L/∂x2 = 2x2 + λ = 0
∂L/∂λ = x1 + x2 − 200 = 0
f = 4·99 + 99² + 101² = 20 398 р.
Проверка: x1 = 98 → f = 20 400; x1 = 100 → f = 20 400.
Оба больше → минимум.
Оптом продаём на 2 машины больше: розница дороже на 4
р. за машину.

54.

ТЕМА 6
Динамическое программирование
Только задачи семинаров
Задание 7 из примера: автолавки

55.

ТЕМА 6 · ДП
Три типа задач, которые были на семинарах
Распределение ресурса
Замена оборудования
Кратчайший путь
Деньги, машины, предприятия
делим между объектами.
Каждый год: сохранить или
заменить.
Сетка: двигаемся только на
восток или на север.
Этап — объект; состояние —
сколько ресурса осталось.
Этап — год; состояние — возраст
t.
Этап — шаг; состояние — узел.
fk(c) = max [gk(x) + fk−1(c − x)]
fk(t) = max {r(t) + fk−1(t+1); s(t) − P +
r(0) + fk−1(1)}
Семинар 5; ДЗ 4, задачи 1–2; задание
7.
f(узел) = min [ci + f(следующий)]
Семинар 6; ДЗ 4, задача 4 (35).
Семинар 6; лекция 8; ДЗ 4, задача 3.
Общая схема. Прямой (или обратный) ход по этапам — таблица условных оптимумов; затем обратный ход —
восстанавливаем, какое решение дало оптимум на каждом этапе.
Где посмотреть: Семинар_5_НОВЫЙ_динамическое_программирование.pptx; Семинар_6_НОВЫЙ_динамическое_программирование_2.pptx.

56.

ЗАДАНИЕ 7 · УСЛОВИЕ
5 автолавок, 3 населённых пункта
Торговая фирма направляет 5 автолавок в 3 населённых пункта. Товарооборот (тыс. руб.) зависит только от числа
машин в пункте. Найти распределение, максимизирующее общий товарооборот.
Машин x
0
1
2
3
4
5
g1(x) — пункт 1
0
1
3
7
9
10
Постановка ДП
g2(x) — пункт 2
0
2
5
6
8
12
Этап k — добавляем пункт k (k = 1, 2, 3).
g3(x) — пункт 3
0
5
6
7
9
11
Состояние c — сколько машин распределяем
между пунктами 1…k.
В условии таблица дана для 1–5 машин; 0 машин — товарооборот 0.
Управление x — сколько машин даём пункту
k.
f1(c) = g1(c)
fk(c) = max [gk(x) + fk−1(c − x)], 0 ≤ x ≤ c
Нулевой столбец (0 машин → 0) добавили сами:
пункт можно не обслуживать.

57.

ЗАДАНИЕ 7 · ЭТАП 2
Пункты 1 и 2: f2(c) = max [g2(x) + f1(c − x)]
c \ x2
0
1
2
3
4
0
0+0=0
1
0+1=1
2+0=2
2
0+3=3
2+1=3
5+0=5
3
0+7=7
2+3=5
5+1=6
6+0=6
4
0+9=9
2+7=9
5+3=8
6+1=7
8+0=8
5
0 + 10 = 10
2 + 9 = 11
5 + 7 = 12
6+3=9
8+1=9
5
12 + 0 = 12
Как читать
Строка c: делим c машин — x2 во второй пункт, c − x2 в первый (по f1 = g1).
Например, c = 4: 0 + 9, 2 + 7, 5 + 3, 6 + 1, 8 + 0 → максимум 9 при x2 = 0 или x2 = 1.
Этап 1 тривиален: f1(c) = g1(c) = 0, 1, 3, 7, 9, 10.
f2(c)
x2*
0
0
2
1
5
2
7
0
9
0, 1
12
2, 5

58.

ЗАДАНИЕ 7 · ЭТАП 3 И ОТВЕТ
Добавляем пункт 3 — и обратный ход
x3
g3(x3) + f2(5 − x3)
0
1
2
3
4
5
0 + 12 = 12
5 + 9 = 14
6 + 7 = 13
7 + 5 = 12
9 + 2 = 11
11 + 0 = 11
Обратный ход
Ответ
f3(5) = 14 при x3 = 1 → пункту 3 — 1 машина.
(3; 1; 1): 7 + 2 + 5 = 14
Остаётся 4 машины: f2(4) = 9 при x2 = 0 или x2 = 1.
(4; 0; 1): 9 + 0 + 5 = 14
x2 = 0 → пункту 1: 4 машины; x2 = 1 → пункту 1: 3
машины.
Два оптимальных плана — это нормально, назвать оба.
Максимальный товарооборот — 14 тыс. руб.
Проверка перебором всех 21 распределений пяти машин —
максимум 14 ровно в этих двух планах.

59.

ТЕМА 7
Системы массового обслуживания
Колмогоров → гибель и размножение → 1 и n каналов
отказы, очередь ограниченная и неограниченная
Задания 5 и 6 из примера

60.

ТЕМА 7 · ОСНОВНЫЕ ПОНЯТИЯ
Что нужно знать о любой СМО
Показатель
Обозначения
Pотк
Смысл
доля заявок, получивших отказ
λ — интенсивность входящего потока (заявок в единицу
времени).
Q = 1 − Pотк
доля обслуженных заявок
tобс — среднее время обслуживания; μ = 1 / tобс —
заявок, которые один канал обслуживает за единицу
времени.
A=λ·Q
обслужено в единицу времени
k̄
среднее число занятых каналов
ρ = λ / μ — нагрузка (λ и μ — в одних единицах!).
Lоч, Lсист
заявок в очереди / в системе
n — число каналов; m — число мест в очереди.
Tоч, Tсист
время в очереди / в системе
pk — финальная (предельная) вероятность состояния:
доля времени, когда в системе k заявок.
Формулы Литтла
Tоч = Lоч / λ; Tсист = Lсист / λ
Для систем с отказами вместо λ берут A = λQ.
Где посмотреть: лекции 10, 11, 11-2; Семинар_7_НОВЫЙ_СМО_часть_1.pptx, Семинар_8_НОВЫЙ_СМО_часть_2.pptx.

61.

ТЕМА 7 · УРАВНЕНИЯ КОЛМОГОРОВА
Граф состояний → система уравнений
Дифференциальные уравнения
Как составлять (правило семинара 7)
Для каждого состояния Si:
1. Для каждого состояния — одно уравнение.
dpi/dt = Σ λji pj − pi · Σ λij
2. Слева — вероятность этого состояния, умноженная
на сумму всех стрелок, которые из него выходят.
«входящие стрелки × вероятность их начала» минус
«вероятность Si × сумма исходящих стрелок».
Финальные вероятности
При t → ∞ вероятности не меняются: dpi/dt = 0.
выход = вход: pi · Σ λij = Σ λji pj
Плюс условие нормировки p1 + p2 + … = 1.
3. Справа — сумма по входящим стрелкам:
интенсивность стрелки × вероятность состояния, из
которого она выходит.
4. Одно уравнение (любое) заменяем нормировкой —
система из n уравнений с n неизвестными.
Одно уравнение из системы «выход = вход» всегда лишнее
— оно следует из остальных.

62.

ЗАДАНИЕ 5 · ГРАФ
Три состояния, шесть переходов
S2
0,1
0,6
0,4
λ
S1 → S2
0,1
Задание
S 2 → S1
0,4
S1 → S3
0,2
S3 → S1
0,3
а) составить
систему
уравнений
Колмогорова;
S 2 → S3
0,6
S3 → S2
0,5
0,5
0,2
S1
Переход
0,3
S3
Чтение графа: у пары стрелок каждая
подписана своим числом; стрелка — из
состояния, откуда выходит. Числа
взяты с графа из примера (проверьте
по оригиналу).
б) найти
предельное
распределение
вероятностей.
Все потоки
простейшие.

63.

ЗАДАНИЕ 5 · УРАВНЕНИЯ
а) Система уравнений Колмогорова
Дифференциальные
Для финальных вероятностей (dp/dt = 0)
dp1/dt = 0,4p2 + 0,3p3 − (0,1 + 0,2)p1
S1: 0,3p1 = 0,4p2 + 0,3p3
dp2/dt = 0,1p1 + 0,5p3 − (0,4 + 0,6)p2
S2: 1,0p2 = 0,1p1 + 0,5p3
dp3/dt = 0,2p1 + 0,6p2 − (0,3 + 0,5)p3
S3: 0,8p3 = 0,2p1 + 0,6p2
Первое слагаемое — вход в состояние, вычитаемое —
выход из него.
p1 + p2 + p3 = 1
Слева — выход: для S1 это 0,1 + 0,2 = 0,3; для S2 — 0,4 + 0,6
= 1,0; для S3 — 0,3 + 0,5 = 0,8.

64.

ЗАДАНИЕ 5 · РЕШЕНИЕ
б) Предельное распределение вероятностей
Решаем
Ответ
Из S2: p2 = 0,1p1 + 0,5p3.
p1 = 1 / 1,88 = 25/47 ≈ 0,532
Подставим в S1: 0,3p1 = 0,04p1 + 0,2p3 + 0,3p3
→ 0,26p1 = 0,5p3 → p3 = 0,52p1.
p2 = 0,36p1 = 9/47 ≈ 0,191
Тогда p2 = 0,1p1 + 0,26p1 = 0,36p1.
Нормировка: p1(1 + 0,36 + 0,52) = 1,88p1 = 1.
Уравнение S3 не использовали — им проверим ответ.
p3 = 0,52p1 = 13/47 ≈ 0,277
Смысл: около 53 % времени система в S1, 19 % — в
S2, 28 % — в S3.
Проверка S3: 0,8 · 13/47 = 10,4/47; 0,2 · 25/47 + 0,6 · 9/47
= (5 + 5,4)/47 = 10,4/47 — верно.

65.

ТЕМА 7 · ГИБЕЛЬ И РАЗМНОЖЕНИЕ
Цепочка состояний: формула вместо системы
λ0
S0
μ0
λ1
S1
μ1
λ2
S2
μ2
···
λn−1
μn−1
Sn
Формулы
Все СМО ниже — частные случаи
p0 = 1 / (1 + λ0/μ0 + λ0λ1/(μ0μ1) + …)
Каналы с отказами: λk = λ, μk = (k + 1)μ.
pk = (λ0 · … · λk−1)/(μ0 · … · μk−1) · p0
Очередь: после Sn стрелки вправо — λ, влево — nμ (все
каналы заняты).
Коэффициент при p0 — произведение стрелок «вправо» до
Sk, делённое на произведение стрелок «влево».
Ограниченная очередь — цепочка конечна;
неограниченная — бесконечна (нужно ρ/n < 1).
Семинар 7: кассы, кредитный отдел; семинар 8: формулы
Эрланга.

66.

ЗАДАНИЕ 6 · ОДНОКАНАЛЬНАЯ С ОТКАЗАМИ
Дежурный администратор: 90 звонков в час
Дежурному по администрации города звонки поступают с интенсивностью 90 в час, средняя продолжительность
разговора — 2 мин. Определить показатели дежурного как объекта СМО.
Решение
λ = 90
S0
S1
μ = 30
S0 — свободен, S1 — разговаривает (новый
звонок — отказ)
Один дежурный — один канал; занят → «занято», звонок теряется: СМО с
отказами.
μ = 60 / 2 = 30 звонков в час; ρ = 90 / 30 = 3
Pотк = 3 / (1 + 3) = 0,75
Формулы (n = 1)
Q = 1 / (1 + 3) = 0,25; A = 90 · 0,25 = 22,5 звонка в час
p0 = Q = 1 / (1 + ρ)
Дежурный занят 75 % времени (p1 = 0,75), но принимает лишь каждый
четвёртый звонок: 67,5 звонка в час теряются.
Pотк = p1 = ρ / (1 + ρ)
A = λQ
Если у дежурного 5 телефонов (вариант задачи на семинаре 8) — это СМО с отказами
на 5 каналов: Pотк ≈ 0,110 (формулы Эрланга, следующий слайд).

67.

ТЕМА 7 · МНОГОКАНАЛЬНАЯ С ОТКАЗАМИ
Формулы Эрланга: пять телефонов (лекция 10)
Формулы (n каналов)
Пример лекции 10, сл. 4 (семинар 8)
p0 = 1 / (1 + ρ + ρ²/2! + … + ρⁿ/n!)
У дежурного 5 телефонов; 90 звонков в час, разговор 2
мин.
pk = ρᵏ/k! · p0
Pотк = pn = ρⁿ/n! · p0
Q = 1 − Pотк; A = λQ; k̄ = ρQ
Слагаемые удобно считать цепочкой: каждое следующее =
предыдущее × ρ / k.
n = 1 даёт формулы предыдущего слайда.
μ = 30 в час; ρ = 90/30 = 3; n = 5
Слагаемые: 1; 3; 4,5; 4,5; 3,375; 2,025 → сумма 18,4.
p0 = 1/18,4 ≈ 0,0543
Pотк = 2,025 · 0,0543 ≈ 0,110
Q ≈ 0,89; A ≈ 80,1 в час; k̄ ≈ 2,67
С пятью телефонами теряется 11 % звонков, с одним
(задание 6) — 75 %. Для отказов ≤ 5 % нужно 7 телефонов.

68.

ТЕМА 7 · ОДИН КАНАЛ, ОЧЕРЕДЬ ≤ m
АЗС: одна колонка, ждать могут 3 машины (лекция 11-2)
Формулы
Решение
Состояния S0…Sm+1; pk = ρᵏ · p0.
Машины — каждые 2 мин: λ = 0,5 в мин; заправка 2,5 мин:
μ = 0,4 в мин; m = 3.
p0 = 1 / (1 + ρ + ρ² + … + ρ^(m+1)) = (1 − ρ) / (1 −
ρ^(m+2))
Pотк = pm+1 = ρ^(m+1) · p0
Q = 1 − Pотк; A = λQ
Lоч = 1·p2 + 2·p3 + … + m·pm+1
Lсист = Lоч + (1 − p0); T = L / λ
Отказ — когда колонка занята и все m мест в очереди заняты.
ρ = 0,5 / 0,4 = 1,25
1 + 1,25 + 1,25² + 1,25³ + 1,25⁴ = 1 + 1,25 + 1,5625 + 1,9531 +
2,4414 = 8,207
p0 = 1 / 8,207 ≈ 0,122
Pотк = 2,4414 · 0,122 ≈ 0,297
Q ≈ 0,703; A ≈ 0,351 машины в мин
Lоч ≈ 1,56; Tоч = Lоч / λ ≈ 3,12 мин
Почти 30 % машин уезжают — нужна вторая колонка или
площадка больше (вывод лекции).

69.

ТЕМА 7 · ОДИН КАНАЛ, ОЧЕРЕДЬ НЕ ОГРАНИЧЕНА
Билетная касса (лекция 11-2)
Формулы (нужно ρ < 1)
Решение
p0 = 1 − ρ; pk = ρᵏ(1 − ρ)
Один кассир обслуживает 2 покупателя в мин, приходят
90 в час.
Lоч = ρ² / (1 − ρ)
Lсист = ρ / (1 − ρ)
Tоч = Lоч / λ; Tсист = Lсист / λ
Pотк = 0; Q = 1; A = λ
При ρ ≥ 1 очередь растёт бесконечно — финальных
вероятностей нет.
λ = 90/60 = 1,5 в мин; μ = 2 в мин; ρ = 0,75
p0 = 0,25 — 25 % времени кассир свободен
Lоч = 0,75² / 0,25 = 2,25 человека
Lсист = 0,75 / 0,25 = 3 человека
Tсист = 3 / 1,5 = 2 мин; Tоч = 2,25 / 1,5 = 1,5 мин
A = λ = 1,5 покупателя в мин — обслуживаются все.

70.

ТЕМА 7 · n КАНАЛОВ, ОЧЕРЕДЬ НЕ ОГРАНИЧЕНА
Формулы (нужно ρ / n < 1)
(
p0 = 1 / 1 + ρ + … +
ρⁿ
ρⁿ⁺¹
+
n!
n!(n − ρ)
)
ρⁿ
n
Pож =
·
· p0
n!
n−ρ
Как запомнить
Начало суммы — как в Эрланге (1, ρ,
…, ρⁿ/n!).
Последнее слагаемое — «хвост»
очереди: геометрическая прогрессия
со знаменателем ρ/n.
Отказов нет: Pотк = 0, Q = 1, A = λ.
Lоч =
ρⁿ⁺¹ · p0
n · n! · (1 − ρ/n)²
Lсист = Lоч + ρ; T = L / λ
k̄ = ρ; Kз = ρ / n
Pож — вероятность, что все каналы заняты и пришедшей заявке придётся ждать.
Занято в среднем ρ каналов —
столько «работы» приходит.
Лекция 11-2, сл. 53–57.

71.

ТЕМА 7 · ПРИМЕР ЛЕКЦИИ
Супермаркет: сколько нужно кассиров?
К расчётному центру поступает 81 покупатель в час, обслуживание — 2 мин. Определить минимальное число
кассиров, при котором очередь не растёт до бесконечности, и характеристики при этом числе.
n
p0
Lоч
Tоч, мин
Решение при n = 3
3
0,025
7,35
5,45
λ = 81/60 = 1,35 в мин; ρ = λ · t = 2,7
4
0,057
0,81
0,6
5
0,065
0,2
0,15
Очередь конечна при ρ/n < 1 → n > 2,7 → nmin = 3.
Сумма: 1 + 2,7 + 3,645 + 3,2805 + 2,7⁴/(3!·0,3) = 10,625 +
29,524 = 40,149
p0 ≈ 0,0249
Lоч ≈ 7,35; Tоч ≈ 5,45 мин
Lсист ≈ 10,05; Tсист ≈ 7,45 мин; Kз = 0,9
Вывод
При трёх кассирах очередь ~7 человек и 5,5 мин
ожидания — перегрузка. Четвёртый кассир сокращает
ожидание в 9 раз.

72.

ТЕМА 7 · n КАНАЛОВ, ОЧЕРЕДЬ ≤ m
АЗС: 2 колонки, очередь до 3 машин (лекция 11-2)
Состояние
S0
S1
S2
S3
S4
S5
Формулы
коэф. при p0
1
1,155
0,667
0,385
0,222
0,128
Состояния S0…Sn — заняты k каналов; Sn+1…Sn+m — все
заняты, в очереди s заявок.
pk
0,281
0,325
0,187
0,108
0,063
0,036
pk = ρᵏ/k! · p0 (k ≤ n)
pn+s = ρⁿ/n! · (ρ/n)ˢ · p0 (s = 1…m)
p0 = 1 / [Σ ρᵏ/k! + ρⁿ/n! · Σ (ρ/n)ˢ]
Решение
Pотк = pn+m; Q = 1 − Pотк; A = λQ
λ = 2,1; t = 0,55 → μ = 1/0,55 ≈ 1,82; ρ = λ · t = 1,155; n = 2,
m = 3.
Lоч = Σ s · pn+s; k̄ = ρQ
ρ/n ≈ 0,58 < 1 — процесс стабилен.
p0 ≈ 0,281 — 28 % времени система простаивает
Pотк = p5 ≈ 0,036; Q ≈ 0,964; A ≈ 2,02
Ответ лекции (сл. 51–52): вероятность простоя 0,28.

73.

ТЕМА 7 · ШПАРГАЛКА
Какая СМО — какие формулы
Тип СМО
p0
Главный показатель
1 канал, отказы
1 / (1 + ρ)
Pотк = ρ / (1 + ρ)
n каналов, отказы
1 / Σ ρᵏ/k! (k = 0…n)
Pотк = ρⁿ/n! · p0
1 канал, очередь ≤ m
(1 − ρ) / (1 − ρ^(m+2))
Pотк = ρ^(m+1) p0; Lоч = Σ (k − 1)pk
1 канал, очередь ∞ (ρ < 1)
1−ρ
Lоч = ρ²/(1 − ρ); Lсист = ρ/(1 − ρ)
n каналов, очередь ∞ (ρ < n)
см. слайд выше
Lоч = ρⁿ⁺¹p0 / (n·n!(1 − ρ/n)²)
Σ ρᵏ/k! + ρⁿ/n! Σ(ρ/n)ˢ → 1/…
Pотк = pn+m
n каналов, очередь ≤ m
Всегда: ρ = λ/μ в одних единицах; Q = 1 − Pотк; A = λQ; T = L / λ (Литтл). Сомневаетесь в формуле — нарисуйте графцепочку и посчитайте pk по формуле гибели и размножения.

74.

ПОВЫШЕННАЯ СЛОЖНОСТЬ
Задачи повышенной сложности
Искусственный базис: двухэтапный метод (лекция 4)
Задание 4 до конца: двойственный симплекс после отсечения

75.

ПОВЫШЕННАЯ · ИСКУССТВЕННЫЙ БАЗИС
Когда обычный симплекс не стартует
Проблема (лекция 4, сл. 20–23)
Двухэтапный метод (сл. 24)
В «≥» вводим избыточную переменную со знаком
минус: 4X1 + 5X2 + 2X3 − X4 = 400.
В «=» дополнительной переменной нет вовсе.
Этап 1. Минимизируем искусственную функцию W —
сумму искусственных переменных. В таблице она
записана как −W → max.
Значит, в этих уравнениях нет базисной переменной
— начальный базис не построить.
W = 0 → все искусственные вышли из базиса —
получено допустимое решение.
Вводим искусственные переменные X7, X8, … ≥ 0
— по одной в каждое такое ограничение.
Этап 2. Строку −W и искусственные столбцы
убираем, продолжаем симплекс по исходной функции.
Физического смысла у них нет; в оптимальном решении они
должны стать равны нулю.
В таблице лекции обе строки, −E и −W, ведутся
одновременно — так сразу видно, что делать на этапе 2.
Где посмотреть: лекция 4, сл. 20–33 (на семинарах не разбирали; пример — раскрой стальных листов).

76.

ПОВЫШЕННАЯ · ИСКУССТВЕННЫЙ БАЗИС · ПРИМЕР ЛЕКЦИИ 4
Раскрой стальных листов: модель и искусственный базис
Изделия A, B, C вырезают из 150 стальных листов; каждый лист раскраивают одним из трёх способов. Нужно не
менее 400 изделий A, не менее 250 B и не более 300 C. Минимизировать отходы.
Способ
A
B
C
Отходы, см²
1
4
1
2
20
2
5
1
1
25
3
2
4
1
17
Xj — число листов, раскроенных способом j.
Стандартная форма + искусственные переменные
4X1 + 5X2 + 2X3 − X4 + X7 = 400
X1 + X2 + 4X3 − X5 + X8 = 250
X1 + X2 + X3 + X9 = 150
2X1 + X2 + X3 + X6 = 300
Начальный базис: X7, X8, X9 (искусственные) и X6 (остаточная).
Модель
E = 20X1 + 25X2 + 17X3 → min
4X1 + 5X2 + 2X3 ≥ 400; X1 + X2 + 4X3 ≥ 250
X1 + X2 + X3 = 150; 2X1 + X2 + X3 ≤ 300
W = X7 + X8 + X9. Выразив их через небазисные: W = −6X1 − 7X2 − 7X3 +
X4 + X5 + 800 → min,
т. е. −W = 6X1 + 7X2 + 7X3 − X4 − X5 − 800 → max; −E = −20X1 − 25X2 − 17X3
→ max

77.

ПОВЫШЕННАЯ · ИСКУССТВЕННЫЙ БАЗИС · ЭТАП 1 · ИТЕРАЦИИ 1–2
Минимизируем W (строка −W — ведущая)
БП
X1
X2
X3
X4
X5
X6
X7
X8
X9
Решение
−E
20
25
17
0
0
0
0
0
0
0
−W
−6
−7
−7
1
1
0
0
0
0
−800
X7
4
5
2
−1
0
0
1
0
0
400
X8
1
1
4
0
−1
0
0
1
0
250
X9
1
1
1
0
0
0
0
0
1
150
X6
2
1
1
0
0
1
0
0
0
300
БП
X1
X2
X3
X4
X5
X6
X7
X8
X9
Решение
−E
0
0
7
5
0
0
−5
0
0
−2000
−W
−0,4
0
−4,2
−0,4
1
0
1,4
0
0
−240
X2
0,8
1
0,4
−0,2
0
0
0,2
0
0
80
X8
0,2
0
3,6
0,2
−1
0
−0,2
1
0
170
X9
0,2
0
0,6
0,2
0
0
−0,2
0
1
70
X6
1,2
0
0,6
0,2
0
1
−0,2
0
0
220
Ход решения
Ведущий столбец — наибольший по модулю
отрицательный элемент строки −W.
Табл. 1: в −W минимум −7 у X2 и X3, берём X2;
входит X2, выходит X7 (отношения 80; 250;
150; 300).
Табл. 2: входит X3, выходит X8 (отношения
200; 47,22; 116,67; 366,67).
Строка −E пересчитывается по тем же
правилам, что и остальные строки.
Оранжевый — ведущий элемент; −W = −800 →
−240 → … растёт к нулю.

78.

ПОВЫШЕННАЯ · ИСКУССТВЕННЫЙ БАЗИС · ЭТАП 1 · ИТЕРАЦИИ 3–4
W = 0 — допустимое решение найдено
БП
X1
X2
X3
X4
X5
X6
X7
X8
X9
Решение
−E
−0,39
0
0
4,61
1,94
0
−4,61
−1,94
0
−2330,56
−W
−0,17
0
0
−0,17
−0,17
0
1,17
1,17
0
−41,67
X2
0,78
1
0
−0,22
0,11
0
0,22
−0,11
0
61,11
X3
0,06
0
1
0,06
−0,28
0
−0,06
0,28
0
47,22
X9
0,17
0
0
0,17
0,17
0
−0,17
−0,17
1
41,67
X6
1,17
0
0
0,17
0,17
1
−0,17
−0,17
0
191,67
БП
X1
X2
X3
X4
X5
X6
X7
X8
X9
Решение
−E
0
0,5
0
4,5
2
0
−4,5
−2
0
−2300
−W
0
0,21
0
−0,21
−0,14
0
1,21
1,14
0
−28,57
X1
1
1,29
0
−0,29
0,14
0
0,29
−0,14
0
78,57
X3
0
−0,07
1
0,07
−0,29
0
−0,07
0,29
0
42,86
X9
0
−0,21
0
0,21
0,14
0
−0,21
−0,14
1
28,57
X6
0
−1,5
0
0,5
0
1
−0,5
0
0
100
Ход решения
Табл. 3: входит X1, выходит X2 (отношения
78,57; 850; 250; 164,29).
Табл. 4: входит X4, выходит X9 (отношения
600; 133,33; 200).
После этого −W = 0, все искусственные X7, X8,
X9 вне базиса.
Допустимое решение: X1 = 116,67; X3 =
33,33; E = 2900
Этап 1 закончен: строку −W и столбцы X7–X9
убираем.

79.

ПОВЫШЕННАЯ · ИСКУССТВЕННЫЙ БАЗИС · ЭТАП 2
Оптимизируем исходную функцию — и ответ
БП
X1
X2
X3
X4
X5
X6
Решение
−E
0
5
0
0
−1
0
−2900
Ход решения
X1
1
1
0
0
0,33
0
116,67
X3
0
0
1
0
−0,33
0
33,33
В строке −E есть −1 под X5 → входит X5, выходит X4
(отношения 350; 200).
X4
0
−1
0
1
0,67
0
133,33
X6
0
−1
0
0
−0,33
1
33,33
После пересчёта отрицательных элементов в строке
−E нет — оптимум.
Ответ (лекция 4, сл. 33)
БП
X1
X2
X3
X4
X5
X6
Решение
X1 = 50, X2 = 0, X3 = 100; Emin = 2700 см²
−E
0
3,5
0
1,5
0
0
−2700
X1
1
1,5
0
−0,5
0
0
50
50 листов — способом 1, 100 — способом 3, способ 2
не используем.
X3
0
−0,5
1
0,5
0
0
100
X5
0
−1,5
0
1,5
1
0
200
X6
0
−1,5
0
0,5
0
1
100
X4 = 0: изделий A ровно 400; X5 = 200: изделий B 450;
X6 = 100: изделий C 200.

80.

ПОВЫШЕННАЯ · ГОМОРИ ДО КОНЦА · ЗАДАНИЕ 4
Таблица с отсечением: выбираем ведущий элемент
БП
x1
x2
x3
x4
x5
x6
b
Fmax
0
0
1
0
4/5
0
364/5
Двойственный симплекс
x1
1
0
1/2
0
−8/5
0
72/5
1. Строка. Берём строку с b < 0 —
это x6 (b = −3/5).
x4
0
0
−1/2
1
8/5
0
28/5
x2
0
1
0
0
1
0
11
x6
0
0
−1/2
0
−3/5
1
−3/5
Δ / |a|
—
—
2
—
4/3
—
2. Столбец. Только по
отрицательным элементам этой
строки считаем Δj / |aj|:
x3: 1 / (1/2) = 2; x5: (4/5) / (3/5) =
4/3.
Минимум 4/3 → столбец x5,
ведущий элемент −3/5
Обычный симплекс наоборот: там
сначала столбец (по строке F), потом
строка (по b / a).
Где посмотреть: это таблица задания 4, шаг 3 (тема 4); метод Гомори — лекция 6, семинар 4.

81.

ПОВЫШЕННАЯ · ГОМОРИ ДО КОНЦА · ЗАДАНИЕ 4
Пересчёт таблицы — целочисленный ответ
БП
x1
x2
x3
x4
x5
x6
b
Как пересчитали
Fmax
0
0
1/3
0
0
4/3
72
x5 входит в базис, x6 выходит.
x1
1
0
11/6
0
0
−8/3
16
x4
0
0
−11/6
1
0
8/3
4
x2
0
1
−5/6
0
0
5/3
10
x5
0
0
5/6
0
1
−5/3
1
Новая строка x5 = строка x6 : (−3/5): b = 1, у x3 —
5/6, у x6 — −5/3.
Остальные строки: из строки вычитаем её
элемент в столбце x5, умноженный на новую
строку x5.
Например, b в строке x1: 72/5 − (−8/5) · 1 = 16.
Строка F: 364/5 − (4/5) · 1 = 72.
Результат
x1 = 16, x2 = 10, Fmax = 72
Все переменные целые и все Δ ≥ 0 — одного отсечения
хватило.