Задача линейного программирования называется канонической если система ограничений включает в себя – Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления: a) отсутствие последействия

Лекция — V1: Линейное программирование

V2: Основные понятия и определения линейного программирования

 

I:

S: Автором линейного программирования является:

+: Л. Канторович

-: Г. Фельдман

-: В. Немчинов.

 

I:

S: Ученый, который разработал метод линейного программирования и стал лауреатом Нобелевской премии:

+: Л.В.Канторович.

-: Н.Д.Кондратьев

-: В.В.Новожилов

 

I:

S: Какое уравнение называется характеристическим уравнением матрицы А:

-: (E – A)*X = Y

-: A*X = B

+:

 

I:

S: Множество n – мерного арифметического точечного пространства называется выпуклым, если:

+: вместе с любыми двумя точками А и В оно содержит и весь отрезок АВ

-: счетно и замкнуто

-: равно объединению нескольких конечных множеств

 

I:

S: Какая задача является задачей линейного программирования:

-: управления запасами

+: составление диеты

-: формирование календарного плана реализации проекта

 

I:

S: Задача линейного программирования называется канонической, если система ограничений включает в себя:

-: только неравенства

-: равенства и неравенства

+: только равенства

 

I:

S: Тривиальными ограничениями задачи линейного программирования называются условия:

-: ограниченности и монотонности целевой функции

+: не отрицательности всех переменных

-: не пустоты допустимого множества

 

I:

S: Если в задаче линейного программирования допустимое множество не пусто и целевая функция ограничена, то:

-: допустимое множество не ограничено

-: оптимальное решение не существует

+: существует хотя бы одно оптимальное решение

 

I:

S: Какое из следующих утверждений истинно?

А) существуют задачи целочисленного линейного программирования, не имеющие допустимых решений даже в тех случаях, когда множество допустимых решений соответствующей линейной задачи не пусто

В) не существует задач целочисленного линейного программирования, не имеющих допустимых решений в случаях, когда множество допустимых решений соответствующей линейной задачи не пусто

-: A– нет, B- нет

-: A– да, B– да

-: A– нет, B– да

+: А – да, В – нет

 

I:

S: Булевское программирование – это целочисленное …

+: линейное программирование, где переменные могут принимать всего лишь два значения — 0 и 1

-: нелинейное программирование, где переменные могут принимать всего лишь два значения — 0 и 1

-: квадратичное программирование, где переменные могут принимать всего лишь два значения — 0 и 1

-: линейное программирование, где переменные могут принимать всего лишь два значения — -1 и +1

 

I:

S: Задача линейного программирования может рассматриваться как…

+: частный случай задачи выпуклого программирования

-: частный случай задачи дискретного программирования

-: обобщение задачи выпуклого программирования

-: частный случай задачи стохастического программирования

 

I:

S: Задача коммивояжера относится к задачам

-: квадратичного программирования

-: выпуклого программирования

-: математического анализа

+: Булевского программирования

 

I:

S: Область допустимых решений задачи линейного программирования имеет вид:

 

Тогда максимальное значение функции равно …

-: 26

-: 32

+: 30

-: 24

 

I:

S: Область допустимых решений задачи линейного программирования имеет вид:

Тогда максимальное значение функции достигается в точке …

-: C

+: B

-: D

-: A

 

I:

S: Область допустимых решений задачи линейного программирования имеет вид:

Тогда максимальное значение функции равно …

-: 26

+: 24

-: 18

-: 12

 

I:

S: Область допустимых решений задачи линейного программирования имеет вид:

Тогда максимальное значение функции достигается в точке …

 

-: C

+: B

-: A

-: E

 

I:

S: Область допустимых решений задачи линейного программирования имеет вид:

Тогда минимальное значение функции равно …

-: – 16

-: – 18

-: – 22

+: – 34

 

I:

S: Минимальное значение целевой функции при ограничениях

равно …

-: – 2

+: – 6

-: 12

-: – 8

 

I:

S: Максимальное значение целевой функции при ограничениях

равно …

+: 22

-: 18

-: 24

-: 16

 

I:

S: Максимальное значение целевой функции при ограничениях

равно …

+: 14

-: – 1

-: 24

-: – 6

 

I:

S: Минимальное значение целевой функции при ограничениях

равно …

+: – 13

-: – 11

-: – 10

-: – 16

 

I:

S: Область допустимых решений задачи линейного программирования имеет вид:

Тогда максимальное значение функции равно…

-: 18

-: 20

-: 23

+: 21

 

I:

S: Максимальное значение целевой функции при ограничениях:

