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

1.  Объясните термин «Линейное программирование».

Наука о методах исследования и отыскания макс. и мин. лин. функций, на неизвестные которых наложены лин. ограничения, т. о. ЗЛП относится к задачам на условный экстремум функции.

2.  Перечислите этапы принятия решения.

1)  Сбор, изучение информации о проблемной ситуации, вербальное описание проблемы.

2)  Построение мат модели.

3)  Решение экономико-математической модели на компьютере.

4)  Анализ полученных результатов: если результаты неудовлетворительны, то переход к п. 2, иначе – принимается решение.

3.  Напишите ЭММ задачи о смесях

4.  Какая модель ЛП называется стандартной, запишите эту модель в векторной форме.

5.  Запишите стандартную модель ЛП в алгебраической (подробной) форме.

6.  Дайте определение оптимального плана задачи ЛП.

Вектор называется оптимальным планом задачи ЛП, если для любого вектора Х из допустимого множества выполняется неравенство.

7.  Может ли задача ЛП иметь бесконечное число оптимальных планов? Дайте геометрическую интерпретацию ответа.

Да: С(А)=С(В)=С(Х*), Х*Î[A, B] + рисунок!!!

8.  Может ли задача ЛП иметь ровно 2 оптимальных плана?

Нет

9.  Перечислите случаи, когда задача ЛП может не иметь решения.

1) Д=Æ, 2) С(х) неограниченна на мн-ве Д

10.  Какая модель ЛП называется канонической. Запишите ее в векторной и алгебраической (подробной) форме.

Векторная:

Алгебраическая:

11.  Дайте определение допустимого множества стандартной задачи и его геометрическую интерпретацию.

Множество векторов называется множеством допустимых планов стандартной задачи или допустимым множетсвом + рис-к!!!

12.  Дайте содержательную интерпретацию дополнительных переменных.

— неиспользованное количество i-го ресурса при реализации производственного плана.

13.  Какова роль градиента функции в графическом решении задачи ЛП.

Указывает направление наиболее быстрого возрастания функции.

14.  Почему в ЗЛП знаки ограничений нестрогие («≥» или «£»)

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

15.  Определение носителя допустимого плана.

Носителем плана X называется множество индексов .

16.  Как определяется носитель псевдоплана.

Носителем псевдоплана X называется множество индексов .

17.  Что общего между планом и псевдопланом канонической модели ЛП.

Компоненты плана удовлетворяют ограничениям канонической задачи Ax=b.

18.  Чем отличаются базисный план и псевдоплан.

Компоненты базисного плана xj>=0. Компоненты псевдоплана м. б. любые, в том числе и отрицательные.

19.  Смысл элементов технологической матрицы в многопродуктовой модели.

aij — кол-во i-го ресурса для производства j-го продукта, .

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

aij — кол-во i-го ресурса для производства единицы продукта по технологии j,

21.  Определение базисного плана.

Пусть — допустимый план ЗЛП и s — его носитель. Если векторы — линейно независимы, то план X – базисный допустимый план.

22.  Сформулируйте признак оптимальности базисного плана.

Пусть вектор — БДП ЗЛП. Если числа , то X0 – оптимальный план.

23.  Сколько положительных компонент может быть в базисном плане.

Положительных компонент в базисном плане м. б. < m (число уравнений).

24.  Что такое мощность носителя плана?

Мощность носителя плана X или — число положительных компонент плана X.

Симплекс-метод решения ЗЛП

25.  Что означает факт невозможности преобразования с/таблицы с помощью алгоритма с/метода.

Найден оптимальный план, или D – неограниченный многогранник, т. е. С(х) неограниченна на D.

26.  Что означает факт невозможности преобразования с/таблицы с помощью алгоритма двойственного с/метода.

Найден оптимальный план, или D=Æ.

27.  В каком случае преобразование с/таблицы с помощью с/метода оказывается невозможным.

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

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

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

29.  Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется с/метод.

, , — ведущий элемент

30.  Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется двойственный с/метод.

, , — ведущий элемент

Элементы теории двойственности

31.  Верно ли, что двойственная задача к стандартной имеет канонический вид, а двойственная задача к канонической имеет стандартный вид.

Нет.

32.  Напишите двойственную задачу к следующей задаче ЛП: AX=B, X>=0, C(X)® MIN

B(Y) ® Max

АтY£C

33.  Напишите двойственную задачу к следующей задаче ЛП:AX>=B, C(X) ® MAX

B(y) ®Max

-АтY=C

Y³0

34.  Сколько ограничений и неизвестных в двойственной задаче.

Ограничений столько, сколько переменных в прямой (исходной) задаче (n).

Неизвестных столько, сколько ограничений в прямой (исходной) задаче (m).

