Правильным отсечением задаче целочисленного программирования называется



Целочисленное программирование

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

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) – выпуклая.

Вопросы по ЭММ

КОНТРОЛЬНО-ТЕСТИРУЮЩИЕ ВОПРОСЫ
по дисциплине «Математические методы в экономике»

  1. Что является объектом и языком исследования в экономико-математическом моделировании:
  2. различные типы производственного оборудования и методы его конструирования;
  3. экономические процессы и специальные математические методы;
  4. компьютерные программы и языки программирования.
  1. Какое матричное уравнение описывает замкнутую экономическую модель Леонтьева:
  2. (E – A)*X = C;
  3. A*X = X;
  4. A*X = E.
  1. Какое допущение постулируется в модели Леонтьева многоотраслевой экономики:
    1. выпуклость множества допустимых решений;
    2. нелинейность существующих технологий;
    3. линейность существующих технологий.
  1. Какое уравнение называется характеристическим уравнением матрицы А:
    1. (E – A)*X = Y;
    2. A*X = B;
    3. |A &#8211; lE| = 0.
  1. Множество n – мерного арифметического точечного пространства называется выпуклым, если:
    1. вместе с любыми двумя точками А и В оно содержит и весь отрезок АВ;
    2. счетно и замкнуто;
    3. равно объединению нескольких конечных множеств.
  1. Какая задача является задачей линейного программирования:
    1. управления запасами;
    2. составление диеты;
    3. формирование календарного плана реализации проекта.
  1. Задача линейного программирования называется канонической, если система ограничений включает в себя:
    1. только неравенства;
    2. равенства и неравенства;
    3. только равенства.
  1. Тривиальными ограничениями задачи линейного программирования называются условия:
    1. ограниченности и монотонности целевой функции;
    2. не отрицательности всех переменных;
    3. не пустоты допустимого множества.
  1. Если в задаче линейного программирования допустимое множество не пусто и целевая функция ограничена, то:
    1. допустимое множество не ограничено;
    2. оптимальное решение не существует;
    3. существует хотя бы одно оптимальное решение.
  1. Симплекс-метод предназначен для решения задачи линейного программирования:
    1. в стандартном виде;
    2. в каноническом виде;
    3. в тривиальном виде.
  1. Неизвестные в допустимом виде системы ограничений задачи линейного программирования, которые выражены через остальные неизвестные, называются:
    1. свободными;
    2. базисными;
    3. небазисными.
  1. Правильным отсечением в задаче целочисленного программирования называется дополнительное ограничение, обладающее свойством:
    1. оно должно быть линейным;
    2. оно должно отсекать хотя бы одно целочисленное решение;
    3. оно не должно отсекать найденный оптимальный нецелочисленный план.
  1. Какой из методов целочисленного программирования является комбинированным:
    1. симплекс-метод;
    2. метод Гомори;
    3. метод ветвей и границ.
  1. Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления:
    1. отсутствие последействия;
    2. наличие обратной связи;
    3. управление зависит от бесконечного числа переменных.
  1. Вычислительная схема метода динамического программирования:
    1. зависит от способов задания функций;
    2. зависит от способов задания ограничений;
    3. связана с принципом оптимальности Беллмана.
  1. Какую задачу можно решить методом динамического программирования:
    1. транспортную задачу;
    2. задачу о замене оборудования;
    3. принятия решения в конфликтной ситуации.
  1. Метод скорейшего спуска является:
    1. методом множителей Лагранжа;
    2. градиентным методом;
    3. методом кусочно-линейной аппроксимации.
  1. Множители Лагранжа в экономическом смысле характеризуют:
    1. доход, соответствующий плану;
    2. издержки ресурсов;
    3. цену (оценку) ресурсов.
  1. Функция нескольких переменных называется сепарабельной, если она может быть представлена в виде:
    1. суммы функций одной переменной;
    2. произведения функций нескольких переменных;
    3. суммы выпуклых функций.
  1. Платежной матрицей называется матрица, элементами которой являются:
    1. годовые прибыли отраслевых предприятий;
    2. выигрыши, соответствующие стратегиям игроков;
    3. налоговые платежи предприятий.
  1. Верхней ценой парной игры является:
    1. гарантированный выигрыш игрока А при любой стратегии игрока В;
    2. гарантированный выигрыш игрока В;
    3. гарантированный проигрыш игрока В.
  1. Чистой ценой игры называется:
    1. верхняя цена игры;
    2. нижняя цена игры;
    3. общее значение верхней и нижней ценой игры.
  1. Возможно ли привести матричную игру к задаче линейного программирования:
    1. возможно;
    2. невозможно;
    3. возможно, если платежная матрица единичная.
  1. Кооперативные игры – это игры:
    1. с нулевой суммой;
    2. со смешанными стратегиями;
    3. допускающие договоренности игроков.
  1. Какие математические методы можно применять для принятия хозяйственных решений в условиях неопределенности:
    1. линейного программирования;
    2. массового обслуживания;
    3. динамического программирования.
  1. Главными элементами сетевой модели являются:
    1. игровые ситуации и стратегии;
    2. состояния и допустимые управления;
    3. события и работы.
  1. В сетевой модели не должно быть:
    1. контуров и петель;
    2. собственных векторов;
    3. седловых точек.
  1. Критическим путем в сетевом графике называется:
    1. самый короткий путь;
    2. самый длинный путь;
    3. замкнутый путь.
  1. Математической основой методов сетевого планирования является:
    1. аналитическая геометрия;
    2. теория электрических цепей;
    3. теория графов.
  1. Какая из данных экономико-математичеких моделей является однофакторной:
    1. модель материализованного технического прогресса;
    2. модель расширенного воспроизводства;
    3. модель естественного роста.

Вопросы с ответами по дисциплине «математические методы в экономике»

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




Комментариев пока нет!

Поделитесь своим мнением