равно…

-: 6

-: 12

+: 18

-: 20

 

I:

S: При использовании градиента необходимое условие экстремума записывается в виде…

-: grad z(X)≤0

-: grad z(X)≠0

+: grad z(X)=0

-: grad z(X)≥0

 

I:

S: Рекуррентная формула метода градиента для минимизации целевой функции имеет вид

+:

 

-:

-:

-:

 

I:

S: Вектор-градиент в некоторой точке определяется как вектор, компонентами которого являются…

-: прямые производные этой функции в точке

+: частные производные первого порядка этой функции в точке

-: частные производные второго порядка этой функции в точке

-: частные производные третьего порядка этой функции в точке

 

I:

S: Выделяются две группы методов нулевого порядка:

+: детерминированные и случайные

-: однопараметрические и многопараметрические

-: конечные и асимптотические

-: однокритериальные и многокритериальные

 

I:

S: Градиентом функции n переменных z(X) называется вектор, компонентами которого являются…

-: прямые производные первого порядка этой функции в точке

-: частные производные третьего порядка этой функции в точке

+: частные производные первого порядка этой функции в точке

-: частные производные второго порядка этой функции в точке

 

I:

S: Направление градиента в точке X совпадает с направлением

-: знакопостоянства целевой функции в этой точке

-: постоянства целевой функции в этой точке

+: наискорейшего возрастания целевой функции в этой точке

-: наискорейшего убывания целевой функции в этой точке

 

V2: Симплексный метод решения задачи линейного программирования

 

I:

S: Симплекс-метод предназначен для решения задачи линейного программирования

-: в стандартном виде

+: в каноническом виде

-: в тривиальном виде

 

I:

S: Неизвестные в допустимом виде системы ограничений задачи линейного программирования, которые выражены через остальные неизвестные, называются :

-: свободными

+: базисными

-: небазисными

 

I:

S: Симплексный метод – это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной точки (базисного решения) к другой. При этом значение целевой функции:

+: улучшается

-: уменьшается

-: ухудшается

-: увеличивается

 

I:

S: Базисным решением является одно из возможных решений, находящихся:

-: в пределах области допустимых значений

+: в вершинах области допустимых значений

-: на границах области допустимых значений

-: за пределами области допустимых значений

 

I:

S: Симплекс-метод основан на проверке на оптимальность:

-: ограничений симплекса

-: области допустимых решений симплекса

-: сторон симплекса

+: вершины за вершиной симплекса

 

I:

S: Симплекс это:

-: выпуклый многоугольникв n- мерном пространстве с n вершинами не лежащими в одной гиперплоскости

+: выпуклый многоугольникв n- мерном пространстве с n+1 вершинами не лежащими в одной гиперплоскости

-: выпуклый многоугольникв n- мерном пространстве с n+1 вершинами лежащими в одной гиперплоскости

-: выпуклый многоугольникв n- мерном пространстве с n вершинами не лежащими в одной гиперплоскости

 

I:

S: Множество переменных, образующих единичную подматрицу, принимается за начальное базисное решение:

-: значения этих переменных равны свободным членам. Все остальные вне базисные переменные не равны нулю.

-: значения этих переменных равны нулю. Все остальные вне базисные переменные равны свободным членам.

-: значения этих переменных равны нулю. Все остальные вне базисные переменные не равны нулю.

+: значения этих переменных равны свободным членам. Все остальные вне базисные переменные равны нулю.

V2: Двойственность в линейном программировании

 

I:

S: Как называются переменные двойственной задачи?

 

-: дополнительными переменными

+: объективно обусловленными переменными

-: объективно обусловленными оценками

-: искусственными переменными

V2: Транспортная задача

 

I:

S: Транспортная задача формулируется следующим образом: Найти такие объемы перевозок для каждой пары «поставщик-потребитель», чтобы 1) мощности всех поставщиков были использованы полностью; 2) спрос всех потребителей был удовлетворен:

-: 3) суммарные затраты на перевозки были минимальные

+: 3) суммарные затраты на перевозки были максимальные

-: 3) мощности всех поставщиков и мощности всех потребителей должны быть равны

-: 3) мощности всех поставщиков должны быть больше мощностей всех потребителей

 

I:

S: Целевая функция транспортной задачи обычно записывается так, что бы:

-: суммарные затраты стремились к нулю

+: суммарные затраты стремились к минимуму

-: суммарные затраты стремились к максимуму

-: суммарная прибыль стремилась к максимуму нулю

 

I:

S: Ограничения транспортной задачи представляет собой:

