Учебно-методический комплекс (стр. 18 )

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

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

Напомним, что от операции минимизации к операции максимизации (и наоборот) переходят умножением целевой функции на "–1".

Задание. Привести к стандартной и канонической формам следующую общую задачу линейного программирования:

Экономическая интерпретация стандартной задачи ЛП

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

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

Построим математическую модель этой задачи. Обозначим через планируемый объем выпуска продукции Тогда ожидаемая прибыль от реализации -го вида продукции составит а суммарная прибыль от реализации всей продукции будет равна

Согласно условиям задачи, она подлежит максимизации.

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

Учитывая естественные условия неотрицательности объемов выпуска продукции

,

придем к постановке стандартной задачи ЛП.

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

Приведем теперь эту задачу к канонической форме, добавив в правую часть каждого i-го неравенства неотрицательную переменную ():

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

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

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

и графо-аналитический способ решения задач ЛП

Рассмотрим стандартную задачу ЛП, поставленную в пространстве , т. е. допускающую проведение геометрического анализа на плоскости переменных :

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

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

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

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

Теперь несложно сформулировать графо-аналитический способ решения стандартных задач ЛП с двумя переменными:

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

·  изображается целевой вектор ;

·  через допустимое множество проводится перпендикуляр к целевому вектору – это изолиния целевой функции;

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

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

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

При решении задач ЛП могут встретиться различные случаи существования оптимального плана:

а) существует и является единственной точкой;

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

в) не существует, т. к. либо допустимое множество пусто, либо целевая функция неограничена.

Замечание. Графо-аналитический метод может быть применен к решению задач ЛП с числом переменных, большим 2, если их удается свести к двумерным задачам. Такое сведение возможно, если ограничения содержат достаточное количество линейно-независимых уравнений (их число меньше числа переменных на два). Тогда можно исключить из задачи все переменные, кроме двух, и исследовать получившуюся вспомогательную задачу графически.

Задание. Ознакомьтесь с более подробным изложением материала данного пункта, размещенным на методическом сайте БГУЭП (Курс оптимизации в экономике, лекция 3).

Решите самостоятельно задачи №№ 1.43; 1.44; 1.47; 1.51; 1.68 (, "Математическое программирование", часть 1).

Структура множества планов канонической задачи ЛП

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

Изучая геометрический метод решения двумерных задач ЛП с ограничениями типа неравенств, мы установили следующие факты:

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

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

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

Покажем, что каноническая задача ЛП обладает теми же или похожими свойствами.

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

Дадим ряд важных определений.

Определение 1. Отрезком, соединяющим две точки называется множество точек вида

Уравнение точек отрезка можно записать и в другой форме, если собрать члены при параметре : Например, пусть даны точки А=(1,6) и В=(2,3).Тогда соединяющий их отрезок можно записать в виде

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

Ниже на рисунках 2.3 и 2.4 даны примеры выпуклых и невыпуклых множеств.

Рис.2.3. Выпуклые множества

Рис.2.4. Невыпуклые множества

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

Свойство 1. Множество планов канонической задачи ЛП выпукло.

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

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

Проверим, удовлетворяют ли точки отрезка ограничениям типа равенств.

Так как для всех , то , и, следовательно, множество X – выпукло.

Определение 3. Точка x , принадлежащая выпуклому множеству X , называется угловой (крайней) точкой множества X, если она не является внутренней точкой ни одного отрезка из множества X.

На математическом языке точка x – угловая точка множества X, если где .

Конечное число угловых точек

(две у отрезка, три у треугольника и т. д.)

Бесконечное множество угловых точек

(все точки окружности)

. Внутренность круга ()

не содержит ни одной угловой точки

Определение 4. Выпуклое множество X , имеющее конечное число угловых точек, называется выпуклым многогранным множеством, а в случае ограниченности – выпуклым многогранником.

Выпуклое многогранное множество Выпуклый многогранник

. Допустимые множества в задаче ЛП

Критерий угловой точки множества допустимых планов канонической задачи ЛП

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

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

(2.11)

(2.12)

(2.13)

Обозначим – j-ый столбец матрицы условий A.

Тогда ограничения (2.12) канонической задачи можно записать в следующем виде:

(2.14)

Теорема 1 (Критерий угловой точки множества допустимых планов канонической задачи линейного программирования). Точка множества планов канонической задачи (2.11-2.13) является угловой точкой этого множества тогда и только тогда, когда её строго положительным координатам соответствуют линейно независимые столбцы матрицы условий системы (2.14).

Задание. Изучите самостоятельно доказательство теоремы 1, ознакомившись, например, с материалами лекций на сайте университета (Оптимизация в экономике).

