RUS ENG

Альсевич В. В. и др. Оптимизация линейных экономических моделей: Статические задачи

Альсевич В. В. и др. Оптимизация линейных экономических моделей: Статические задачи: Учеб. пособие/В. В. Альсевич, Р. Габасов, В. С. Глушенков.— Мн.: БГУ, 2000. — 210 с.: ил.

ISBN 985-445-258-1

Основная цель пособия состоит в обосновании одного из методов решения линейных задач оптимизации — адаптивного метода. Помимо этого в пособии приведено большое количество примеров конкретных прикладных задач, в особенности из экономической области, для которых построены ма­тематические модели в виде линейных задач оптимизации. Приводится программная реализация адаптивного метода на языке PASCAL. Приложение содержит некоторые известные результаты, а также необходимый вспомогательный материал.

Предназначено для студентов экономических и математических специальностей университетов. Может быть использовано студентами других специальностей, а также специалистами любой производственной области, интересующимися решением и анализом оптимизационных задач.


Оглавление

Предисловие

7

Введение

8

Глава 1. ЛИНЕЙНЫЕ МОДЕЛИ ПРИКЛАДНЫХ ЗАДАЧ

11

§ 1. Общие приемы построения экономико-математических моделей

11

1.1. Два пути повышения эффективности производства

11

1.2. Основные этапы моделирования

12

1.3. Математическое описание зависимостей между входными и выходными ингредиентами

13

1.4. Ограничения на переменные

15

1.5. Виды целевых функций

15

§ 2. Задачи о диете, раскрое, смесях

17

2.1. Задача о диете (рационе)

17

2.2. Задача о раскрое

18

2.3. Задача о сплавах (смесях)

19

2.4. Управление металлургическим процессом

20

§ 3. Некоторые производственные задачи

21

3.1 Рациональное использование ресурсов .

21

3.2. Эффективная загрузка оборудования

22

3.3. Задача технического контроля

23

§4. Задачи сельскохозяйственного производства

24

4.1. Задача о посевах

24

4.2. Задачи животноводства

25

§ 5. Задачи выбора технологических процессов

27

5.1. Оптимальное использование различных технологий

27

5.2. Производство продукции с минимальными затратами при заданном спросе

29

5.3. Выпуск продукции цементного завода

30

§ 6. Задачи энергетики

32

6.1. Электрификация экономического региона

32

6.2. Переработка нефти

33

§ 7. Транспортные задачи

34

7.1. Матричная транспортная задача

34

7.2. Сетевая задача

36

7.3. Задача о назначениях

37

§ 8. Задачи специального вида

38

8.1. Рациональное использование станочного парка

38

8.2. Оптимальное использование комплексного сырья

39

§ 9. Статические задачи математической экономики

40

9.1. Задача оптимального потребления

40

9.2. Задача производства

43

9.3. Двухфакторная модель фирмы

47

9.4. Оптимальная политика инвестиций фирмы

47

9.5. Задача многоотраслевых связей

48

§ 10. Динамические задачи

51

10.1. Динамическая модель межотраслевого баланса

51

10.2. Сглаживание производственного процесса

52

10.3. Управление запасами

53

10.4. Задача оптимального управления производственной деятельностью фирмы

54

10.5. Неоклассическая модель экономического роста

57

10.6. Оптимальная политика фирмы

60

10.7. Оптимизационная модель расширяющейся экономики

65

Глава 2. АДАПТИВНЫЙ МЕТОД

68

§ 11. Классификация экстремальных задач

68

§ 12. Интервальная задача .линейного программирования (ИЗЛП)

69

12 .1. Основные понятия

69

12.2. Каноническая, нормальная и произвольная формы задач линейного программирования

71

12.3. Оптимальный и субоптимальный (ξ-оптимальный) планы

72

12.4. Опора. Опорный план. Физический смысл опоры

74

12.5. Формула приращения целевой функции

75

12.6. Потенциалы, оценки, их физический смысл

76

12.7. Критерий оптимальности опорного плана

77

12.8. Принцип максимума

84

12.9. Обсуждение

84

12.10. Сопровождающий псевдоплан и сопровождающий вектор псевдозатрат

85

12.11. Оценка субоптимальности. Достаточное условие субоптимальности

86

§ 13. Двойственная задача. Элементы теории двойственности

88

13.1 Построение двойственной задачи

88

13.2. Мнемоническое правило построения двойственной задачи

91

13.3. Согласованный и сопровождающий двойственные планы

92

13.4. Взаимная двойственность прямой и двойственной задач

93

13.5. Теоремы существования и двойственности

94

13.6. Достаточное условие оптимальности

95