-: систему неравенств

-: систему неравенств и уравнений

-: область допустимых решений

+: систему уравнений

 

I:

S: Коэффициенты в системе ограничений транспортной задачи представляет собой:

-: равны единице

— : большие нуля

+: равны единице или нулю

-: меньше или равны нулю

 

I:

S: Метод северо-западного угла предполагает планирование поставок в:

+: верхнюю левую ячейку

-: верхнюю правую ячейку

-: нижнюю левую ячейку

-: нижнюю правую ячейку

 

I:

S: Транспортная задача

будет закрытой, если …

-:,

-:,

+:,

-:,

 

I:

S: Транспортная задача

будет закрытой, если …

+:,,

-:,,

-:,,

-:,,

 

I:

S: Транспортная задача

будет открытой, если…

+: a=40, b=30

-: a=13, b=23

-: a=100, b=110

-: a=30, b=40

 

I:

S: Транспортная задача будет закрытой, если

-: a=35, b=20

-: a=35, b=15

-: a=35, b=30

+: a=35, b=25

 

I:

S: Пусть имеется два поставщика мощностью 80 и 90 и три потребителя мощностью 40; 50 и 60. Затраты на перевозки от первого поставщика к потребителям соответственно равны 2, 5, 6; от второго 4, 7, 3. Определите суммарные затраты на перевозки методом наименьших затрат.

-: 620

+: 530

-: 760

-: 480

 

I:

S: Пусть имеется два поставщика мощностью 80 и 90 и три потребителя мощностью 40; 50 и 60. Затраты на перевозки от первого поставщика к потребителям соответственно равны 2, 5, 6; от второго 4, 7, 3. Определите суммарные затраты на перевозки при оптимальном плане перевозок.

-: 420

-: 500

+: 530

-: 570

 

I:

S: Пусть имеется два поставщика мощностью 80 и 90 и три потребителя мощностью 40; 50 и 60. Затраты на перевозки от первого поставщика к потребителям соответственно равны 2, 5, 6; от второго 4, 7, 3. Сколько продукции останется для фиктивных потребителей при оптимальном плане перевозок.

+: 1-го – 0; 2 – го 20

-: 1-го – 20; 2 – го 0

-: 1-го – 10; 2 – го 10

-: 1-го – 5; 2 – го 15

 

I:

S: Пусть имеется два поставщика мощностью 80 и 90 и три потребителя мощностью 40; 50 и 60. Затраты на перевозки от первого поставщика к потребителям соответственно равны 2, 5, 6; от второго 4, 7, 3. Как изменятся суммарные затраты, если затраты на перевозку единицы груза от второго поставщика ко второму потребителю снизятся на 1?

-: — 1

+: — 10

-: — 40

-: — 20

 

I:

S: Транспортная задача решается методом потенциалов.

 ui
 
 u2
  u3
vjv1v2v3 

Тогда значение потенциала v3 равно…

-: 24

-: 7

-: 60

+: 11

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

 

I:

S: Какое из следующих утверждений истинно?

1-ый алгоритм Гомори используется при решении

А) целочисленной задачи линейного программирования

В) частично целочисленной задачи линейного программирования

-: A – да, B – да

-: A – нет, B – да

-: A – нет, B — нет

+: А – да, В – нет

 

I:

S: Правильным отсечением в задаче целочисленного программирования называется дополнительное ограничение, обладающее свойством:

+: оно должно быть линейным

-: оно должно отсекать хотя бы одно целочисленное решение

-: оно не должно отсекать найденный оптимальный нецелочисленный план

 

I:

S: Какой из методов целочисленного программирования является комбинированным

-: симплекс-метод

-: метод Гомори

+: метод ветвей и границ

 

I:

S: Какое из следующих утверждений истинно?

Задача математического программирования, в которой переменные могут принимать любые целочисленные значения называется…

А) задачей целочисленного программирования,

В) задачей Булевского программирования

+: A – да, B — нет

-: A – да, B – да

-: A – нет, B – нет

-: A – нет, B — да

 

I:

S: Какое из следующих утверждений истинно?

Задача о коммивояжере относится к задачам

А) дискретного программирования

В) целочисленного программирования

-: A – нет, B — нет

+: А – да, В – да

-: A – да, B – нет

-: A – нет, B – да

 

I:

S: Алгоритмы методов отсечения разработаны для решения…

+: полностью или частично целочисленных и дискретных задач линейного программирования

-: полностью целочисленных задач нелинейного программирования

-: полностью целочисленных задач линейного программирования

