 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Тема 4. Линейное программирование (ЛП)
1) Постановка задачи линейного программирования. Формы записи задачи ЛП.
2) Графический метод решения задачи ЛП.
3) Стандартная форма задачи ЛП. Симплекс-метод.
4) Двойственность в линейном программировании.
ü Прикладные задачи линейного программирования (ЛП). Графическая интерпретация задачи ЛП
Методы линейного программирования оказались весьма эффективными для решения некоторых задач из области исследования операций. Под "программированием " мы будем понимать планирование. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и управлении - как в местных, так и в государственных масштабах. Этими методами можно решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.
Пример 1.1
Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки.
Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В - 4 м2.
Фирма может получить от своих поставщиков до 1700 м2 досок в неделю.
Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли?
Чтобы сформулировать эту задачу математически, обозначим через x 1количество выпущенных за неделю полок модели А, а через x 2- количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения x 1и x 2. Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль. Еженедельная прибыль
P = 2 x 1+ 4 x 2. (1.1)
Фирма будет получать максимальную еженедельную прибыль, если максимизирует целевую функцию
P = 2 x 1+ 4 x 2.
Согласно классической теории оптимизации функция принимает экстремальные значения в точках, в которых обращаются в нуль ее производные, либо на границе области определения. Рассмотрения производных в нашем случае недостаточно, так как
и 
и никаким выбором x 1и x 2нельзя обратить эти производные в нуль. Действительно, чтобы увеличить функцию Р, надо увеличить x 1и x 2. Но (и в этом суть проблемы) значения x 1и x 2не могут быть увеличены неограниченно. Эти значения ограничены, в частности, лимитами на сырье и машинное время.
Поскольку x 1и x 2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т. е.
(1.2)
Теперь ограничения на наличие досок и машинное время могут быть записаны следующим образом:
(для досок),
(для машинного времени), (1.3)
Следовательно, задача состоит в том, чтобы найти значения x 1и x 2, удовлетворяющие условиям неотрицательности (1.2) и ограничениям типа неравенства (1.3) и максимизирующие функцию P = 2 x 1+ 4 x 2.
Это типичная двухмерная задача линейного программирования. Целевая функция, которая должна быть максимизирована, является линейной функцией своих переменных. Ограничения на эти переменные тоже линейны (они представлены на рис. 1.1). Условия неотрицательности позволяют ограничиться рассмотрением положительного квадранта. Границы определяются прямыми
,
.
Стрелка на каждой границе рис 1.1 указывает, с какой стороны прямой выполняется ограничение. 
Заштрихованная область ОАВС, содержащая точки, для которых соблюдены условия (1.2) и (1.3), называется допустимой. Точки внутри и на границе этой области изображают допустимые решения. Допустимых решений много. Задача состоит в том, чтобы найти решение (может ли их быть более одного?), максимизирующее функцию P.
Штриховыми линиями на рис. 1.1 изображены прямые 
, обозначенные a и b соответственно. Эти прямые параллельны и представляют собой две линии уровня функции P со значениями соответственно 0 и 800. Ясно, что значение функции P возрастает по мере того, как линии уровня удаляются от начала координат в положительном квадранте. Действительно, вектор с компонентами 
, 
, т. е. вектор с компонентами 
указывает направление возрастания функции P, перпендикулярен штриховым линиям и направлен в сторону, противоположную началу координат.
Линией уровня с наибольшим значением функции P, имеющей хотя бы одну общую точку с допустимой областью, является прямая c, проходящая через вершину B; на ней P принимает значение 1400. Точка B, в которой x 1= 300, x 2= 200, соответствует оптимальному решению задачи. Эти значения могут быть получены как решения уравнений
,
.
Следовательно, максимальная прибыль составляет 2 × 300 + 4 × 200 = 1400. При оптимальном решении оба ограничения превращаются в равенства, что означает полное использование сырья и машинного времени.
Рассмотренная задача может быть расширена до трех и более моделей и соответствующего количества неотрицательных переменных. Могут быть введены дополнительные ограничения, связанные с возможностями рынка, упаковкой и т. д. В этом случае задача по-прежнему заключается, в максимизации линейной функции от нескольких неотрицательных переменных с линейными ограничениями в форме неравенств.
1) Постановка задачи линейного программирования. Формы записи задачи ЛП.
Общая задача линейного программирования состоит в максимизации (или минимизации) линейной функции
(1.4)
от n вещественных переменных x 1,x 2,…, x n, удовлетворяющих условиям неотрицательности
(1.5)
и m линейным ограничениям
(1.6)
Среди ограничений могут одновременно встречаться знаки ≤, = и ≥. Задача состоит в максимизации (минимизации) целевой функции. Значения bi, cj, aij предполагаются известными.
В матричных обозначениях задача может быть представлена следующим образом:
максимизировать (минимизировать) функцию
где
а
Индекс 0 в векторе x 0и в матрице A0 указывает на то, что это начальные значения.
2) Графический метод решения задачи ЛП.
На примере 1, мы рассмотрели задачу линейного программирования, возникающую на практике, и продемонстрировали графический метод их решения. Рассмотрев еще несколько примеров такого рода, мы сможем выявить несколько общих свойств задач линейного программирования, которые могут подсказать путь к их общему решению.
Пример 1.2
Минимизировать функцию
z = − 3 x1 − 4 x2
при ограничениях x 1,x 2 ≥0,
Допустимой областью, изображенной на рис. 1.2, является четырехугольник PQRS.
Два последних ограничения усиливают условия неотрицательности. Функция z убывает в направлении вектора
Минимальное значение функции z = – 68 и достигается в точке R = (12, 8). Заметим, что, как и в примере 1, минимум достигается в вершине допустимой области. Оптимальным решением задачи является точках x 1=
12, x 2= 8 с минимальным значением функции z = – 68.
Из рассмотренного примера можно вывести несколько характерных черт задач линейного программирования:
1. Допустимая область всегда является выпуклым многоугольником, даже в случае, когда она не ограничена.
2. Оптимальное решение всегда достигается в вершинах допустимой области.
Задача линейного программирования могут быть приведены к стандартной форме.
3.1 Стандартная форма задачи ЛП
На первый взгляд задачи линейного программирования представляются по-разному. Все они могут быть приведены к стандартной форме, в которой целевая функция должна быть минимизирована, а все ограничения должны быть заданы в виде равенств с неотрицательными переменными.
Привести задачу к стандартной форме очень просто, используя следующие правила:
а) Максимизация целевой функции 
равносильна минимизации целевой функции 
б) Ограничение в виде неравенств, например 
, может быть приведено к стандартной форме 
, где новая переменная x4 неотрицательна.
Ограничение 
может быть приведено к стандартной форме 
, где новая переменная x 5неотрицательна.
в) Если некоторая переменная xk может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду 
, где 
и 
.
Таким образом, приведение задачи к стандартной форме может потребовать введения дополнительных переменных (по-прежнему неотрицательных).
Аналогично соотношениям (1.7), (1.8), (1.9) выразим наиболее общую задачу линейного программирования в следующем виде (в):
Если задача в таком виде является следствием задачи, рассмотренной выше, то в x наряду с исходными переменными будут входить новые переменные (и в матрицу А тоже).
Так, пример 2 может быть приведен к следующему виду:
минимизировать функцию z = − 3 x 1− 4 x 2
при ограничениях
Пример 1 может быть приведен к следующему виду:
минимизировать функцию z = − 2 x 1− 4 x 2
при ограничениях
Они состоят из двух уравнений с четырьмя неизвестными. Любое неотрицательное решение при этих ограничениях является допустимым решением.
Конечно, имея два уравнения с четырьмя неизвестными, можно получить решение (хотя не всегда допустимое), придавая двум неизвестным произвольные значения и разрешая уравнения относительно двух других неизвестных. Особенно интересны решения такого типа, когда два неизвестных приравниваются нулю. Если такое решение единственно, то оно называется базисным решением. Если оно к тому же допустимо, то называется базисным допустимым решением. Для общей задачи линейного программирования с n переменными, подчиненными m ограничениям (m < n), базисные решения ограничений могут быть получены, если приравнять нулю n – m из переменных и решить m уравнений относительно оставшихся m переменных; предполагается, что эти уравнения имеют единственное решение. Переменные, приравненные нулю, называются небазисными переменными. Остальные называются базисными и образуют базис.
В рассмотренных выше задачах можно выбрать две небазисные переменные шестью способами. Легко видеть, что базисные решения могут быть сведены в таблицу, в которой каждое решение соответствует паре небазисных переменных (x 1,x 2), (x 1,x 3), (x 1,x 4), (x 2,x 3), (x 2,x 4), (x 3,x 4). Из этих шести базисных решений только четыре допустимы и соответствуют вершинам допустимой области рис. 1.1 (см. приведенную таблицу).
В трехмерном случае линейные ограничения являются плоскостями, а не прямыми, допустимая область является выпуклым многогранником, а не выпуклым многоугольником. Оптимальному решению задачи будет соответствовать вершина этого многогранника, поскольку поверхностями уровня целевой функции будут плоскости вместо прямых, а плоскость, соответствующая наименьшему значению, имеет, вообще говоря, только одну общую точку с допустимой областью; эта точка и будет вершиной выпуклого многогранника, соответствующей оптимальному решению задачи.
Мы увидим, что этот результат закономерен. Базисные решения системы m уравнений с n неизвестными соответствуют вершинам допустимой области; оптимальное решение (если оно существует) соответствует базисному допустимому решению и, следовательно, является вершиной допустимой области.
3.2) Симплекс-метод
Графический метод, показанный в примере 1.2, удобен для двухмерных задач, но его невозможно применить к задачам с размерностью, большей трех. Однако во всех задачах оптимальное решение определяется допустимым базисным решением. Симплекс-метод, разработанный Г. Данцигом, является вычислительной процедурой, основанной на этом положении, однако представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме:
причем предполагается, что имеется базисное допустимое решение, удовлетворяющее всем ограничениям.
Базисное решение, удовлетворяющее ограничениям, можно получить, если найти m столбцов матрицы A, образующих несингулярную матрицу B m × n. Если эти столбцы соответствуют переменным 
, то ограничения могут быть преобразованы так, чтобы выразить через b и остальные x, что можно записать в виде
(Невырожденная матрица (иначе несингулярная матрица) ― квадратная матрица, определитель которой отличен от нуля. В противном случае матрица называется вырожденной
Если умножить ограничения системы (2.4) на 
и вычесть из z, то 
исключатся из z и мы получим
Разумеется, уравнения (2.4) и (2.3) выражают одинаковые ограничения, а уравнения (2.5) и (2.1) представляют одну и ту же целевую функцию, хотя и в разных алгебраических формах. Уравнения (2.4) и (2.5) являются канонической формой для базиса . Если положить 
равными 0, то соотношения
задают базисное решение.
Если все 
, это решение допустимо. Среди таких решений надо найти оптимальное. Симплекс-метод обеспечивает систематическую процедуру для такой замены одной допустимой канонической формы на другую, при которой значение целевой функции оптимизируется.
Иногда базисное допустимое решение очевидно, как в выбранном для иллюстрации симплекс-метода примере 1.1, который уже решен графически.
Поиск по сайту: