Составители:
Рубрика:
5 6
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ …………………………………………………….. 5
1. ПРИМЕРЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ……..................
12
1.1. Задача оптимального производственного планирова-
ния…………………………………………………...............
12
1.2. Задача о смесях……………………………………...... 13
1.3. Задача о раскрое....………………………………….... 15
1.4. Транспортная задача ………………………………..... 16
1.5. Вопросы для самопроверки ………………………..... 18
2. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ.. 19
2.1. Основные понятия и теоремы ……………………..... 19
2.2. Решение систем линейных алгебраических уравне-
ний методом Жордана−Гаусса..................……………........
20
3. РАЗЛИЧНЫЕ ФОРМЫ МОДЕЛИ
ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …................….
26
3.1. Формулировка основной задачи линейного програм-
мирования …………………………….…………….............
26
3.1.1. Общая форма модели ………………………........ 26
3.1.2. Стандартная форма модели ……………….......... 26
3.1.3. Каноническая форма модели ……………........... 27
3.2. Понятие допустимого решения, области допустимых
решений, оптимального решения задачи линейного про-
граммирования …….......................................................…..
28
3.3. Переход от задачи минимизации целевой функции
к задаче максимизации ……………………………............
28
3.4. Переход от одной формы
модели задачи линейного
программирования к другой.................................................
29
3.4.1. Переход к канонической форме модели …..... 29
3.4.2. Переход от канонической формы модели зада-
чи линейного программирования к стандартной........
32
3.5. Выпуклые множества …………………….………....... 34
4. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИ-
НЕЙНОГО ПРОГРАММИРОВАНИЯ …..................….….
36
4.1. Геометрическая интерпретация множества решений
линейного неравенства ……………………………............
36
4.2. Геометрическая интерпретация множества решений
системы линейных неравенств
…….……………...............
37
4.3. Вопросы для самопроверки ………………………...... 46
5. СВОЙСТВА ДОПУСТИМЫХ ПЛАНОВ ЗАДАЧИ ЛИ-
НЕЙНОГО ПРОГРАММИРОВАНИЯ. ОПОРНЫЙ ПЛАН..
47
6. СИМПЛЕКС-МЕТОД ………………………….................. 51
6.1. Идея симплекс-метода ……………………………...... 51
6.2. Алгебра симплекс-метода …………………………..... 55
6.2.1. Алгоритм симплекс-метода ………………....... 58
6.2.2. Выбор разрешающей строки в симплексных
преобразованиях ……………………………...............
61
6.2.3. Альтернативный оптимум …………………..... 62
6.2.4. Признак неограниченности целевой функции.. 63
6.3. Понятие о вырождении ……………………………..... 65
6.4. Вопросы для
самопроверки ………………………...... 76
6.5. Индивидуальное задание ……………........................... 77
6.6. Задачи для самостоятельной работы …….………...... 85
7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИ-
РОВАНИИ ………………......………………………………
88
7.1. Пример двойственных задач линейного программи-
рования………………….. …………………....…………….
88
7.2. Правила построения двойственных задач ………....... 90
7.3. Симметричные двойственные задачи ……………...... 92
7.4. Основные теоремы двойственности ……………........ 98
7.5. Анализ устойчивости двойственных оценок ……..... 115
7.6. Вопросы для самопроверки ………………………..... 122
7.7. Индивидуальное задание ……….........................……. 122
ЗАКЛЮЧЕНИЕ…………………………………………………. 127
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ………………………... 128
ПРИЛОЖЕНИЕ. Применение программы Excel
к решению
задач линейного программирования ………………………….
130
ОГЛАВЛ ЕНИЕ 4.2. Геометрическая интерпретация множества решений
системы линейных неравенств …….……………............... 37
ВВЕДЕНИЕ …………………………………………………….. 5 4.3. Вопросы для самопроверки ………………………...... 46
1. ПРИМЕРЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ 5. СВОЙСТВА ДОПУСТИМЫХ ПЛАНОВ ЗАДАЧИ ЛИ-
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ…….................. 12 НЕЙНОГО ПРОГРАММИРОВАНИЯ. ОПОРНЫЙ ПЛАН.. 47
1.1. Задача оптимального производственного планирова- 6. СИМПЛЕКС-МЕТОД ………………………….................. 51
ния…………………………………………………............... 12 6.1. Идея симплекс-метода ……………………………...... 51
1.2. Задача о смесях……………………………………...... 13 6.2. Алгебра симплекс-метода …………………………..... 55
1.3. Задача о раскрое....………………………………….... 15 6.2.1. Алгоритм симплекс-метода ………………....... 58
1.4. Транспортная задача ………………………………..... 16 6.2.2. Выбор разрешающей строки в симплексных
1.5. Вопросы для самопроверки ………………………..... 18 преобразованиях ……………………………............... 61
2. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ.. 19 6.2.3. Альтернативный оптимум …………………..... 62
2.1. Основные понятия и теоремы ……………………..... 19 6.2.4. Признак неограниченности целевой функции.. 63
2.2. Решение систем линейных алгебраических уравне- 6.3. Понятие о вырождении ……………………………..... 65
ний методом Жордана−Гаусса..................……………........ 20 6.4. Вопросы для самопроверки ………………………...... 76
3. РАЗЛИЧНЫЕ ФОРМЫ МОДЕЛИ ЗАДАЧИ 6.5. Индивидуальное задание ……………........................... 77
26
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …................…. 6.6. Задачи для самостоятельной работы …….………...... 85
3.1. Формулировка основной задачи линейного програм- 7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИ-
мирования …………………………….……………............. 26 РОВАНИИ ………………......……………………………… 88
3.1.1. Общая форма модели ………………………........ 26 7.1. Пример двойственных задач линейного программи-
3.1.2. Стандартная форма модели ……………….......... 26 рования………………….. …………………....……………. 88
3.1.3. Каноническая форма модели ……………........... 27 7.2. Правила построения двойственных задач ………....... 90
3.2. Понятие допустимого решения, области допустимых 7.3. Симметричные двойственные задачи ……………...... 92
решений, оптимального решения задачи линейного про- 7.4. Основные теоремы двойственности ……………........ 98
граммирования …….......................................................….. 28 7.5. Анализ устойчивости двойственных оценок ……..... 115
3.3. Переход от задачи минимизации целевой функции 7.6. Вопросы для самопроверки ………………………..... 122
к задаче максимизации ……………………………............ 28 7.7. Индивидуальное задание ……….........................……. 122
3.4. Переход от одной формы модели задачи линейного
программирования к другой................................................. 29 ЗАКЛЮЧЕНИЕ…………………………………………………. 127
3.4.1. Переход к канонической форме модели …..... 29 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ………………………... 128
3.4.2. Переход от канонической формы модели зада-
ПРИЛОЖЕНИЕ. Применение программы Excel к решению
чи линейного программирования к стандартной........ 32
задач линейного программирования …………………………. 130
3.5. Выпуклые множества …………………….………....... 34
4. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИ-
НЕЙНОГО ПРОГРАММИРОВАНИЯ …..................….…. 36
4.1. Геометрическая интерпретация множества решений
линейного неравенства ……………………………............ 36
5 6