-: полностью целочисленных задач выпуклого программирования

 

I:

S: В алгоритме метода ветвей и границ на 1-м шаге находится решение задачи линейного программирования

-: с учетом целочисленности

-: без учета не целочисленных ограничений

+: без учета целочисленности

-: без учета всех ограничений

 

I:

S: В алгоритме метода ветвей и границ на 2-м шаге…

-: находится решение задачи линейного программирования без учета всех ограничений

-: находится решение задачи линейного программирования без учета целочисленности

+: составляются дополнительные ограничения на дробную компоненту плана

-: находится решение задачи нелинейного программирования без учета целочисленности

 

I:

S: В алгоритме метода ветвей и границ на 3-м шаге…

-: находится решение задачи линейного программирования без учета целочисленности

-: составляются дополнительные ограничения на дробную компоненту плана

-: находится решение задачи линейного программирования без учета всех ограничений

+: находим решение двух задач с ограничениями на компоненту

 

I:

S: В алгоритме метода ветвей и границ на 4-м шаге…

-: находится решение задачи нелинейного программирования без учета целочисленности

-: находится решение задачи линейного программирования без учета всех ограничений

+: строятся в случае необходимости дополнительные ограничения и получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи

-: находится решение задачи линейного программирования без учета целочисленности

 

I:

S: В задачах целочисленного программирования неизвестные параметры могут принимать…

-: только положительные значения

+: только целочисленные значения

-: любые значения

-: только отрицательные значения

 

I:

S: Общая формула построения правильного отсечения для всех алгоритмов

запишется в следующем виде:

-:

 

-:

 

+:

 

-:

 

 

I:

S: Метод ветвей и границ является…

+: нерегулярным

-: расходящимся

-: регулярным

-: асимптотическим

 

I:

S: Правильные отсечения в методах отсечения должны быть…

-: положительно определенными

+: линейными

-: нелинейными

-: отрицательно определенными

www.ronl.ru

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

1. Что является объектом и языком исследования в экономико-математическом моделировании:

A) различные типы производственного оборудования и методы его конструирования;

B) экономические процессы и специальные математические методы;

C) компьютерные программы и языки программирования.

2. Какое матричное уравнение описывает замкнутую экономическую модель Леонтьева:

A) (E – A)*X = C;

B) A*X = X;

C) A*X = E.

3. Какое допущение постулируется в модели Леонтьева многоотраслевой экономики:

A) выпуклость множества допустимых решений;

B) нелинейность существующих технологий;

C) линейность существующих технологий.

4. Какое уравнение называется характеристическим уравнением матрицы А:

A) (E – A)*X = Y;

B) A*X = B;

C) |A – lE| = 0.

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. Неизвестные в допустимом виде системы ограничений задачи линейного программирования, которые выражены через остальные неизвестные, называются:

A) свободными;

B) базисными;

C) небазисными.

12. Правильным отсечением в задаче целочисленного программирования называется дополнительное ограничение, обладающее свойством:

A) оно должно быть линейным;

B) оно должно отсекать хотя бы одно целочисленное решение;

C) оно не должно отсекать найденный оптимальный нецелочисленный план.

13. Какой из методов целочисленного программирования является комбинированным:

A) симплекс-метод;

B) метод Гомори;

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. Возможно ли привести матричную игру к задаче линейного программирования:

A) возможно;

B) невозможно;

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) модель естественного роста.

ОТВЕТЫ

1

B

11

B

21

C

2

B

12

A

22

С

3

C

13

С

23

A

4

C

14

A

24

C

5

A

15

С

25

B

6

B

16

B

26

C

7

C

17

B

27

A

8

B

18

C

28

B

9

C

19

A

29

C

10

B

20

B

30

C

sdalna10.com

ЭММ(теория)ответы на тест

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

  1. Что является объектом и языком исследования в экономико-математическом моделировании:

  1. различные типы производственного оборудования и методы его конструирования;

  2. экономические процессы и специальные математические методы;

  3. компьютерные программы и языки программирования.

  1. Какое матричное уравнение описывает замкнутую экономическую модель Леонтьева:

  1. (E – A)*X = C;

  2. A*X = X;

  3. A*X = E.

  1. Какое допущение постулируется в модели Леонтьева многоотраслевой экономики:

    1. выпуклость множества допустимых решений;

    2. нелинейность существующих технологий;

    3. линейность существующих технологий.

  1. Какое уравнение называется характеристическим уравнением матрицы А:

    1. (E – A)*X = Y;

    2. A*X = B;

    3. |A — 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

b

11

b

21

