Правильным отсечением задаче целочисленного программирования называется
Целочисленное программирование
При решении многих задач нецелочисленное решение не имеет смысла. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования - целочисленное программирование.
1.2. Целочисленные и частично целочисленные задачи линейного программирования
Определение 2.1. Экстремальная задача линейного программирования, в которой на решение налагается целочисленность компонент, является задачей целочисленного программирования и называется целочисленной задачей.
Определение 2.2.Экстремальная задача линейного программирования, в которой на решение налагается целочисленность нескольких компонент, является задачей целочисленного программирования и называется частично целочисленной задачей.
Общий алгоритм метода Гомори
Определение 2.3. Правильное отсечение - отсечение, которое удовлетворяют следующим требованиям:
2. отсекает часть области, не содержащей допустимых решений целочисленной-задачи не отсекает ни одного целочисленного оптимального плана.
Алгоритм метода Гомори в общем виде
Решается - задача, соответствующая исходной задаче.
Если -задача не имеет решения, т.е. G пуста или неограниченна в положительном направлении возрастания (убывания) F, то устанавливается неразрешимость целочисленной задачи.
Оптимальное решение Оптимальное решение Если решение целочисленное, то задача решена.
В противном случае, если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу.
Дополнительное ограничение, которое
2. отсекает часть области, не содержащей допустимых решений целочисленной - задачи;
3. не отсекает ни одного целочисленного оптимального плана, который входит в систему ограничений.
Процесс построения дополнительных ограничений продолжается до тех пор, пока не получится целочисленный план или же установится отсутствие целочисленного решения задачи.
В общем виде ЗНЛП состоит в определении макс. или мин. значений функции f(x1,x2,…,xn) (1) при условии, что её переменные удовлетворяют соотношениям:
где f и g - некоторые известные функции n переменных, а - заданные числа.
Метод множителей Лагранжа
Включает следующие этапы:
1) составл. фкц. Лагранжа
2) находим частн. произв. подфункции Лагранжа по перем. xj и xi, и приравниваем их нулю
3) решая систему ур-й (10), находим точки, в которых целевая функция задачи может иметь экстремум
4) среди точек, подозрительных на экстремум, находим такие, в к-х достиг. экстремум и вычисляем знач. функции (7) в этих точках.
Метод множит. Лагранжа можно применять и в том случае, когда условные связи (ограничения) представляют собой неравенства. Если треб. найти экстремум z=f(x), при условии g(x)£b, то сначала следует найти т. экстремума функции z из уравнений . . затем среди этих точек отобрать те, координаты которых удовл-ют системе уравнений
точки, найденные в результате реш-я этой системы вместе с точками опред. на 1 этапе и ужовл. условию g(x)<b подлежат дальнейщему исследованию.
Задачи выпуклого програмирования
gi(x1,…,xn) £bi (12)
Для решения сформулированной задачи в такой общей подстановке не сущ-ет универсальных методов. Однако для отд-х классов задач, в к-х сделаны доп. ограничения относительно свойств функций f, gi, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (11)-(13) при условии, что f вогнутая (выпуклая) функция и ОДР, определённая ограничениями (12)-(13) – выпуклая.
Вопросы по ЭММ
КОНТРОЛЬНО-ТЕСТИРУЮЩИЕ ВОПРОСЫ
по дисциплине «Математические методы в экономике»
- Что является объектом и языком исследования в экономико-математическом моделировании:
- различные типы производственного оборудования и методы его конструирования;
- экономические процессы и специальные математические методы;
- компьютерные программы и языки программирования.
- Какое матричное уравнение описывает замкнутую экономическую модель Леонтьева:
- (E – A)*X = C;
- A*X = X;
- A*X = E.
- Какое допущение постулируется в модели Леонтьева многоотраслевой экономики:
- выпуклость множества допустимых решений;
- нелинейность существующих технологий;
- линейность существующих технологий.
- Какое уравнение называется характеристическим уравнением матрицы А:
- (E – A)*X = Y;
- A*X = B;
- |A – lE| = 0.
- Множество n – мерного арифметического точечного пространства называется выпуклым, если:
- вместе с любыми двумя точками А и В оно содержит и весь отрезок АВ;
- счетно и замкнуто;
- равно объединению нескольких конечных множеств.
- Какая задача является задачей линейного программирования:
- управления запасами;
- составление диеты;
- формирование календарного плана реализации проекта.
- Задача линейного программирования называется канонической, если система ограничений включает в себя:
- только неравенства;
- равенства и неравенства;
- только равенства.
- Тривиальными ограничениями задачи линейного программирования называются условия:
- ограниченности и монотонности целевой функции;
- не отрицательности всех переменных;
- не пустоты допустимого множества.
- Если в задаче линейного программирования допустимое множество не пусто и целевая функция ограничена, то:
- допустимое множество не ограничено;
- оптимальное решение не существует;
- существует хотя бы одно оптимальное решение.
- Симплекс-метод предназначен для решения задачи линейного программирования:
- в стандартном виде;
- в каноническом виде;
- в тривиальном виде.
- Неизвестные в допустимом виде системы ограничений задачи линейного программирования, которые выражены через остальные неизвестные, называются:
- свободными;
- базисными;
- небазисными.
- Правильным отсечением в задаче целочисленного программирования называется дополнительное ограничение, обладающее свойством:
- оно должно быть линейным;
- оно должно отсекать хотя бы одно целочисленное решение;
- оно не должно отсекать найденный оптимальный нецелочисленный план.
- Какой из методов целочисленного программирования является комбинированным:
- симплекс-метод;
- метод Гомори;
- метод ветвей и границ.
- Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления:
- отсутствие последействия;
- наличие обратной связи;
- управление зависит от бесконечного числа переменных.
- Вычислительная схема метода динамического программирования:
- зависит от способов задания функций;
- зависит от способов задания ограничений;
- связана с принципом оптимальности Беллмана.
- Какую задачу можно решить методом динамического программирования:
- транспортную задачу;
- задачу о замене оборудования;
- принятия решения в конфликтной ситуации.
- Метод скорейшего спуска является:
- методом множителей Лагранжа;
- градиентным методом;
- методом кусочно-линейной аппроксимации.
- Множители Лагранжа в экономическом смысле характеризуют:
- доход, соответствующий плану;
- издержки ресурсов;
- цену (оценку) ресурсов.
- Функция нескольких переменных называется сепарабельной, если она может быть представлена в виде:
- суммы функций одной переменной;
- произведения функций нескольких переменных;
- суммы выпуклых функций.
- Платежной матрицей называется матрица, элементами которой являются:
- годовые прибыли отраслевых предприятий;
- выигрыши, соответствующие стратегиям игроков;
- налоговые платежи предприятий.
- Верхней ценой парной игры является:
- гарантированный выигрыш игрока А при любой стратегии игрока В;
- гарантированный выигрыш игрока В;
- гарантированный проигрыш игрока В.
- Чистой ценой игры называется:
- верхняя цена игры;
- нижняя цена игры;
- общее значение верхней и нижней ценой игры.
- Возможно ли привести матричную игру к задаче линейного программирования:
- возможно;
- невозможно;
- возможно, если платежная матрица единичная.
- Кооперативные игры – это игры:
- с нулевой суммой;
- со смешанными стратегиями;
- допускающие договоренности игроков.
- Какие математические методы можно применять для принятия хозяйственных решений в условиях неопределенности:
- линейного программирования;
- массового обслуживания;
- динамического программирования.
- Главными элементами сетевой модели являются:
- игровые ситуации и стратегии;
- состояния и допустимые управления;
- события и работы.
- В сетевой модели не должно быть:
- контуров и петель;
- собственных векторов;
- седловых точек.
- Критическим путем в сетевом графике называется:
- самый короткий путь;
- самый длинный путь;
- замкнутый путь.
- Математической основой методов сетевого планирования является:
- аналитическая геометрия;
- теория электрических цепей;
- теория графов.
- Какая из данных экономико-математичеких моделей является однофакторной:
- модель материализованного технического прогресса;
- модель расширенного воспроизводства;
- модель естественного роста.
Вопросы с ответами по дисциплине «математические методы в экономике»
1. Что является объектом и языком исследования в экономико-математическом моделировании:
A) различные типы производственного оборудования и методы его конструирования;
B) экономические процессы и специальные математические методы;
C) компьютерные программы и языки программирования.
2. Какое матричное уравнение описывает замкнутую экономическую модель Леонтьева:
3. Какое допущение постулируется в модели Леонтьева многоотраслевой экономики:
A) выпуклость множества допустимых решений;
B) нелинейность существующих технологий;
C) линейность существующих технологий.
4. Какое уравнение называется характеристическим уравнением матрицы А:
5. Множество n – мерного арифметического точечного пространства называется выпуклым, если:
A) вместе с любыми двумя точками А и В оно содержит и весь отрезок АВ;
B) счетно и замкнуто;
C) равно объединению нескольких конечных множеств.
6. Какая задача является задачей линейного программирования:
A) управления запасами;
B) составление диеты;
C) формирование календарного плана реализации проекта.
7. Задача линейного программирования называется канонической, если система ограничений включает в себя:
A) только неравенства;
B) равенства и неравенства;
C) только равенства.
8. Тривиальными ограничениями задачи линейного программирования называются условия:
A) ограниченности и монотонности целевой функции;
B) не отрицательности всех переменных;
C) не пустоты допустимого множества.
9. Если в задаче линейного программирования допустимое множество не пусто и целевая функция ограничена, то:
A) допустимое множество не ограничено;
B) оптимальное решение не существует;
C) существует хотя бы одно оптимальное решение.
10. Симплекс-метод предназначен для решения задачи линейного программирования:
A) в стандартном виде;
B) в каноническом виде;
C) в тривиальном виде.
11. Неизвестные в допустимом виде системы ограничений задачи линейного программирования, которые выражены через остальные неизвестные, называются:
12. Правильным отсечением в задаче целочисленного программирования называется дополнительное ограничение, обладающее свойством:
A) оно должно быть линейным;
B) оно должно отсекать хотя бы одно целочисленное решение;
C) оно не должно отсекать найденный оптимальный нецелочисленный план.
13. Какой из методов целочисленного программирования является комбинированным:
C) метод ветвей и границ.
14. Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления:
A) отсутствие последействия;
B) наличие обратной связи;
C) управление зависит от бесконечного числа переменных.
15. Вычислительная схема метода динамического программирования:
A) зависит от способов задания функций;
B) зависит от способов задания ограничений;
C) связана с принципом оптимальности Беллмана.
16. Какую задачу можно решить методом динамического программирования:
A) транспортную задачу;
B) задачу о замене оборудования;
C) принятия решения в конфликтной ситуации.
17. Метод скорейшего спуска является:
A) методом множителей Лагранжа;
B) градиентным методом;
C) методом кусочно-линейной аппроксимации.
18. Множители Лагранжа в экономическом смысле характеризуют:
A) доход, соответствующий плану;
B) издержки ресурсов;
C) цену (оценку) ресурсов.
19. Функция нескольких переменных называется сепарабельной, если она может быть представлена в виде:
A) суммы функций одной переменной;
B) произведения функций нескольких переменных;
C) суммы выпуклых функций.
20. Платежной матрицей называется матрица, элементами которой являются:
A) годовые прибыли отраслевых предприятий;
B) выигрыши, соответствующие стратегиям игроков;
C) налоговые платежи предприятий.
21. Верхней ценой парной игры является:
A) гарантированный выигрыш игрока А при любой стратегии игрока В;
B) гарантированный выигрыш игрока В;
C) гарантированный проигрыш игрока В.
22. Чистой ценой игры называется:
A) верхняя цена игры;
B) нижняя цена игры;
C) общее значение верхней и нижней ценой игры.
23. Возможно ли привести матричную игру к задаче линейного программирования:
C) возможно, если платежная матрица единичная.
24. Кооперативные игры – это игры:
A) с нулевой суммой;
B) со смешанными стратегиями;
C) допускающие договоренности игроков.
25. Какие математические методы можно применять для принятия хозяйственных решений в условиях неопределенности:
A) линейного программирования;
B) массового обслуживания;
C) динамического программирования.
26. Главными элементами сетевой модели являются:
A) игровые ситуации и стратегии;
B) состояния и допустимые управления;
C) события и работы.
27. В сетевой модели не должно быть:
A) контуров и петель;
B) собственных векторов;
C) седловых точек.
28. Критическим путем в сетевом графике называется:
A) самый короткий путь;
B) самый длинный путь;
C) замкнутый путь.
29. Математической основой методов сетевого планирования является:
A) аналитическая геометрия;
B) теория электрических цепей;
C) теория графов.
30. Какая из данных экономико-математичеких моделей является однофакторной:
A) модель материализованного технического прогресса;
B) модель расширенного воспроизводства;
C) модель естественного роста.
Запись навигация
Источники: http://life-prog.ru/2_32613_tselochislennoe-programmirovanie.html, http://damirock.com/exam/economics/voprosyi-po-emm/, http://sdalna10.com/24051860
Комментариев пока нет!
Поделитесь своим мнением