Содержание

Лабораторная работа № 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 часа)

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

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

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

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

НЕ нашли? Не то? Что вы ищете?

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

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

Номер операции	Производительность ( в шт.)
А	В
Операция 1	12	6
Операция 2	8	8
Операция 3	6	-
Операция 4	-	8

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

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

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

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

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

или

Операция 1 +

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

Операция 3 6

Операция 4 8

max F = max F =

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

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

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

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

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

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

, , F = 2D.