c

2

b

12

a

22

с

3

c

13

с

23

a

4

c

14

a

24

c

5

a

15

с

25

b

6

b

16

b

26

c

7

c

17

b

27

a

8

b

18

c

28

b

9

c

19

a

29

c

10

b

20

b

30

c

7

studfiles.net

ЭММ тест

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

  1. Что является объектом и языком исследования в экономико-математическом моделировании:

  1. различные типы производственного оборудования и методы его конструирования;

  2. экономические процессы и специальные математические методы;

  3. компьютерные программы и языки программирования.

  1. Какое матричное уравнение описывает замкнутую экономическую модель Леонтьева:

  1. (E – A)*X = C;

  2. A*X = X;

  3. A*X = E.

  1. Какое допущение постулируется в модели Леонтьева многоотраслевой экономики:

    1. выпуклость множества допустимых решений;

    2. нелинейность существующих технологий;

    3. линейность существующих технологий.

  1. Какое уравнение называется характеристическим уравнением матрицы А:

    1. (E – A)*X = Y;

    2. A*X = B;

    3. |A — 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

b

11

b

21

c

2

b

12

a

22

с

3

c

13

с

23

a

4

c

14

a

24

c

5

a

15

с

25

b

6

b

16

b

26

c

7

c

17

b

27

a

8

b

18

c

28

b

9

c

19

a

29

c

10

b

20

b

30

c

7

studfiles.net

Виды задач линейного программирования

Линейное программирование – метод решения задач оптимизации.

В первых оптимизационных задачах требовалось выяснить, сколько различных изделий нужно произвести, чтобы получить максимальный доход, если известно количество ресурсов (сырья, рабочего времени, оборудования) и цены, по которым можно реализовать готовые изделия. Другой вид задач – выяснить, при каких условиях свести расходы к минимуму (это, например, задача о питании). Таким образом, общая задача линейного программирования – это задача, в которой требуется найти максимум или минимум (оптимум) функции, называемой функцией цели, при ограничениях, заданных системой линейных неравенств или уравнений.

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

Функция цели в задаче линейного программирования обычно записывается так:

.

Или в сокращённом виде с сигмой:

.

Можно встретить обозначение целевой функции и через C, и через F.

Система ограничений в задаче линейного программирования в канонической форме записывается так:

.

Или в сокращённом виде:

И система ограничений, и целевая функция имеют линейный характер, то есть содержат переменные только в первой степени.

Канонической задачей линейного программирования называется задача, в которой, как было показано выше, требуется найти максимум целевой функции при ограничениях, заданных системой линейных уравнений.

Задачей линейного программирования в стандартной, или, как говорят иначе, нормальной форме, называется задача, в которой требуется найти максимум целевой функции при ограничениях, заданных системой неравенств одного смысла, то есть с одинаковым знаком, и этот знак — «меньше или равно», причём действует также условие неотрицательности переменных. Если в задаче линейного программирования, заданной в стандартной форме, требуется найти минимум целевой функции, то система ограничений состоит из системы неравенств со знаком «больше или равно».

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

Если все или некоторые ограничения в системе заданы неравенствами, то задачу можно свести к канонической путём преобразования неравенств в уравнения.

Множество чисел (запись последовательности иксов), удовлетворяющих системе ограничений, называется решением этой системы. Решение системы также часто называется планом, и немного реже – программой, но именно отсюда и пошло название «линейное программирование».

Оптимальным решением задачи линейного программирования называется решение системы, при которых функция цели обращается в максимум или минимум, в зависимости от условия задачи, или в общем смысле – в оптимум.

Решение задачи линейного программирования называется вырожденным, если в нём некоторые переменные равны нулю. В противном случае решение является невырожденным.

Как было отмечено выше, переменные в задаче линейного программирования чаще всего должны быть неотрицательными, но, как мы уже усвоили, общая форма записи задачи допускает и отрицательные значения переменных. Если переменные (икс с индексом) означают наличность фирмы, которую требуется направить на различные нужды, но по некоторым статьям фирма должна денег больше, чем имеет, то тогда можно допустить, что соответствующие переменные – отрицательные.

К приведённым определениям следует добавить следующее правило, имеющее практическое значение. Для того чтобы решение задачи имело смысл, ограничения задачи линейного программирования должны быть заданы в одних и тех же единицах. Например, если фигурантами задачи линейного программирования являются трудодни, то необходимо определить, идёт ли речь о трудоднях в неделю или в месяц и определённого уточнения придерживаться на всём протяжении решения задачи.

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

