ОГЛАВЛЕНИЕ

Предисловие редактора перевода
Из предисловия автора

1.1. Задачи линейного программирования
1.2. Эквивалентные формулировки
1.3. Неравенства
1.4. Конусы, выпуклые множества и выпуклые функции
1.5. Базисные, допустимые и оптимальные решения
1.6. Геометрическая интерпретация задачи линейного программирования
Упражнения

1.1. Введение
2.2. Таблица симплекс-метода
2.3. Начальный допустимый базис и вырожденность
2.4. Симплекс-метод в матричной форме записи
2.5. Геометрическая интерпретация симплекс-метода
2.6. Экономическая интерпретация симплекс-метода
Упражнения
Дополнение

3.1. Теорема двойственности (Гейл, Кун, Таккер [71])
3.2. Дополняющая нежесткость (Данциг и Орден [44]).
3.3. Ортогональность решений (Таккер [193])
3.4. Геометрическая интерпретация двойственности и дополняющей нежесткости (Гомори [83])
Упражнения
Дополнение

4.1. Двойственный симплекс-метод (Лемке [141])
4.2. Столбцовая таблица (Бил [8])
4.3. Геометрическая интерпретация (Лемке [141])
Упражнения

5 1. Введение (Данциг и Орчард-Хейс [43])
5.2. Изменение исходной информации Упражнения

*6.1. Взаимный метод решения прямой и двойственной задач (Балинский и Гомори [7] и Тролл [184])
6.2. Прямо-двойственный метод (Данциг, Форд и Фалкерсон [40])

7.1. Принцип декомпозиции (Данциг и Вулф [46], [47])
7.2. Пример
Упражнения
Дополнение

8.1. Введение
8.2. Метод расстановки пометок для нахождения максимального потока
8.3. Приложения
8.4. Линейное программирование и потоки в сетях
8.5. Свойство абсолютной унимодулярности (Гофман, Краскал [103], Вейнотт, Данциг [l99])
Упражнения
Дополнение

9.1. Постановки задач
9.2. Условие реализуемости (Гомори и Ху [89])
9.3. Анализ сети (Гомори и Ху [89])
9.4. Синтез сети (Гомори и Ху [89])
Упражнения
Дополнение
Нерешенные задачи

10.1. Кратчайшие цепи (Дийкстра [49])
10.2. Многополюсные кратчайшие цепи (Флойд [63], Ху [111), Мерчленд [158], Уоршелл [209])
10.3. Декомпозиционный алгоритм (Ху [111], [113])
10.4. Потоки минимальной стоимости
10.5. Задачи об оптимальном преобразовании заданной сети (Фалкерсон [68], Ху [108])
Упражнения

*11.1. Двухпродуктовые потоки (Ху [106])
11.2. Многопродуктовые потоки (Форд и Фалкерсон [66), Томлин [186])
11.3. Синтез коммуникационных сетей (Гомори и Ху [91])

12.1. Локально минимальные разрезы
12.2. Сети с пропускными способностями узлов
12.3. Потоки в непрерывной среде
12.4. r-разделяющее множество .

13.1. Введение (Гомори [79])
13.2. Примеры (Гомори [79])
13.3. Геометрическая интерпретация
13.4. Свойства дополнительных неравенств (Гомори и Баумоль [87])

14.1. Полностью целочисленный алгоритм (Гомори [80])
14.2. Пример

15.1. Введение (Гомори [81])
15.2. Метод разбиения в смешанном целочисленном программировании (Бендерс [18])
15.3. Приложения

16.1. Введение (Витцгалл [215])
16.2. Таблица
16.3. Преобразование
16.4. Алгоритм
16.5. Примеры
16.6. Доказательство конечности

17.1. Введение и алгоритм
17.2. Пример
17.3. Доказательство конечности
17.4. Вывод соотношений и пояснений

18.1. Задача о рюкзаке (Гилмор, Гомори [75], Гомори [84])

19.1. Введение (Гомори [84], Кортанек и Ярослав [133])
19.2. Асимптотический алгоритм (Гомори [84], [85], [86])
19.3. Алгоритм групповой минимизации (Ху [112])

20.1. Введение
20.2. Вычисление грани
20.3. Многогранники P(G, g)
20.4. Автоморфизмы главных многогранников
20.5. Грани многогранников циклических групп
20.6. Грани многогранников гомоморфных групп
20.7. Характеры и неравенства