Линейное программирование
3.Лекция. Линейное программирование.
3.1 Общая постановка задачи
Линейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
Определение .
Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.
В общем виде математическая модель задачи линейного программирования (ЛП) записывается как
Z(x)=C1X1+C2X2 + . . . +СJXJ + . . . +СnXn _ max(min)
при ограничениях:
Рекомендуемые материалы
где Xi — неизвестные;a ij , bj , Ci — заданные постоянные величины.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.
Математическая модель в более краткой записи имеет вид
Z(x) = ∑Ci Xi → max(min)
при ограничениях:
Определение Допустимым решением (планом) задачи линейного программирования называется вектор X = (х1, х2, ,...хn , ) , удовлетворяющий системе ограничений.
Множество допустимых решений образует область допустимых решений (ОДР).
Определение Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается Хопт.
Базисное допустимое решение
Является опорным решением, где r— ранг системы ограничений.
Виды математических моделей ЛП
Математическая модель задачи ЛП может быть канонической и неканонической.
Определение. Если все ограничения системы заданы уравнениями и переменные Xj неотрицательные, то такая модель задачи называется канонической.
Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое
неравенство ввести балансовую переменную хn+i .
Если знак неравенства <, то балансовая переменная вводится со знаком плюс, если знак неравенства >, то — минус. В целевую функцию балансовые переменные не вводятся.
Чтобы составить математическую модель задачи ЛП, необходимо:
— ввести обозначения переменных;
— исходя из цели экономических исследований, составить целевую функцию;
— учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений.
3. 2 Двойственность в задачах линейного программирования
Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.
Математические модели этих задач имеют следующий вид.
| прямая задача:
| двойственная задача:
|
Эти задачи экономически могут быть сформулированы следующим образом.
Прямая задача: сколько и какой продукции хi(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции Сi, объемом имеющихся ресурсов bj (j=1,2,…, m) и нормах расхода ресурсов аij максимизировать выпуск продукции в стоимостном виде.
Двойственная задача: какова должна быть оценка единицы каждого ресурса yj (j=1, 2,…, m), чтобы при заданных bj, ci и аij минимизировать общую оценку затрат на все ресурсы.
Правила построения двойственной задачи по имеемой прямой задаче:
1.Если прямая задача решается на максимум, то двойственная задача решается на минимум; если прямая задача решается на минимум то двойственная на максимум;
2.В задаче на максимум ограничения неравенства имеют вид – ≤, а в задаче на минимум – ³;
3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи, в другой модели ограничению двойственной задачи соответствует переменная прямой задачи;
4.Матрица системы ограничений двойственной задачей получается из матрицы из матрицы систем ограничений прямой задачи транспонированием;
5.Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи и наоборот;
6.Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, в противном случае – как ограничение равенство;
7.Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.
Пример:
| Прямая задача:
| Двойственная задача:
|
В этой задаче 
– предельные оценки стоимости единицы каждого ресурса, целевая функция – оценка стоимости всех ресурсов, а каждое ограничение есть условие, что оценка ресурсов, идущих на производство продукции 
, не менее чем цена единицы продукции.
Взаимосвязь решений прямой и двойственной задач находится из трех теорем двойственности.
3. 3 Теоремы двойственности.
Первая теорема двойственности:
Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают Z(X)=Z'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения и оценок ресурсов, при этом полная стоимость продукта, полученного в результате реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадения, значений целевых функций для соответствующих решений пары двойственных задач достаточно для того, чтобы эти решения были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными только тогда, когда полная стоимость произведенной продукции и суммарная оценка ресурсов совпадает.
Оценки выступают как инструмент сбалансирования затрат и результатов. Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.е. равенство общей стоимости продукции и ресурсов обуславливает убыточность всякого другого плана отличающегося от оптимального. Двойственные оценки позволяют сопоставлять и сбалансировать затраты и результаты производства.
Вторая теорема двойственности:
Для того чтобы план Х* и Y* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
Эти условия называются условиями дополняющей нежесткости. Из них следует, что если какое-либо неравенство системы ограничений в одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующий элемент оптимального плана двойственной задачи должен равняться нулю. Если какой-либо элемент оптимального плана одной из задач положителен, то соответствующее ограничение в двойственной задаче её оптимальным планом должно обращаться в строгое равенство, т.е.
если 
< bj, то 
;
если 
> 0, то 
.
Аналогично,
если 
> 
;
если 
>0 то 
.
Экономически это означает, что если по некоторому оптимальному плану X*= 
производства расход j-го ресурса меньше его запаса bj, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.
Третья теорема двойственности:
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи линейного программирования, т.е.
В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:
,
если 
, тогда 
, Экономическое содержание третьей теоремы двойственности: двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки yj часто называются скрытыми теневыми или маргинальными оценками ресурсов.
3.4 Решение задач линейного программирования
геометрическим методом
При решении задач линейного программирования геометрическим способом необходимо помнить, что визуализация решения достигается только при рассмотрении задачи с двумя переменными и небольшим количеством ограничений. Также желательно выбрать масштаб осей так, чтобы график был компактным, но было четко видно все точки пересечения ограничений.
С геометрической точки зрения в задаче линейного программирования ищется такая точка или набор точек из допустимого множества решений, на которой достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.
Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор gradZ на плоскости Х2ОХ2 .
Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора grandZ являются коэффициенты целевой функции Z(x).
Алгоритм геометрического метода решения задач ЛП.
Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму:
1.Строим координатные оси Х1ОХ2 и с учетом коэффициентов математической модели выбираем масштаб.
2.Находим область допустимых решений (ОДР) системы ограничений математической модели.
3.Строим прямую целевой функции и показываем направление наискорейшего ее изменения (нормаль-gradL).
4.Линию целевой функции (линия уровня) перемещаем по направлению нормали для задач на максимум целевой функции и в противоположном направлении - для задач на минимум ЦФ.
Перемещение линии уровня через ОДР производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений. Эта точка будет точкой экстремума, и будет определять единственное решение задачи ЛП.
Если окажется, что линия уровня совпадает с одной из сторон ОДР , то задача ЛП будет иметь бесчисленное множество решений.
Если ОДР представляет неограниченную область, то целевая функция – неограниченна.
Задача ЛП может быть неразрешима ,когда определяющие ее ограничения окажутся противоречивыми.
5.Находим координаты точки экстремума и значение ЦФ в ней.
Рассмотрим задачу.
Торговая фирма для продажи товара трех видов использует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида даны в таблице. Прибыль получаемая от реализации одной парии товаров 1 вида – 5 у.е. 2 вида – 8 у.е.
| Ресурсы | Вид товара | Объем ресурсов | |
| 1 | 2 | ||
| Время | 0,5 | 0,7 | 370 |
| Площадь | 0,1 | 0,3 | 90 |
Определить оптимальную структуру товарооборота, обеспечивающую фирме максимальную прибыль.
Решение задачи.
Математическая модель прямой задачи
Max Z= 5x1+8x2
0,5 x1+0,7x2 £ 370
0,1 x1+0,3x2 £ 90
x1,2 ³ 0
Математическая модель двойственной задачи
Min Z’= 370y1+90y2
0,5y1+0,1y2 ³ 5
0,7у1+0,3у2 ³ 8
y1,2 ³ 0
Разберем экономический смысл переменных, входящих в модели и ограничений, составленных на основе условия задачи.
x1 – количество товара первого вида, которое необходимо продавать согласно оптимальному плану.
х2 – количество товара второго вида, которое необходимо продавать согласно оптимальному плану.
0,5 x1+0,7x2 – это условие показывает, сколько времени всего будет потрачено на продажу товаров первого и второго вида.
0,1 x1+0,3x2 – это условие показывает, сколько площади будет потрачено на продажу товаров первого и второго вида.
5x1+8x2 – выручка, полученная при продаже оптимального количества товаров первого и второго вида.
у1 – цена одной единицы первого ресурса (1 часа работы продавца)
у2 – цена одной единицы второго ресурса (1 м2 площади торгового зала).
0,5y1+0,1y2 – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого вида.
0,7у1+0,3у2 это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий второго вида.
370y1+90y2 – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого и второго вида.
Непосредственное решение состоит из построения нескольких прямых на плоскости XOY. Построение неравенств на плоскости состоит из построения соответствующих прямых и выбора нужной полуплоскости. Для выбора полуплоскости необходимо подставить какую-нибудь точку плоскости (чаще всего точку (0,0)) в соответствующее неравенство и о выполнении или невыполнении этого неравенства сделать вывод о том, какая именно полуплоскость соответствует неравенству.
Для построения прямых достаточно взять две точки.
Целевая функция приравнивается к 0 для возможности ее построения. Потом с помощью параллельного переноса функция цели двигается так, чтобы из положения секущей она стала касательной. В точке, где целевая функция становится касательной области допустимых значений и будет точка оптимального решения.
Построение системы ограничений для данной задачи дает следующую область ограничений.
Темным цветом показана область допустимых значений. Теперь, если построить целевую функцию на этом же графике, то видно, что при параллельном переносе из точки (0,0) она становится касательной в точке (600,100).
Аналитически найдем координаты точки пересечения двух прямых системы ограничений.
Решая эту систему, получаем, что для получения максимальной прибыли необходимо продавать 600 единиц товара первого вида и 100 товара второго вида. При этом максимальная выручка от продажи составит 600*5+100*8=3800 ден. ед.
Анализ решения данной задачи.
Так как оба ограничения этой задачи активно, то товары обоих видов необходимо продавать. По второй теореме двойственности это означает, что остатков ресурсов не будет, и ограничения-неравенства двойственной модели превратятся в ограничения-равенства.
Решая соответствующую модель, находим стоимости ресурсов.
у1 = 8,75 ден. ед., у2 = 6,25 ден. ед.
Проверим выполнение первой теоремы двойственности.
Min Z’= 370*8,75+90*6,25=3800 ден. ед.
Это означает, что выручка от продажи товаров будет равна суммарным расходам на продажу товаров первого и второго вида.
Аналогично можно проверить выполнение рентабельность продаж изделий.
Для товара первого вида: 0,5*8,75+0,1*6,25=5 – следовательно, продавать товары первого вида рентабельно.
Для товара первого вида: 0,7*8,75+0,3*6,25=8 – следовательно, продавать товары второго вида рентабельно.
Этот же вывод можно сделать исходя из второй теоремы двойственности.
Построим матрицу взаимозаменяемости ресурсов.
| у1 | у2 | |
| у1 | 1 | 6,25/8,75=0,71 |
| у2 | 1,4 | 1 |
Это означает, что одну единицу второго ресурса можно заменить 1,4 единицами первого ресурса.
Рассмотрим необходимость покупки двух единиц первого ресурса по цене 50 ден. ед. за партию и трех единиц второго ресурса по цене 15 ден. ед. за партию.
Так как одну единицу первого ресурса предлагают по цене 50/2=25 и это больше, чем 8,75 , то покупка первого ресурса по таким ценам невыгодна, одну единицу второго ресурса предлагают по цене 15/3=5 и это меньше, чем 6,25, поэтому покупка второго ресурса по таким ценам выгодна.
Тем не менее, вопрос о покупке ресурсов невозможно рассматривать без учета устойчивости. Так как малейшее изменение условий задачи приведется к изменению оптимального плана продаж.
Для того чтобы определить устойчивость необходимо найти матрицу, обратную к матрице ограничений.
В данном случае это будет матрица 
Найдем устойчивость по количеству ресурсов. Для нахождения на сколько можно уменьшить количество ресурсов из обратной матрицы берутся только положительные числа, соответственно для нахождения на сколько можно увеличить объем ресурсов из обратной матрицы берутся только отрицательные величины по модулю.
=0,00625
=0,0625
=0,0125
=0,014583
Таким образом,
,
Для расчета по цене товара используется аналогичная методика.
=2,33
=1
=5
=1
Таким образом, 
, 
С помощью анализа решения можно ответить и на вопрос продажи нового продукта, если известны затраты ресурсов и продажная цена.
Например, если предлагается на продажу товар третьего вида по цене 10 ден. ед., который требует времени продавца в объеме 1,5 ед., и занимает площадь 0,5 ед., то затраты на его продажу составят 1,5*8,75+0,5*6,25=16,25 ден. ед. Это явно больше 10 ден. ед. прибыли, которой товар третьего типа мог бы принести , и его продажа на данных условиях не выгодна.
3. 5 Симплексный метод решения задач ЛП
Общая постановка задачи
Симплексный метод – метод последовательного улучшения плана.
Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.
Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.
Алгоритм симплексного метода
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).
5.Построить новую симплекс-таблицу-второй шаг.
При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.
-Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.
-Построение других строк в новой таблице. Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.
6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.
Прямая задача на минимум решается следующим образом:
-Написать математическую модель двойственной задачи в стандартном виде
-Решить двойственную модель симплекс - методом
-Записать ответ.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой.
Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.
| Х1
| x2 | … | xn | S1 | S2 | … | Sm |
| S1
| S2 | … | Sm | y1 | y2 | … | ym |
Задача
На предприятии имеется возможность выпускать n видов продукции (1,2,…n). При ее изготовлении используются ресурсы Р1, Р2, Р3. Размеры прямых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход i –го ресурса на единицу продукции j-того вида составляют aij. Цена единицы продукции j-того вида равна cj ден. ед. Сформулировать прямую и двойственную задачу и раскрывать экономический смысл всех переменных.
Требуется:
Найти оптимальный план симплекс-методом.
Найти решение двойственной задачи
Указать дефицитность ресурсов
Обосновать эффективность плана производства
Оценить целесообразность приобретения ресурса
Оценить целесообразность выпуска новой продукции
Данные :
b1 = 25, b2 = 30, b3 = 42
a11= 2, a12= 3, a13= 2, a14= 1
a21= 4, a22= 1, a23= 3, a24= 2
a31= 3, a32= 5, a33= 2,a34= 2
c1= 6, c2= 5, c3= 4, c4= 3
Математическая модель прямой задачи
max (Z= 6x1+5x2+4x3+3x4)
2x1+3x2+2x3+x4< 25
4x1+x2+3x3+2x4< 30
3x1+5x2+2x3+2x4< 42
x1, x2, x3, x4 > 0
Математическая модель двойственной задачи
min (Z*= 25y1+30y2+42y3)
2y1+4y2+3y3> 6
3y1+y2+5y3> 5
2y1+3y2+2y3> 4
y1+2y2+2y3> 3
y1, y2, y3, y4 > 0
Стандартный вид
min (Z= -6x1-5x2-4x3-3x4)
2x1+3x2+2x3+x4+S1=25
4x1+x2+3x3+2x4+S2=30
3x1+5x2+2x3+2x4+S3=42
x1, x2, x3, x4, S1, S2, S3 > 0
Экономический смысл переменных
Xi – количество произведенной продукции
Yj – цена ресурса
Si – количество оставшегося ресурса
| базис | значение |
| x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 0 | -6 | -5 | -4 | -3 | 0 | 0 | 0 | |
| S1 | 25 | 2 | 3 | 2 | 1 | 1 | 0 | 0 | 12,5 |
|
| 30 | 4 | 1 | 3 | 2 | 0 | 1 | 0 | 7,5 |
| S3 | 42 | 3 | 5 | 2 | 2 | 0 | 0 | 1 | 14 |
| Таблица 2 | |||||||||
| базис | значение | x1 |
| x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 45 | 0 | -3,5 | 0,5 | 0 | 0 | 1,5 | 0 | |
| S1
| 10 | 0 | 2,5 | 0,5 | 0 | 1 | -0,5 | 0 | 4 |
| x1 | 7,5 | 1 | 0,25 | 0,75 | 0,5 | 0 | 0,25 | 0 | 30 |
| S3 | 19,5 | 0 | 4,25 | -0,3 | 0,5 | 0 | -0,8 | 1 | 4,59 |
| Таблица 3 | |||||||||
| базис | значение | x1 | x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 59 | 0 | 0 | 1,2 | 0 | 1,4 | 0,8 | 0 | |
| x2 | 4 | 0 | 1 | 0,2 | 0 | 0,4 | -0,2 | 0 | |
| x1 | 6,5 | 1 | 0 | 0,7 | 0,5 | -0,1 | 0,3 | 0 | |
| S3 | 2,5 | 0 | 0 | -1,1 | 0,5 | -1,7 | 0,1 | 1 |
x1 
S2
x2 
Анализ решения
Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц.
Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому его покупать не нужно.
Ресурсы 1 и 2 типа дефицитны, 3 типа избыточен.
Эффективность производства
Z = 6*6.5+5*4+4*0+3*0=59 Z*=25*1.4+30*0.8+42*0=59 Производство в целом эффективно
2*1,4+4*0,8+3*0< 6 6=6 Производство 1 вида продукции эффективно
Вам также может быть полезна лекция "4 Система управления охраной труда".
3*1,4+1*0,8+5*0< 5 5=5 Производство 2 вида продукции эффективно
2*1,4+3*0,8+2*0< 4 5,2> 4 Производство 3 вида продукции не эффективно
1*1,4+2*0,8+2*0< 3 3=3 Т.к. x4 не входит в базис, то оптимальный план не единственен.
Оценить целесообразность покупки 5 ед. второго ресурса по цене 10 ден. ед, т.е. единица ресурса обойдется нам в 2 ден. ед. Мы же готовы покупать только по 0,8 ден. ед. за 1 единицу ресурса.
а1 = 2, а2 = 2, а3 = 4. Цена новой продукции равна 4.
2*1,4+2*0,8+2*0< 4 4,4> 4 Производство 5 вида продукции не эффективно.