13.7. Условия дополняющей нежесткости

96

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

96

13.9. Свойство сопровождающего псевдоплана

97

13.10. Оценка оптимальных значений целевых функций прямой и двойственной задач

97

§ 14. Критерий ξ -оптимальности

98

14.1. Разложение оценки субоптимальности

98

14.2. Необходимое условие субоптимальности

99

14.3. Критерий ξ -оптимальности

99

14.4. Принцип ξ -максимума

100

14.5 Обсуждение

101

§ 15. Классификация методов решения экстремальных задач

101

15.1. Что значит "решить экстремальную задачу"?

102

15.2 Классификация итеративных методов

102

§ 16. Прямой адаптивный метод

103

16.1. Принципы прямого адаптивного метода

103

16.2. Процедура замены плана

105

16.3. Процедура замены опоры . . Построение подходящего направления

113

16.4. Процедура замены опоры. Вычисление короткого двойственного шага

122

16.5. Адаптивный метод с коротким двойственным шагом

124

16.6. Правило длинного двойственного шага при замене опоры

127

16.7. Адаптивный метод с длинным двойственным шагом. Случай двойственно вырожденного опорного плана

133

16.8. Конечность адаптивного метода

135

16.9. Обсуждение

135

§ 17. Первая фаза адаптивного метода

136

17.1. Построение начального плана

136

17.2. Построение начальной опоры

139

17.3. Обсуждение

141

§ 18. Двойственный адаптивный метод

141

§ 19. Анализ решения

142

19.1. Единственность оптимального плана

143

19.2. Единственность оптимальной опоры

144

19.3. Чувствительность значения интервальной задачи к вариации вектора стоимости

146

19.4. Чувствительность значения задачи к вариации векторов прямых ограничений

149

19.5. Чувствительность значения ИЗЛП к варьированию векторов основных ограничений

152

19.6. Чувствительность значения ИЗЛП к вариации элементов матрицы условий

155

§ 20. Разные задачи

157

20.1. Метод решения семейства интервальных задач

157

20.2. Метод решения нестационарных задач

158

20.3. Решение задач ЛП в произвольной форме

159

Глава 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

161

§ 21. Схемы основных алгоритмов

161

21.1. Прямой опорный метод с симплексной нормировкой для интервальной задачи

161

21.2. Двухфазный опорный метод с симплексной нормировкой

163

21.3. Двойственный метод для интервальной задачи

165

21.4. Прямой метод с адаптивной нормировкой для интервальной задачи

167

21.5. Прямой опорный метод с симплексной нормировкой для канонической задачи

168

21.6. Двойственный метод для канонической задачи

169

§ 22. Реализация некоторых шагов

171

22.1. Схема хранения условий задачи

171

22.2. Ввод исходных данных

172

22.3. Задание начальной пустой опоры

173

22.4. Вычисление векторов потенциалов и оценок, сопровождающих текущую опору

173

22.5. Вычисление неопорных компонент псевдоплана

174

22.6. Вычисление опорных компонент псевдоплана

174

22.7. Проверка условия оптимальности двойственного метода

175

22.8. Проверка условия оптимальности прямого метода

175

22.9. Построение направления для изменения потенциалов и оценок

176

22.10. Построение направления для изменения плана

176

22.11. Прямой шаг

177

22.12. Длинный двойственный шаг

178

22.13. Замена опоры в двойственном методе

180

22.14. Процедура пересчета обратной матрицы

180

22.15. Процедуры контроля для отладочного режима

182

22.16. Вывод результата

184

§ 23. Особенности программирования и отладки

185

23.1. Контроль работы алгоритма

185

23.2. Контроль полученного решения

186

23.3. Наиболее часто встречающиеся ошибки и их поиск

187

23.4. Проверка входных данных

187

23.5. Тестирование программы

187

23.6. Генератор тестовых задач

188

Приложение

192

П 1. Симплекс-метод и адаптивный метод для канонической задачи ЛИ

192

П1.1. Симплекс-метод

192

П1.2. Адаптивный метод

196

П 2. Доказательство невырожденности новых опорных (базисных) матриц

198

П2.1. Замена столбца

199

П2.2. Замена строки

199

П2.3. Удаление строки и столбца

200

П2.4. Добавление столбца и строки

200

П 3. Анализ чувствительности значения ИЗЛП в вырожденном случае

201

П 4. Конечные модификации

204

П4.1. Конечность в случае невырожденности

204

П4.2. Способы предупреждения зацикливания

205

П4.3. Конечная модификация прямого опорного метода с симплексной нормировкой для канонической задачи

206

П4.4. Конечная модификация двойственного метода для канонической задачи

207

Литература

210

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры