ОСНОВНЫЕ ПОНЯТИЯ, ОПРЕДЕЛЕНИЯ, МОДЕЛИ И ФОРМУЛЫ

1. Запишите ЗЛП в нормальной форме и двойственную к ней.

2. Запишите ЗЛП в канонической форме и двойственную к ней.

3. На какие две группы разбиваются основные ограничения-неравенства ЗЛП?

Ресурсные и количественные.

4. Какие ограничения относят к дефицитным? Избыточным?

Дефицитные (=) – оказывают непосредственное влияние на оптимальный план, при увеличении количества прибыль увеличивается.

Избыточные (<) – не участвуют в непосредственном формировании оптимального плана, не влияют на прибыль.

5. Какие ограничения относят к несущественным? Существенным?

Несущественные (<, >) – не оказывают влияния на формирование оптимального плана.

Существенные: (≤) – оказывают непосредственное влияние на оптимальный план, при увеличении количества прибыль увеличивается; (≥) – оказывают непосредственное влияние на оптимальный план, при увеличении количества прибыль уменьшается.

6. Что такое «чувствительность целевой функции к изменению правых частей»?

– скорость изменения целевой функции в зависимости от изменения i-щй правой части.

7. Запишите формулу, по которой находят оптимальный двойственный план y*.

8. Что такое «устойчивость оптимального плана к изменению правых частей»?

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

9. Какая транспортная задача называется открытой? Закрытой?

Транспортная задача называется закрытой, если выполняется условие баланса (a_i – запасы продукции у каждого поставщика, b_i – потребность каждого потребителя)

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

10. Запишите условие баланса для транспортной задачи.

(a_i – запасы продукции у каждого поставщика, b_i – потребность каждого потребителя)

11. Каким образом открытая транспортная задача приводится к закрытой?

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

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

12. Что называется планом транспортной задачи? Оптимальным планом?

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

13. Что такое «заполненная клетка транспортной таблицы»? «Пустая клетка»?

Заполненная клетка – это клетка с ненулевым объёмом перевозок . Пустая клетка – это клетка с нулевым объёмом перевозок , который не заносится в клетку.

14. Что такое «фиктивно заполненная клетка транспортной таблицы»?

Это клетка, в которую занесён объём перевозок .

15. Что называют циклом транспортной задачи?

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

16. Что называют базисом транспортной задачи?

Это совокупность клеток транспортной таблицы, в которой:

1) никакие клетки не образуют между собой циклов

2) любая клетка, не входящая базис, образует со всеми клетками базиса или их частью цикл

17. Что такое «базисный план транспортной задачи»?

Транспортный план перевозок называют базисным, если заполненные клетки таблицы образуют базис.

18. Сколько заполненных клеток содержит базисный план транспортной таблицы?

(n+m-1)

19. Какой базисный план называют вырожденным?

Количество базисных клеток в нём меньше, чем (n+m-1)

20. Как вычисляется оценка небазисной клетки?

Ц_ij – множество клеток, которые образуют с клеткой ij цикл.

21. Что показывает оценка небазисной клетки?

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

22. Сформулируйте достаточное условие оптимальности базисного плана транспортной таблицы.

Оценки всех небазисных клеток неотрицательны.

23. Что такое «максимально допустимая циркуляция»?

Максимальное значение циркуляции, на которое можно изменить объём перевозок в интересующем нас цикле.

24. Как вычисляется максимально допустимая циркуляция.

Она равна минимальному объёму перевозок в клетках цикла со знаком «-».

25. Что происходит, если максимально допустимая циркуляция достигается сразу в нескольких клетках?

Следует выбрать одну из них.

26. Что происходит, если максимально допустимая циркуляция равна нулю?

План не изменяется – изменяется базис. Изменится только положение ведущей клетки.

27. Запишите систему для отыскания потенциалов.

28. Как с помощью потенциалов вычисляются оценки небазисных клеток?

29. Какие задачи относятся к дискретному программированию?

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

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

31. Какие две основные проблемы нужно решить при разработке метода ветвей и границ?

1) Как разбивать исходное множество на подмножества, а получившиеся подмножества – на более мелкие.

2) Получить метод оценивания.

32. Что называется рекордом в методе ветвей и границ?

Это наилучшая из границ.

Граница – это любое известное значение целевой функции на допустимом целочисленном решении.

33. Для чего используется рекорд в методе ветвей и границ?

Для удаления из дерева решения неперспективных вершин.

34. Когда решение задачи методом ветвей и границ считается оконченным?

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

35. Как строится оценка в задаче целочисленного линейного программирования?

φ(х) – оценка задачи без требования целочисленности.

x* – оптимальное решение нецелочисленой задачи.

φ(х)=c^T x*

возможны 2 случая:

1) x* – целочисленное решение

2) х* – есть i₀ –компонента, не являющаяся целочисленной, т.е. х*_i0 – нецелочисленное.

х¹={x €X: х_i0≤ [х*_i0]}

х²={x €X: х_i0≥ [х*_i0+1]}

