54

Содержание

Лабораторная работа № 1 (4 часа) 1

Лабораторная работа № 2 (4 часа) 3

Лабораторная работа № 3 (4 часа) 9

Лабораторная работа № 4 (4 часа) 27

Лабораторная работа № 5 (4 часа) 31

Лабораторная работа № 6 (4 часа) 35

Лабораторная работа № 7 (4 часа) 38

Лабораторная работа № 8 (4 часа) 44

Приложение. Задачи к л/р 50

Лабораторная работа № 1 (4 часа)

Геометрическая интерпретация ЗЛП

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

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

.

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

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

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

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

Кроме того, известно, что реализация каждого изделия А приносит прибыль 2 единицы, а реализация каждого изделия В – 3 единицы.

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

Математическая модель задачи может быть построена следующим образом:

Обозначим x₁ и x₂ количество заложенных в производственный план изделий видов Аи В соответственно. Обозначим буквой F получаемую при реализации производственного плана прибыль. Тогда с учетом этих обозначений имеем:

или

О перация 1 +

Операция 2 + + 8

Операция 3 6

Операция 4 8

max F = max F =

Строго говоря, не переменные и нужно было бы наложить еще требование целочисленности.

Дадим геометрическую интерпретацию данной задачи линейного программирования в пространстве решений и . Заметим, что система ограничений изображена графически (прямые линии) как система уравнений, полученная путем замены фигурирующих в ней неравенств на равенства. Отсекаемая этими прямыми область пространства решений вместе с граничными точками представляет собой область допустимых решений (сокращенно ОДР) данной задачи линейного программирования. Поскольку ни одна из управляемых переменных не может принимать отрицательных значений, область допустимых решений x₁ и x₂, ограничена и осями координат, образуя, таким образом, выпуклый многоугольник. Выпуклость многоугольника означает, что любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри него или проходит его границы, т.е. принадлежит ему. Вершины О, C, D, E и F называются экстремальными точками – они не могут принадлежать внутренней части ни одного из отрезков, принадлежащих данному выпуклому многоугольнику.

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

Пример геометрической интерпритации ЗЛП

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

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

, , F = 2D.

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

4 + 24 = 12

4 + 4 = 8

4 < 6

4 < 8

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

Лабораторная работа № 2 (4 часа)

Элементы теории игр

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

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

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

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