35.  Сколько ограничений-равенств в прямой задаче ЛП, если все переменные двойственной задачи неотрицательны.

Ограничений – равенств в прямой задаче нет.

36.  Известен план прямой задачи и план двойственной задачи. Что можно сказать о разрешимости этих задач; аргументируйте ответ.

По первой теореме двойственности если одна из пары двойственных задач разрешима, то разрешима и другая (имеет оптимальный план). Причем если Х* — оптимальный план, Y* — оптимальный план => C(X*)=B(Y*)

37.  Пусть Х – план прямой задачи, а У – план двойственной задачи. Что следует из равенства С(Х) = В(Y)?

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

38.  Пусть выполняется равенство С(Х) = В(Y), причем известно, что Х – неоптимальный план прямо задачи; что можно сказать о векторе Y?

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

39.  Сформулируйте первую теорему двойственности (теорему разрешимости).

Если одна из задач дв. пары разрешима, то др. задача разрешима, причем значение целевых функций на оптимальных планах прямой и двойственной задач совпадают, если Х* — оптимальный план (1), Y* — оптимальный план (2), то С(Х*)=b(Y*).

Если С(х) одной из пары двойственных задач неограниченна на Д, то Д другой задачи – пусто.

Док-во: Пусть D2¹Æ. Тогда существует по крайней мере один план yÎD2. Возьмём любой план xÎD1. На основании Леммы 1: , следовательно ц. ф. C(x) – ограничена, а по условию теоремы , ч. т.д.

40.  Сформулируйте теорему о планах двойственных задач.

D1 – допустимое мн-во (1), D2 — допустимое мн-во (2)

Если XD1, YD2 => C(X)<В(Y).

Док-во: , ч. т.д.

41.  Дайте экономическую интерпретацию равенства Х(Ат Y– С) = 0

Если Xj>0, то Ат Y= Сj, если j-ый тех-ий способ исп-ся в произ-ве, то «цены» на ресурсы () д. б. такими, чтобы суммарная стоим-ть ресурсов, идущих на изгот-ние 1 шт продукции, производимой j-ым тех-им способом, была равна Сj-ой стоим 1 шт созданного этим способом продукта. Для остальных способов, не вошедших в опт-ый план, никаких требований к «ценам» не предъявляется.

Если Ат Y> Сj, то Xj=0. В этом случае стоимостные оценки ресурсов таковы, что суммарные затраты на произ-во 1 шт продукции j-ым тех-им способом строго больше стоимости продукта, созданного этим способом. Естественно, что этот способ не используется в производстве, он неэффективен и не входит в опт-ый план.

Послеоптимизационный анализ

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

Номенклатура (состав) выпускаемых продуктов, которые входят в план производства; Перечень дефицитных и избыточных ресурсов;

43.  Каким образом формализуется понятие структуры плана в теории ЛП.

Математическим эквивалентом структуры плана является носитель плана.

44.  Сколько оптимальных базисных планов с одинаковой структурой может быть у задачи ЛП.

Один.

45.  Сколько интервалов устойчивости ассоциируется с оптимальным планом.

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

46.  Дайте определение интервала устойчивости.

Интервал изменения количества ресурсов, кот. не влияет на структуру opt плана

47.  В чем практическое значение интервала устойчивости.

Определяет интервал изменения ресурсов, не влияющий на структуру opt плана.

48.  Сколько интервалов оптимальности ассоциируется с оптимальным планом.

Для каждого коэф. ц. ф. свой интервал оптимальности.

49.  Дайте определение интервала оптимальности.

Интервал изменения значения коэффициентов ц. ф., при котором оптимальное решение остаётся неизменным

50.  В чем практическое значение интервала оптимальности.

Определяет интервал изменения значения коэффициентов ц. ф., при котором оптимальное решение остаётся неизменным

51.  Какие ресурсы в теории ЛП называются дефицитными, а какие – избыточными.

xn+i, i=1…m, если xn+i = 0 => i-тый ресурс — дефицитный, xn+i>0, => i-тый ресурс — избыточный

52.  Как вычисляется нижняя граница интервала устойчивости для избыточного ресурса (а верхняя граница?).

Δbk/ниж=-x*n+k, Δbk/верх=∞; [bk+ Δbk/ниж; ∞] – интервал устойчивости

53.  Как вычисляется верхняя граница интервала оптимальности для коэффициента при небазисной переменной оптимального плана (а нижняя?).

Опт-ый план не изм-ся, если:

54.  Дайте качественную экономическую хар-ку двойственных оценок.

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

55.  Дайте количественную хар-ку двойственных оценок как меры дефицитности ресурсов.

Δn+k=0 => k-й ресурс избыточен

Δn+k>0 => k-й ресурс дефицитен

56.  Что такое маргинальные оценки?

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