Контрольное задание по «Методы оптимальных решений»

 

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

при условиях

                                                                  (20)

     (21)

Задача, состоящая в нахождении минимального значения функции

                                                                               (22)

при условиях

                                                                  (23)

   (24)

называется двойственной по отношению к задаче.

 

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

 

- Первая теорема двойственности.

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

- Вторая теорема двойственности.

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

                                                                                (25)

 

45. Дайте интерпретацию двойственных переменных в задаче линейного программирования.

 

Для двойственной задачи:

 

 

 (26) 

Интерпретация переменных следующая:

Вектор , соответствующий ограничению  прямой задачи, будем интерпретировать как вектор цен на производимые в системе товары. Предположим, что малоквалифицированный труд, являющийся единственным ресурсом для производства продукции отраслей , оплачивается по единой ставке заработной платы , которая является двойственной переменной к ресурсному ограничению \* MERGEFORMAT (11).

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

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

 

46. Расскажите об анализе чувствительности в задаче линейного программирования.

 

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

 

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

 

Решить графически

  . (27)

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

Областью решения есть многогранник:

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

Для нахождения максимума:

Прямая пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:

,

Максимальное значение целевой функции:

Для нахождения минимума:

Прямая пересекает область в точке С. Так как точка С получена в результате пересечения прямых (4) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:

,

Минимальное значение целевой функции:

Поскольку функция цели F(x) параллельна прямой (5), то на отрезке CA функция F(x) будет принимает одно и тоже минимальное значение.

 

48. В чем состоят методы решения задач линейного программирования, основанные на направленном переборе вершин (симплекс-метод и др.)?

 

Направленный перебор.

Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

 

49. Какие возможности предоставляет среда MS Excel для решения задач линейного программирования?

 

Для решения подобных задач в MS EXCEL предназначена команда Поиск решения из меню Сервис.

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

 

50. В чем состоят градиентные методы решения задачи безусловной оптимизации?

 

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

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

f(x(1)), то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1).

 

51. Как штрафные функции используются при поиске решения выпуклой задачи нелинейного программирования?

 

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

Весьма актуальным является обобщение метода квадратичной штрафной функции для получения проекции произвольной точки на множество решений прямой или двойственной задач ЛП.

 

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

 

Методы штрафных функций:

- «бесконечный» штраф

- логарифмический штраф

- штраф обратной функции

- штраф квадрата срезки

 

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

 

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

 

54. Назовите и сформулируйте критерии выбора решений в условиях неопределенности    (принцип гарантированного результата, критерий Гурвица, критерий Байеса-Лапласа, критерий Сэвиджа).

 

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

- критерий Вальда (критерий «максимина»)

- критерий «максимакса»

- критерий Гурвица (критерий «оптимизма-пессимизма» или «альфа-критерий»)

- критерий Сэвиджа (критерий потерь от «минимакса»)

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

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

3. Критерий Гурвица (критерий «оптимизма-пессимизма» или «альфа-критерий») позволяет руководствоваться при выборе рискового решения в условиях неопределенности некоторым средним результатом эффективности, находящимся в поле между значениями по критериям «максимакса» и «максимина» (поле между этими значениями связано посредством выпуклой линейной функции).

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

 

55. Как определяется множество допустимых гарантирующих программ? Что такое наилучшая гарантирующая программа?

 

Множество допустимых гарантирующих программ определяется следующим образом:

1. Строят прямые соответствующие  стратегиям второго (первого) игрока.

2. Определяют нижнюю (верхнюю) границу выигрыша

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

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

Наилучшая гарантирующая программа – стратегия, которая гарантирует максимальный выигрыш игрока в наихудших для него условиях

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

 

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

 

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

заданные величины cj, аij, bi, dj, Dj. Часто на практике величины cj, аij, bi могут быть случайными. Так, если bi - ресурс, то он зависит от ряда факторов. Аналогично, cj - цены - будут зависеть от спроса и предложения, аij - расходные коэффициенты - от уровня техники и технологии.

Задачи, в которых cj, аij, bi - случайные величины, относят к задачам стохастического программирования.

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

реализацией случайных величин;

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

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

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

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

 

 

57. В чем состоит принятие решений на основе математического ожидания?

 

Процедура принятия решений строится на основе теории вероятностей и математической статистики.

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

                                                           (28)

 

58. Как учитывается склонность к риску?

 

Предположение о несклонности к риску сыграло центральную роль в экономической теории.