В процессе оценки множества х¹(х²) может оказаться х^1*окажется целочисленным. В этом случае вершина соответствующая множеству х¹ объявляется рекордом и дальше не разбивается на подмножества, а используется для отсечения неперспективных вершин.

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

х¹={x €X: х_i0≤ [х*_i0]}

х²={x €X: х_i0≥ [х*_i0+1]}

37. Что такое «отсечение» (в методе отсечений)?

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

38. Что называется правильным отсечением Гомори?

Отсечение удовлетворяет трем требованиям:

1) является линейным.

2) отсекает оптимальное нецелочисленное оптимальное решение ЗЛП.

3) не отсекает ни одного целочисленного плана исходной задачи.

39. Что такое «целая часть числа»? «Дробная часть»?

Вещественное число α:

- целая часть – [α] – максимально целое число не превосходящее заданное

- дробная часть – {α}= α-[α].

40. Запишите формулу для построения правильного отсечения Гомори.

41. При каких условиях задача, решаемая алгоритмом Гомори, считается решенной?

Когда получено целочисленное решение.

42. Какие модели относят к динамическому программированию?

- игровые задачи

- задачи планирования

- ряд задач технического характера

- сводятся экономические задачи

- задача о распределении ресурсов

- задача о замене оборудования

43. Сформулируйте принцип инвариантного погружения.

Вместо конкретного N-шагового процесса рассматривается процесс с произвольным количеством шагов k, k≤N.

44. Сформулируйте принцип оптимальности.

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

45. Запишите математическую модель задачи о распределении ресурсов.

46. В чем состоит принцип инвариантного погружения для задачи о распределении ресурсов?

Вместо конкретного N-шагового процесса рассматривается процесс с произвольным количеством шагов k, k≤N

47. Что выражает функция Беллмана в задаче о распределении ресурсов?

– распределение y единиц ресурсов между k предприятиями

48. Запишите рекуррентные соотношения Беллмана для задачи о распределении ресурсов.

49. Сформулируйте задачу о замене оборудования.

Предположим, что планируется эксплуатация оборудования в течение некоторого периода времени продолжительностью n лет. Оборудование имеет тенденцию с течением времени стареть и приносить все меньший доход r(t) (t – возраст оборудования). При этом есть возможность в начале любого года продать устаревшее оборудование за цену S(t), которая также зависит от возраста t, и купить новое оборудование за цену P. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарный доход за все n лет был бы максимальным, учитывая, что к началу эксплуатации возраст оборудования составлял t₀ лет. Исходными данными в задаче являются доход r(t) от эксплуатации в течение одного года оборудования возраста t лет, остаточная стоимость S(t), цена нового оборудования P и начальный возраст оборудования t₀.

50. Что выражает функция Беллмана в задаче о замене оборудования?

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

51. Запишите рекуррентные соотношения Беллмана для задачи о замене оборудования.

1. Двойственная задача лп.

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

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

Задача, двойственная к двойственной, равняется исходной.

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

Предприятие производит n видов продукции и при реализации получает c_i от единицы продукции i-го вида. Для производства используется m видов сырья. Расход сырья на изготовление продукции осуществляется в соответствии с нормой – количество сырья i-го вида для изготовления продукции j-го вида.

, x – прибыли.

Тогда

, y – цены.

3. Основные соотношения двойственности.

1) Если x – план прямой задачи, а y – план двойственной задачи, то . При этом, если x^* и y^* – оптимальные планы, то

2) Если ограничения прямой задачи несовместны, то целевая функция двойственной задачи неограниченно убывает на множестве двойственных планов; наоборот, если ограничения двойственной задачи несовместны, то целевая функция прямой задачи неограниченно возрастает на множестве планов.

3) Условия дополняющей нежёсткости позволяют по оптимальному прямому плану найти оптимальный двойственный и наоборот

Если x^* – оптимальный план прямой задачи а y^*– оптимальный план двойственной задачи, то

4. Предварительный анализ оптимального решения задачи линейного программирования.

Основные ограничения-неравенства ЗЛП

1)ресурсные

а) дефицитные (=) – оказывают непосредственное влияние на оптимальный план, при увеличении количества прибыль увеличивается.

б) избыточные (<) – не участвуют в непосредственном формировании оптимального плана, не влияют на прибыль.

2) количественные.

а) несущественные (<, >) – не оказывают влияния на формирование оптимального плана.

б) существенные: (≤) – оказывают непосредственное влияние на оптимальный план, при увеличении количества прибыль увеличивается; (≥) – оказывают непосредственное влияние на оптимальный план, при увеличении количества прибыль уменьшается.

5. Чувствительность целевой функции к изменениям ограничений.

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

ЗЛП в канонической форме содержит m ограничений и n переменных. Решение задачи линейного программирования будем называть невырожденным, если оно содержит ровно m положительных и n-m нулевых компонент.

Если оптимальное решение x* задачи линейного программирования не вырождено, то

Здесь L(x*) – значение целевой функции на оптимальном плане; - частная производная целевой функции по переменной b_i; y_i^* – i-ая компонента оптимального двойственного плана, который находится из соотношения .

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

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