Методические указания к лабораторным работам Чебоксары 2006 (стр. 4 из 4)
2. На k-й итерации базисные переменные – это X1, …, Xm, которые принимают значения b'1, …, b'm. Обращение базиса – матрица B–1 размерностью m´m, а симплекс-множители равны p1, …, pm.
3. Вычислить коэффициенты небазисных переменных в канонической форме целевой функции в текущем базисе:
,где pi- текущие симплекс-множители, aij - исходные коэффициенты из уравнения.
4. Величины C'j вычисляются для каждой небазисной переменной. Найти наименьший из коэффициентов C'm+1 , …, C'n.
5. Если C's ³ 0, то минимум функции Z найден, конец. Иначе: C's < 0, и переменная Xs войдет в базис.
6. Определить переменную, которая будет заменена переменной Xs. С этой целью вычислить a's = B–1*as.
7. Определить строку базисной переменной, предназначенной для исключения из базиса
.Заменить старый базис X1, …, Xr, …, Xm на новый X1, …, Xs, …, Xm. Новые значения базисных переменных равны
; Xi = bi+ = b'i – ais *br+; (i ¹ r).8. Cформировать матрицу:
- r-я строка5-я строка
9. Вычислить (новое обращение) =Е
(исходное обращение).10. Найти новые симплекс-множители. Исходные значения симплекс-множителей
.11. Новые значения симплекс множителей
.Вернуться к 2.
Контрольные вопросы и задания
1. Как определяется направление возрастания целевой функции в графическом методе решения задачи линейного программирования (ЛП)?
2. Дайте характеристику стандартной формы задач линейного программирования.
3. Приведите основные правила для преобразования задачи ЛП к стандартному виду.
4. Каким соотношением задается отрезок в n-мерном пространстве?
5. Дайте определение экстремальной точки.
6. Какое множество называется выпуклым?
7. Докажите, что если ограничения имеют допустимое решение, то они имеют и базисное решение.
8. Докажите, что допустимая область является выпуклым множеством.
9. Докажите, что базисные допустимые решения соответствуют вершинам выпуклого множества.
10. Докажите, что если целевая функция имеет конечный минимум, то, по крайней мере, одно оптимальное решение является базисным.
11. Дайте характеристику канонической формы задачи ЛП.
12. Выведите основные соотношения для симплекс-метода.
13. Назовите основные шаги симплекс-метода.
14. Какой базис называется вырожденным?
15. Рассмотрите изменения значений правых частей.
16. Рассмотрите изменения коэффициентов целевой функции.
17. Как решается задача ЛП при появлении дополнительных переменных?
18. Опишите решение задачи ЛП при включении дополнительных ограничений.
19. Приведите основные шаги двойственного симплекс-метода.
20. Приведите основные шаги улучшенного симплекс-метода.
21. Основные правила перехода к двойственной задаче.
22. Докажите, что двойственной задачей к двойственной задаче есть прямая задача.
23. Докажите, что Z ³ W, где W – целевая функция двойственной задачи.
24. Докажите, что если прямая задача имеет конечное решение, то двойственная задача имеет конечное решение Wmax = Zmin.
25. Докажите, что значения симплекс-множителей оптимального решения двойственной задачи являются значениями переменных в оптимальном решении прямой задачи.
Задание к лабораторной работе
Составить диету, содержащую 20 единиц белков, 30 единиц углеводов, 10 единиц жиров и 40 единиц витаминов, из пяти продуктов. Как дешевле всего достичь этого при указанных в таблице ценах на 1 кг (или на 1 л) продуктов?
Таблица
| Хлеб | Соя | Сушеная рыба | Фрукты | Молоко | |
| Белки Углеводы Жиры Витамины | 2 12 1 2 | 12 0 8 2 | 10 0 3 4 | 1 4 0 6 | 2 3 4 2 |
| Цена | 12 | 36 | 32 | 18 | 10 |
Отчет о работе
1. Титульный лист.
2. Задание к лабораторной работе.
3. Алгоритм метода.
4. Программа решения задачи.
5. Краткий анализ результатов вычисления.
6. Выводы по работе.
Список методов
1. Симплекс-метод.
2. Улучшенный симплекс-метод.
3. Двойственный симплекс-метод.
Выбор методов решения
1. Порядковый номер студента в журнале по модулю 3.
2. Номер первого метода +2 по модулю 3.
Список рекомендуемой литературы
1. Карманов В.Г. Математическое программирование. М.: Наука, 1980.
2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Оглавление
| Лабораторная работа 1. Одномерная оптимизация…………... | 3 |
| Лабораторная работа 2. Методы прямого поиска оптимума для функции N переменных……………………………………. | 9 |
| Лабораторная работа 3. Численные методы для оптимизации дифференцируемых функций………………………………….. | 13 |
| Лабораторная работа 4. Линейное программирование………. | 18 |
Методы оптимизации
Методические указания к лабораторным работам
Отв. за выпуск О.М. Садовникова
Подписано в печать 20.10.06. Формат 60×84/16. Бумага газетная. Гарнитура Times. Печать оперативная. Усл. печ. л. 1,39. Уч.-изд. л. 1,25. Тираж 50 экз. Заказ № 676.
Чувашский государственный университет
Типография университета
428015 Чебоксары, Московский просп., 15Министерство образования и науки
российской федерации
федеральное агентство по образованию
Федеральное государственное образовательное учреждение
высшего профессионального образования
«Чувашский государственный университет имени И. Н. Ульянова»
Методы оптимизации
Методические указания к лабораторным работам
Чебоксары 2006