Для этого, как следует из предыдущего параграфа, надо так представить предметную область, чтобы получить следующие атрибуты задачи линейного программирования.

Целевая функция. Её нужно максимизировать или минимизировать. Для того, чтобы функцию максимизировать, переменные, являющиеся её слагаемыми, должны принимать как можно большие значения в соответствии с условиями задачи. При минимизации — наоборот, меньшие. Обычно целевая функция выражает доходы или расходы.

Переменные. Каждая переменная, как правило, означает запасы одного из производственных факторов — вида сырья, времени, рабочей силы, технологических возможностей или чего-либо другого.

Ограничения. Очень просто. Например, в каждом уравнении (неравенстве) заданы ограничения перечисленных выше или других запасов, используемых для производства определённого вида продукции.

Пример 1. Схема задачи использования сырья.

Сформулировать для решения как задачи линейного программирования следующую задачу.

Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья — соответственно , , , единицы.

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

Решение. Для удобства сначала все данные запишем в виде таблицы:

Тогда на основании таблицы запишутся неравенства (ограничения):

В самом деле, для изготовления каждой единицы продукции необходимо единиц сырья , а для изготовления единиц требуется единиц сырья . Для изготовления единиц продукции требуется единиц сырья . Так как запасы сырья составляют , то расход не может превышать . В результате получим первое неравенство:

Из остальных строк таблицы составим ещё 3 неравенства системы.

Доход от реализации единиц продукции по у. е. за каждую единицу составляет у. е. Аналогично доход от реализации единиц продукции по у. е. за каждую единицу составит у. е. Тогда суммарный доход от реализации двух видов продукции и запишется в виде . В задаче требуется найти максимальный доход, то есть найти максимум функции цели .

На нашем сайте есть решение числового примера этой задачи графическим методом.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.


Пример 2. Схема задачи о смесях.

Сформулировать для решения как задачи линейного программирования следующую задачу.

Требуется найти наиболее дешёвый набор из доступных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в свойм составе n различных компонент в определённых количествах, а сами компоненты являются составными частями m исходных материалов. Для упрощения примем, что n=3 и m=4. Пусть стоимость одной единицы материала соответственно составляет , , , . В свою очередь необходимое количество каждой из компонент в смеси составляет соответственно , , .

Решение. Строим таблицу:

Коэффициенты aij показывают количество j-й компоненты в единице i-го материала K1. Требуется получить смесь с заданными свойствами при наименьших затратах на приобретение материалов.

Запишем задачу в виде математических соотношений. Обозначим через xi количество материалов i-го вида, входящего в смесь. Тогда задача сведётся к отысканию минимума функции

при ограничениях

Одним из частных случаев общей задачи о смесях служит задача о питании. К ней сейчас же и перейдём.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.


Пример 3. Схема задачи о питании.

Сформулировать для решения как задачи линейного программирования следующую задачу.

Для нормального функционирования организма необходимо потреблять ежесуточно определённое количество питательных веществ: жиров, белков, углеводов, витаминов. Они содержатся в разных продуктах в различных количествах. Пусть стоимость одной единицы продукта соответственно составляет , , . Нужно так организовать питание, чтобы организм получал необходимое количество питательных веществ, а стоимость питания была бы наименьшей.

Решение. Строим таблицу:

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

Запишем задачу в виде математических соотношений. В задаче неизвестно количество каждого вида продукта. Поэтому обозначим количество продукта буквой , количество продукта — буквой , количество продукта — буквой .

Получим систему неравенств (ограничений):

Требуется найти найти такое неотрицательное решение системы ограничений, при котором функция цели обращалась бы в минимум.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.


Пример 4. Схема задачи об использовании мощностей оборудования.

Сформулировать для решения как задачи линейного программирования следующую задачу.

Предприятию требуется за время T выпустить N1 единиц продукции П1 и N2 единиц продукции П2. Каждый из этих двух видов продукции может производиться тремя машинами A, B, C. Составить оптимальный план работы машин, то есть найти время загрузки машин A, B, C, с тем расчётом, чтобы стоимость изготовления всей продукции предприятием оказалась минимальной.

Мощность машин задана следующей таблицей:

В этой таблице — количество единиц продукции, производимое за единицу времени.

Цена одной единицы рабочего времени на изготовление одной единицы продукции на каждой машине задана следующей таблицей:

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

Запишем задачу в виде математических соотношений. Неизвестным является время загрузки машин по производству продукции. Обозначим через время загрузки машины A по изготовлению продукции П1, через — время загрузки машины A по изготовлению продукции П2. Аналогично — время загрузки машины B по изготовлению продукции П1, — время загрузки машины B по изготовлению продукции П2, — время загрузки машины C по изготовлению продукции П1, время загрузки машины C по изготовлению продукции П2.

