- •Обозначения
- •Введение
- •Задача математического программирования
- •Задача выпуклого программирования
- •Задача линейного программирования
- •Основная идея симплекс-метода
- •Примеры задач линейного программирования
- •Задача максимизации прибыли
- •Транспортная задача
- •Задачи о назначениях
- •Задача коммивояжера
- •Задачи
- •Симплекс-метод
- •Числовой пример
- •Симплекс-метод в строчной форме
- •Зацикливание и способы защиты от него
- •Зацикливание
- •Лексикографический метод
- •Правило Бленда выбора ведущего элемента
- •Получение начального допустимого опорного плана
- •Задачи
- •Столбцовая форма
- •Двойственность в линейном программировании
- •Теорема двойственности
- •Дополняющая нежесткость в линейном программировании
- •Задачи
- •Двойственный симплекс-метод
- •Задачи
- •Целочисленное линейное программирование
- •Идея правильных отсечений
- •Постановка задачи
- •Циклический алгоритм Гомори
- •Полностью целочисленный алгоритм
- •Прямой метод целочисленного программирования
- •Задачи
- •Программа курса
- •Литература
Линейное и целочисленное линейное программирование
учебное пособие 1
В.Н.Шевченко, Н.Ю.Золотых
2002
1Нижегородский государственный университет
Оглавление
Обозначения |
|
4 |
||
1. |
Введение |
|
5 |
|
|
1.1. |
Задача математического программирования . . . . . . . . |
5 |
|
|
1.2. |
Задача выпуклого программирования . . . . . . . . . . . . |
6 |
|
|
1.3. |
Задача линейного программирования . . . . . . . . . . . . |
12 |
|
|
1.4. |
Основная идея симплекс-метода . . . . . . . . . . . . . . . |
15 |
|
|
1.5. Примеры задач линейного программирования . . . . . . . |
16 |
||
|
|
1.5.1. |
Задача максимизации прибыли . . . . . . . . . . . |
16 |
|
|
1.5.2. |
Задача о «смесях» . . . . . . . . . . . . . . . . . . . |
17 |
|
|
1.5.3. |
Транспортная задача . . . . . . . . . . . . . . . . . |
17 |
|
|
1.5.4. |
Задачи о назначениях . . . . . . . . . . . . . . . . . |
18 |
|
|
1.5.5. |
Задача о «раскрое» . . . . . . . . . . . . . . . . . . |
19 |
|
|
1.5.6. |
Задача коммивояжера . . . . . . . . . . . . . . . . . |
20 |
|
1.6. |
Задачи |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
22 |
2. |
Симплекс-метод |
23 |
||
|
2.1. |
Числовой пример . . . . . . . . . . . . . . . . . . . . . . . |
23 |
|
|
2.2. Симплекс-метод в строчной форме . . . . . . . . . . . . . |
26 |
||
|
2.3. Зацикливание и способы защиты от него . . . . . . . . . . |
32 |
||
|
|
2.3.1. |
Зацикливание . . . . . . . . . . . . . . . . . . . . . |
32 |
|
|
2.3.2. |
Лексикографический метод . . . . . . . . . . . . . |
36 |
|
|
2.3.3. |
Правило Бленда выбора ведущего элемента . . . . |
38 |
|
2.4. |
Получение начального допустимого опорного плана . . . |
39 |
|
|
2.5. |
Задачи |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
43 |
|
2.6. |
Столбцовая форма . . . . . . . . . . . . . . . . . . . . . . . |
44 |
|
2
ОГЛАВЛЕНИЕ |
3 |
|
3. Двойственность в линейном программировании |
50 |
|
3.1. |
Теорема двойственности . . . . . . . . . . . . . . . . . . . |
50 |
3.2. Дополняющая нежесткость в линейном программировании |
57 |
|
3.3. |
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
59 |
3.4. |
Двойственный симплекс-метод . . . . . . . . . . . . . . . . |
60 |
3.5. |
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
62 |
4. Целочисленное линейное программирование |
63 |
|
4.1. |
Идея правильных отсечений . . . . . . . . . . . . . . . . . |
63 |
4.2. |
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . |
64 |
4.3. |
Циклический алгоритм Гомори . . . . . . . . . . . . . . . . |
64 |
4.4. |
Полностью целочисленный алгоритм . . . . . . . . . . . . |
68 |
|
4.4.1. Прямой метод целочисленного программирования |
71 |
4.5. |
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
73 |
Программа курса |
74 |
|
Литература |
76 |
|
Обозначения
Z кольцо целых чисел,
Q поле рациональных чисел,
R поле вещественных чисел,
P n множество n-мерных арифметических векторов с компонентами из P (рассматриваемых как строки или как столбцы),
P n×m множество матриц размером n × m с элементами из P ,
[α] целая часть числа α: наибольшее целое, не превосходящее α.
{α} дробная часть числа α: {α} = α − [α].
4