Напомним, что максимальное число линейно независимых столбцов матрицы равно ее рангу. Заметим, что, так как число уравнений m < n, то , то есть среди столбцов A1 , A2 , … , An не более чем m линейно независимых векторов. Следовательно, крайняя точка может иметь не более чем m положительных координат и, значит, не менее чем n–m ее координат обязательно равны нулю.

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

Базисные планы канонической задачи ЛП

Напомним алгебраическую трактовку канонической задачи ЛП.

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

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

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

В канонической задаче ЛП нас будут интересовать как раз только неотрицательные базисные решения системы (2.12), называемые базисными планами. Дадим более строгое определение.

Определение 5. План канонической задачи ЛП называется базисным, если n – m его переменных (небазисных) равны нулю, а остальным (базисным) переменным соответствуют линейно независимые столбцы матрицы условий A.

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

Сравнивая определение 5 с критерием угловой точки множества планов X канонической задачи ЛП, видим, что алгебраическому понятию базисного плана соответствует геометрическое понятие крайней точки множества X.

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

Рассмотрим вопрос о числе угловых (крайних) точек множества планов канонической задачи ЛП.

Очевидно, что среди n столбцов A1, A2 ,..., An матрицы условий A выбрать подсистему из m столбцов можно не единственным способом. Известно, что число всевозможных сочетаний из n элементов по m равно . Например, в канонической задаче с 3 переменными и 2 ограничениями (n = 3, m = 2) из матрицы условий A = {A1, A2, A3} можно выделить только три различные подсистемы пар векторов A1 A2 , A1 A3 , A2 A3 , что как раз и равно Cnm = C32 = 3.

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

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

Чтобы на практике найти какой-либо базисный план – угловую точку множества планов канонической задачи ЛП, нужно любые n – m координат плана положить равными нулю, а оставшиеся m переменных найти из системы Ax = b, которая будет содержать m уравнений и m неизвестных. Если столбцы матрицы А, вошедшие в укороченную систему, окажутся линейно независимыми, то система будет иметь единственное решение. Если полученное решение будет неотрицательным, то это – базисный план.

Пример 1. Найти все базисные планы - угловые точки множества планов канонической задачи ЛП

(2.15)

(2.16)

(2.17)

(2.18)

Решение. Матрица условий А содержит 4 столбца

Так как n = 4, m = 2 , то

В задаче не более шести базисных планов (угловых точек). В любом плане должно быть n – m = 2 нуля. Возможные варианты расположения двух нулей среди четырех координат запишем во втором столбце таблицы:

Точка	Состав переменных	Базис	Базисное решение	Базисный план?
T1	0, 0, x3, x4	A3 , A4	( 0, 0, 4, 12 )	да
T2	0, x2, 0, x4	A2 , A4	( 0, 2, 0, 8 )	да
T3	0, x2 , x3, 0	A2 , A3	( 0, 6, -8, 0 )	нет
T4	x1, 0, 0 , x4	A1 , A4	(-4, 0, 0, 24 )	нет
T5	x1 , 0 , x3, 0	A1 , A3	( 4, 0, 8, 0 )	да
T6	x1, x2, 0, 0	A1 , A2	( 2, 3, 0, 0 )	да

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

Рассмотрим точку T1. Подставляя x1 = 0, x2 = 0 в уравнения (2.16), (2.17), получим x3 = 4 , x4 = 12. Базис точки T1 состоит из единичных векторов {A3,A4}. Очевидно, что эти столбцы линейно независимы. Так как все координаты точки T1 неотрицательны, то T1 = (0, 0, 4, 12 ) – угловая точка.

Для нахождения базисных координат точки T2 подставим небазисные (нулевые) значения x1 = 0 и x3 = 0 в уравнения (2.16), (2.17). Получим систему

2 x2 = 4 ,

2 x2 + x4 = 12,

откуда найдем x2 = 2 , x4 = 8.Следовательно, точка T2 = (0, 2, 0, 8). Ее базис состоит из столбцов A2 и A4 . Так как все ее координаты неотрицательны, то это – базисный план (крайняя точка).

При вычислении базисных координат точки T3 обнаружим, что x3 = –8, следовательно, T3 =( 0, 6, -8, 0) не является базисным планом.

Проведя аналогичные вычисления для остальных претендентов на базисные планы и заполнив таблицу, мы видим, что эта задача имеет четыре различных базисных плана (четыре угловые точки) T1 , T2 , T5 , T6 , причем все они невырожденные.

Заметим, что рассматриваемая каноническая задача получена из стандартной задачи ЛП с двумя переменными