Машины A, B, C работают одновременно, значит если обозначим время одновременной работы всех трёх машин буквой T, то получим систему неравенств:

Машина A изготовлением продукции П1 занята единицы времени на единицы продукции. Машина B изготовлением П1 занята единицы времени по единицы продукции.

Аналогично машина C изготовлением П1 занята единицы времени, по единицы продукции и т.д. Всего нужно N1 единиц продукции П1 и N2 единицы П2.

То есть получаем ещё одну систему:

Тогда общая стоимость всей продукции запишется в виде равенства:

.

Окончательно получаем систему ограничений, состоящую из соотношений:

Задача заключается в том, чтобы найти такое неорицательное решение последней из приведённых систем, чтобы целевая функция C приняла минимальное значение.

Пример 5. Транспортная задача (схема).

Сформулировать для решения как задачи линейного программирования следующую задачу.

На двух станциях отправления и имеется соответственно и единиц некоторого груза. Этот груз следует доставить в три пункта назначения , , и в каждый из них должно быть завезено соответственно , , единиц этого груза. Стоимость перевозки одной единицы груза из пункта в пункт равна .

Составить такой план перевозок, чтобы общая стоимость всех перевозок была минимальной.

Решение. Считаем, что запас всего груза на обоих пунктах отправления равен потребности в этом грузе на всех трёх пунктах назначения, т. е.

Запишем задачу в виде математических соотношений. Количество единиц груза, отправляемых из пункта в пункт , обозначим и составим матрицу перевозок (таблицу):

В таблице выше каждая клетка для пункта назначения разделена на две части. В верхней части записана стоимость перевозки, а в нижней — количество груза. Например, в клетке (в клетке, расположенной на пересечении строки ) со столбцом ) число означает стоимость перевозки из пункта в пункт .

Тогда система ограничений запишется в виде уравнений:

Цель задачи — найти неотрицательное решение системы уравнений, при котором функция цели была минимальной.

На сайте есть статья, посвящённая решению транспортной задачи распределительным методом.

В большинстве задач линейного программирования ограничения задаются не в виде системы уравнений, а в виде системы линейных неравенств, причём возможны различные формы таких систем: левая часть меньше или равна (меньше) правой, левая часть больше или равна (больше) правой. Кроме того, система ограничений может быть смешанной: часть ограничений неравенства первого из вышеназванных типов, части — второго типа, а часть задана в виде уравнений.

Однако любую систему ограничений можно свести к системе уравнений. Для этого достаточно к левой части каждого неравенства прибавить, если система первого типа, или отнять, если система второго типа, некоторое неотрицательное число — добавочную переменную, чтобы каждое неравенство превратилось в уравнение. Эти действия называются сведением задачи линейного программирования к канонической.

Пример 6. Записать систему неравенств

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

Решение. Прибавляя к левым частям неравенств по одной дополнительной переменной, получим систему уравнений:

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

На нашем сайте также даны примеры решения задач линейного программирования графическим методом без сведения задачи к канонической и симплекс-методом с предварительным сведением задачи к канонической.

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

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

О том, что такое выпуклые множества — на уроке Системы линейных неравенств и выпуклые множества точек.

Теорема 2. Если существует, и притом единственное, оптимальное решение задачи линейного программирования, то оно совпадает с одной из угловых точек множества допустимых решений.

Эта теорема позволяет сделать вывод, что поиски оптимального решения можно ограничить перебором конечного числа угловых точек. Однако для отыскания угловых точек требуется построение области решений системы ограничений. Это построение возможно только для двух- или трёхмерного пространства, а в общем случае задача остаётся неразрешимой. Следовательно, нужно располагать каким-то аналитическим методом, позволяющим находить координаты угловых точек. Для этого понадобятся следующие две теоремы.

Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений.

Теорема 4 (обратная). Каждой угловой точке множества допустимых решений системы ограничений соответствует допустимое базисное решение.

Следствие. Если существует, и притом единственное, оптимальное решение задачи линейного программирования, то оно совпадает с одним из допустимых базисных решений системы ограничений.

Справедливость этого утверждения вытекает из теорем 2 и 4.

Итак, оптимум линейной формы нужно искать среди конечного числа допустимых базисных решений. Однако даже в простейших задачах линейного программирования (при небольших значениях m и n) нахождение оптимального решения путём рассмотрения всех базисных решений является крайне трудоёмким процессом, поскольку число базисных решений может быть весьма велико. Поэтому нужна какая-то вычислительная схема, позволяющая осуществлять переход от одного допустимого базисного решения к другому, при котором линейная форма или приблизилась к оптимуму, или, по крайней мере не изменила своего значения. Такой вычислительной схемой является, например, симплекс-метод решения задач линейного программирования.

Продолжение темы «Линейное программирование»

Поделиться с друзьями

function-x.ru

Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления: a) отсутствие последействия

1.    Задача линейного программирования называется канонической, если система ограничений включает в себя:
a)    только неравенства;
b)    равенства и неравенства;
c)    только равенства. (*ответ к тесту*)
2.    Тривиальными ограничениями задачи линейного программирования называются условия:
a)    ограниченности и монотонности целевой функции;
b)    не отрицательности всех переменных; (*ответ к тесту*)
c)    не пустоты допустимого множества.
3.    Если в задаче линейного программирования допустимое множество не пусто и целевая функция ограничена, то:
a)    допустимое множество не ограничено;
b)    оптимальное решение не существует;
c)    существует хотя бы одно оптимальное решение. (*ответ к тесту*)
4.    Симплекс-метод предназначен для решения задачи линейного программирования:
a)    в стандартном виде;
b)    в каноническом виде; (*ответ к тесту*)
c)    в тривиальном виде.
5.    Неизвестные в допустимом виде системы ограничений задачи линейного программирования, которые выражены через остальные неизвестные, называются:
a)    свободными;
b)    базисными; (*ответ к тесту*)
c)    небазисными.
6.    Правильным отсечением в задаче целочисленного программирования называется дополнительное ограничение, обладающее свойством:
a)    оно должно быть линейным; (*ответ к тесту*)
b)    оно должно отсекать хотя бы одно целочисленное решение;
c)    оно не должно отсекать найденный оптимальный нецелочисленный план.
7.    Какой из методов целочисленного программирования является комбинированным:
a)    симплекс-метод;
b)    метод Гомори;
c)    метод ветвей и границ. (*ответ к тесту*)
8.    Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления:
a)    отсутствие последействия; (*ответ к тесту*)
b)    наличие обратной связи;
c)    управление зависит от бесконечного числа переменных.

www.soloby.ru

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

Запись целевой функции и системы ограничений в различных задачах линейного программирования неодинаков: в одних задачах требуется найти минимум целевой функции, а в других – максимум; в одних случаях искомые переменные зависят от одного индекса, а в других – от двух; в одних задачах ограничения заданы в виде системы линейных неравенств, а в других – в виде системы линейных уравнений. На практике возможны также задачи, в которых часть ограничений имеет вид линейных неравенств, а часть – линейных уравнений. Также не во всех задачах может требоваться неотрицательность переменных .

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

Если в задаче линейного программирования система исходных ограничений приобретает вид уравнений типа

или

и нужно найти максимум линейной целевой функции

,

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

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

В том случае, когда нужно найти минимум функции , можно перейти к нахождению максимума функции , поскольку справедливо утверждение: .

Ограничение-неравенство исходной задачи, которое имеет вид «» , можно превратить в ограничение-уравнение путем добавления к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида «»– путем вычитания из его левой части дополнительной неотрицательной переменной.

Заметим, что количество введенных дополнительных неотрицательных переменных всегда равно количеству неравенств в исходной системе ограничений.

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

Отметим также, что если некоторая переменная не подчиняется условию неотрицательности, то ее нужно заменить двумя неотрицавтельными переменными и , приняв .

Пример. Записать в канонической форме следующую задачу линейной оптимизации: найти минимум функции при ограничениях

Решение

В данной задаче нужно найти минимум целевой функции, а система ограничений включает четыре неравенства. Для того, чтобы записать ее в канонической форме, нужно перейти от ограничений-неравенств к ограничениям-уравнениям, а также превратить целевую функцию.

Так как количество неравенств, входящих в систему ограничений задачи , равно четырем, то этот переход должен быть осуществлен с введением четырех дополнительных неотрицательных переменных. При этом во втором и четвертом неравенствах стоит знак «» , поэтому к их левой части дополнительные переменные добавляем. В первом и третьем неравенствах – знак «», значит от их левой части дополнительные переменные вычитаем.

Также превращаем целевую функцию, поменяв все знаки на противоположные, и находим ее максимум.

Таким образом, данная задача линейного программирования будет записана в следующем каноническом виде:

найти максимум функции

при ограничениях

studfiles.net