Линейное программирование

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. Линейное программирование – это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Для решения задач линейного программирования потребовалось создание специальных методов. Особенно широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные. Построение математических моделей простейших экономических задач. 1) Задача использования ресурсов. Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья S1, S2 и S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 1. Таблица 1. Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции S1 S2 S3 Прибыль от продукции, грн. 20 40 30 единицы Р1 Р2 2 8 5 5 5 6 50 40 Необходимо составить такой план выпуска продукции, чтобы при его реализации получить максимальную прибыль. Решение: обозначим через х1 количество единиц продукции Р1, а через х2 – количество единиц продукции Р2. Тогда, учитывая количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также запасы сырья, получим систему ограничений 2х1 + 5х2  20 8x1 + 5х2  40 5х1 + 6х2  30 которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысить имеющихся запасов. Если продукция Р1 не выпускается, то х1 = 0; в противном случае х1>0. То же самое получаем и для продукции Р2. таким образом, на неизвестные х1 и х2 должно быть наложено ограничение неотрицательности: х1  0, х2  0. Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2. Реализация х1 единиц продукции вида Р1 и х2 единиц продукции вида Р2 дает соответственно 50х1 и 40х2 грн. прибыли, суммарная прибыль Z = 50x1 + 40x2. Условиями не оговорена неделимость единицы продукции, поэтому х 1 и х2 (план выпуска продукции) могут быть и дробными числами, следовательно, задача имеет бесконечное множество вариантов планов (значений х1 и х2, которые удовлетворяют системе ограничений). Необходимо найти такие неотрицательные значения х 1 и х2, при которых функция Z достигает максимума, т.е. найти максимальное значение линейной функции Z=50x1 + 40x2. При ограничениях 2х1 + 5х2  20 8x1 + 5х2  40 5х1 + 6х2  30 х1  0, х2  0. Построенная линейная функция называется функцией цели (целевой функцией) и совместно с системой ограничений образует математическую модель рассматриваемой экономической задачи. Задачу использования сырья можно легко записать в общем виде, если при выпуске n видов продукции используются m видов сырья. Обозначим через Si ( i = 1, 2, … , m) виды сырья; bi – запасы сырья i-го вида; Рj (j = 1,2, …, n) – виды продукции; аij – количество единиц i – го сырья, идущего на изготовление j – й продукции; Сj – величину прибыли, получаемой при реализации единицы j – й продукции. Условия задачи запишем в таблице 2. Вид сырья Запас сырья S1 S2 … Sm Прибыль от продукции, грн. b1 b2 … bm единицы Таблица 2. Количество единиц сырья, идущих на изготовление единицы продукции Pn Р1 P2 … a11 a21 … am1 a12 a22 … am2 … … … … a1n a2n … amn C1 C2 … Cn Пусть хj – количество единиц j – й продукции, которое необходимо произвести. Тогда математическую модель задачи можно представить в следующем виде. Найти максимальное значение линейной функции z  c1 x1  c2 x2  ...  cn xn при ограничениях a11 x1  a12 x 2  ...  a1n x n  x n 1  b1 a x  a x  ...  a x  x  b  21 1 22 2 2n n n 2 2  ................................................  a m1 x1  a m 2 x 2  ...  a mn xn  x n  m  bm хj  0 (j = 1, 2, …, n) bi  0 (i = 1, 2, …, m) 2) Задача составления рациона. При откорме каждое животное ежедневно должно получить не менее 9 ед. питательного вещества S1, не менее 8ед. вещества S2 и не менее 12 ед. вещества S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 3. Таблица 3 Количество единиц питательных веществ Питательные в 1 кг вещества Вещества Корм 1 S1 3 Корм 2 1 S2 S3 Стоимость 1 кг корма, коп 1 1 2 6 4 6 Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными. Для составления математической модели обозначим через х1 и х2 соответственно количество килограммов корма I и II в дневном рационе. Принимая во внимание значения, приведенные в таблице 3, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений 3х1 + х2  9 x1 + 2х2  8 х1 + 6х2  12 Если корм I не используется в рационе, то х1 = 0; в противном случае х1>0. Аналогично имеем х2  0, т.е. должно выполняться условие неотрицательности переменных: х1  0 х2  0. Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4x1 + 6x2 Задача является многовариантной, х1 и х2 могут принимать бесконечное множество значений. Из этого множества следует выбрать такие х1 и х2, при которых функция Z принимает минимальное значение линейной функции Z = 4x1 + 6x2 При ограничениях 3х1 + х2  9 x1 + 2х2  8 х1  0, х2  0. х1 + 6х2  12 Задачу составления рациона можно легко записать в общем виде, если предусмотреть в рационе m видов питательных веществ в количестве не менее bi ( i = 1, 2, … , m) и использовать n видов кормов. Для составления математической модели задачи через аij ; аij – количество единиц i – го питательного вещества, содержащегося в единице j – го корма; Сj – стоимость единицы j – го корма; хj – количество единиц j – го корма в дневном рационе. Найти минимальное значение линейной функции Z = c1x1 + c2x2 + … + cnxn При ограничениях а11 + а12 + … + а1n  b1 a21 + a22 + … + а2n  b2 ……………………………………. am1 + аm2 + … + аmn  bm 3). Задача составления оптимальных смесей. Во многих отраслях промышленности составляются различные смеси, которые должны удовлетворять определенным требованиям. Большое количество компонентов смеси, разнообразие их технико-экономических характеристик, показателей, которым должна соответствовать смесь, - все это нередко делает задачу составления смесей весьма сложной. Приведем некоторые примеры. Для получения бензина заданного свойства требуется составить смесь из различных видов нефтепродуктов. В технической характеристике авиабензинов наибольшее значение имеют такие показатели, как октановое число, степень сжатия, содержание тетраэтилсвинца и др. Эти показатели для каждого сорта бензина устанавливаются либо в определенных пределах, либо как предельно допустимые. Задача может состоять в том, чтобы определить такой ассортимент выпускаемых бензинов (смесей), при котором имеющиеся нефтепродукты (компоненты смесей) использовались бы с наибольшей рентабельностью, а готовая продукция строго отвечала бы техническим требованиям, установленным для каждого сорта бензина. Сформулируем задачу в виде экономико-математической модели. Примем следующие обозначения: i – виды смесей (i = 1, 2, …,m); j – разновидности нефтепродуктов, являющиеся компонентами смесей (j = 1, 2, …,n); bj – количество нефтепродуктов j-го вида, которыми располагает предприятие для изготовления бензинов (смесей); s – технические свойства нефтепродуктов (например, s = 1- по октановому числу, s = 2 – по степени сжатия, s = 3 – по содержанию тетраэтилсвинца); Psij – коэффициент эффективности единицы нефтепродуктов j-го вида, используемого для изготовления бензина i-го сорта, по техническому свойству s; ci – величина дохода от выпуска единицы бензина i-го сорта; xij – количество нефтепродуктов j-го вида, расходуемое на выпуск бензина i-го сорта; xi – количество бензина i-го сорта, выпускаемое предприятием. Цель данной экономико-математической модели состоит в максимизации общей величины прибыли от реализации продукции: m max Z = ∑ cixi (1) i=1 Ограничения (условия) модели двоякого рода. Во-первых, выпускаемый бензин каждого сорта должен удовлетворять определенным техническим характеристикам, что может быть выражено следующей системой неравенств n ∑ Psij xij  0 (i = 1, 2, …, m; s = 1, 2, 3) (2) j=1 Во-вторых, расход нефтепродуктов на изготовление бензинов всех сортов не должен превышать их количества, что выражается неравенством: m ∑ xij  bj, (j = 1, 2, …, n) (3) (i = 1, 2, …, m) (4) i=1 n ∑ xij  xi j=1 xi  0; xij  0. (5) Целевая функция (1) и системы ограничений (2) – (5) представляют собой одну из возможных формулировок экономико-математической модели оптимального смешивания нефтепродуктов. Во всех этих задачах требовалось найти максимум или минимум линейной функции при условии, что ее переменные принимали неотрицательные значения и удовлетворяли некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные неравенства, так и линейные уравнения. Каждая из этих задач является частным случаем общей задачи линейного программирования. Определение1. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции n F= ∑cjxj j=1 при условиях n (1) ∑ аijxi  bi (i = 1, …, k) (2) (i = k+1, …, m) (3) j=1 n ∑ аijxi = bi j=1 xj  0 (j = 1, …, l; l  n) где аij, bi, cj – заданные постоянные величины и k  m. (4) Определение 2. Функция (1) называется целевой функцией ( или линейной формой) задачи (1) – (4), а условия (2) – (4) ограничениями данной задачи. Определение 3. Стандартной (или симметрической) задачей линейного программирования называется задача, которая состоит в определении максимального значения целей функции (1) при выполнении условий (2) и (4), где k =m и l=n. Определение 4. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k = 0 и l = n. Определение 5. Совокупность чисел Х = (х1, х2, …, хn), удовлетворяющих ограничениям задачи (2) – (4), называется допустимым решением (или планом). Определение 6. План Х* = (х1*, х2*, …, хn*), при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называется оптимальным. Значение целевой функции (1) при плане Ч будем обозначать F (X). Следовательно, Х* оптимальный план задачи, если для любого Х выполняется неравенство F (X)  F (X*) (соответственно F (X)  F (X*)). Различные формы записи задачи ЛП. Приведение произвольной задачи ЛП к каноническому виду. В самом общем виде задача ЛП ставиться следующим образом: Найти значения переменных x1, x2, …, xn, которые бы удовлетворяли условиям a11x1  a12 x2  ...  a1n xn  xn1  b1 a x  a x  ...  a x  x  b  21 1 22 2 2n n n 2 2 (1)  .......... .......... .......... .......... ........   am1 x1  am 2 x2  ...  amn xn  xn m  bm и обеспечиваем требуемый экстремум заданной целевой функции z  c1 x1  c2 x2  ...  cn xn (2) Для решения задачи с помощью универсальных методов она должна быть приведена к каноническому виду, следующего вида: Найти значения переменных x1, x2, …, xn, которые подчиняются условиям x1  0, x2  0, ..., xn  0 (3) a11x1  a12 x2  ...  a1n xn  xn1  b1 a x  a x  ...  a x  x  b  21 1 22 2 2n n n 2 2 (4)  .......... .......... .......... .......... ........   am1 x1  am 2 x2  ...  amn xn  xn m  bm и приносят минимум целевой функции z  c1 x1  c2 x2  ...  cn xn (5) С помощью простых преобразований любая задача линейного программирования может быть сведена к каноническому виду, т.е. представлена в форме записей (3) - (5). Рассмотрим эти преобразования. 1. Из условия (3) ясно, что в каноническом задании на все переменные наложено требование не отрицательности. В экономических задачах это так и есть. Но в общем случае могут встречаться переменные неотрицательные, неположительные и такие, которые могут принимать как положительные, так и отрицательные значения. И в этом общем случае задачу надо свести к таким переменным, каждая из которых подчинялась бы требованию не отрицательности. Как это делать? Пусть по отношению к некоторой переменной xк имеется требование не отрицательности, т.е. хk  0 . Тогда эта переменная никаким преобразованиям не подвергается. Пусть по отношению к некоторой переменной xр имеется требование х p  0 . Это требование противоречит условию (3) канонической формы. В связи с этим вводится новая переменная x p   x p , тогда уже для переменной x p утверждаем x p  0 . Если же по отношению к некоторой переменной x q нет требований по знаку, т.е. она может принимать любые значения (положительные и отрицательные), переменная xq заменяется разностью неотрицательных переменных. Именно, вводятся дополнительные переменные xq  0 и xq  0 и делается замена xq  xq  xq . Этой заменой переменная x q исключается из задачи, а в задаче остаются переменные xq и xq на которые наложено требование не отрицательности. 2. Условия (4) предоставлены в виде упражнений. Это означает, что любое из имеющихся в условии неравенств должно быть переделано в уравнение. Делается это с помощью введения дополнительных не отрицательных балансирующих переменных. Пусть некоторое условие задано в виде неравенства ai1 x1  ai 2 x2  ...  ain xn  bi Введём дополнительную балансирующую переменную xn1  0 . Прибавляем эту переменную к меньшей части неравенства ai1 x1  ai 2 x2  ...  ain xn  xn1  bi Если в исходном задании имеется r неравенств, то вводится r дополнительных переменных: xn1  0, xn2  0, ..., xnr  0 Пример: Пусть задана следующая задача ЛП. 3x1  2 x2  4 x3  x4  12 Z  2 x1  3x2  x3  2 x4  max   2 x1  3x2  x3  2 x4  6 x1  0, x2  0, x3  0  x  2 x  x  3 x  8 2 3 4  1 В данной задаче количество переменных n=4 Количество ограничений m=3. Данную задачу необходимо преобразовать к каноническому виду. На переменные x1,x2 наложено требование не отрицательности. Переменная x3  0 по условию, заменяем её на x3  0 . Переменная x4 не задана, следовательно, ее заменяем разностью x4  x4  x4 . В системе ограничений два неравенства, следовательно, вводится две балансирующих переменных x5  0, x6  0 . Тогда после подстановки, задача будет иметь вид: x1  0, x2  0, x3  0, x4  0, x4  0, x5  0, x6  0 3x1  2 x2  4 x3  x4  x4  x5  12   2 x1  3x2  x3  2 x4  2 x4  x6  6   x1  2 x2  x3  3x4  3x4  8 Z  Z   2 x1  3x2  x3  2 x4  2 x4  min   Примечание: Между задачами максимизации и минимизации имеется следующая связь: max Z(x)=-min[-Z(x)] min Z(x)=-max[-Z(x)] Свойства основной задачи линейного программирования. Рассмотрим основную задачу линейного программирования. n F = ∑ cjxj (1) j=1 при условии n ∑ аijxi = bi (i = 1, …, m ), xj  0 (j = 1, …, n). (2) Перепишем эту задачу в векторной форме: Найти максимум функции F = CX (3) При условиях x1P1 + x2P2 + … + xnPn = P0, X  0 (4) где С = (с1; с2; …; сn), X = (x1; x2; …; xn); CX = скалярное произведение; Р1; …; Рn – m-мерные векторы-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи: Р0 = b1 b2 ; P1 = … bm a11 a21 … am1 ; a12 P2 = a22 ; …; … am2 a1n Pn = a2n … amn Определение: План Х = (х1; х2; …; хn) называется опорным планом основной задачи линейного программирования, если система векторов Рj, входящих в разложение (4) с положительными коэффициентами хj, линейно независима. Определение: Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он называется вырожденным. Определение: Пусть Х1, Х2, …, Хn – произвольные точки евклидова пространства Еn. Выпуклой линейной комбинацией этих точек называется сумма α1Х1 + α2Х2 + … + αnХn, где αi – произвольные неотрицательные числа, сумма которых равна 1: n ∑αi = 1, i=1 αi  0 (i = 1, …, n). Определение: Множество точек называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию. Определение: Точка Х выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух других различных точек данного множества. Свойства: Теорема 1. Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Определение: Непустое множество планов основной задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной. Теорема 2. Если основная задача линейного программирования имеет оптимальный план, то максимальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция задачи принимает более чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин. Теорема 3. Если система векторов Р1, Р2, …, Рk ( k  n ) в разложении ( 4) линейно независима и такова, что х1Р1 + х2Р2 + … + xkPk = P0 ( 5) где все хj  0, то точка Х = ( х1; х2; …; xk; 0; …; 0) является вершиной многогранника решений. Теорема 4. Если Х = (х1; х2; …; хn) – вершина многогранника решений, то векторы Рj, соответствующие положительным хj в разложении (4), линейно независимы. Графический метод решения задач линейного программирования Графический метод основан на геометрической интерпретации задачи ЛП и применяется в основном при решении задач двухмерного пространства и только некоторых задач трёхмерного пространства, т.к. довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно. Пусть задача ЛП задана в двухмерном пространстве, т.е. ограничения содержат две переменные. Найти минимальное значение функции F  c1 x1  c2 x2 (1) при ограничениях a11 x1  a12 x 2  b1 a x  a x  b  21 1 22 2 2 (2)   a m1 x1  a m 2 x 2  bm x1  0, x2  0 (3) Пусть система (2) при условии (3) совместна и её многоугольник решений ограничен. Каждое из неравенств (2) и (3) определяет полуплоскость ограниченной прямой: ai1 x1  ai 2 x2  bi , x1  0, x2  0 Линейная функция (1) при фиксированных значениях F является уравнением прямой линии: c1 x1  c2 x2  const Построим многоугольник решений системы ограничений и график линейной (целевой) функции при F=0. Значения функции F  c1 x1  c2 x2 возрастают в направлении вектора N  c1 ,c2  . Возможны несколько вариантов: Вариант 1: Прямую F=0 передвигаем параллельно самой себе в направлении вектора N. Из рисунка видно, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), а минимум достигается в точке А(x1,x2), значения x1и x2 находятся из системы двух прямых АВ и АЕ. Вариант 2: c1 x1  c2 x2  const , Прямая (F) передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу. Вариант 3: Прямая F, передвигаясь, всё же становится опорной относительно многоугольника решений. Функция ограничена сверху и не ограничена снизу. Вариант 4: Вариант 5: Ограничена снизу, но не ограничена сверху. Ограничена сверху и снизу. Примеры: 1.Задача использования сырья. Найти максимальное значение линейной функции F  50 x1  40 x2 при ограничениях 2 x1  5 x 2  20  x1  0, x 2  0 8 x1  5 x 2  40 5 x  6 x  30 2  1 Решение Построим многоугольник решений. Для этого в системе координат x1 0x2 на плоскости изобразим граничные прямые. 2 x1  5 x 2  20 8 x1  5 x 2  40 5 x1  6 x 2  30 L1   L2  L3  L1  0;4, 10;0 L2  0;8, 5;0 L3  0;5, 6;0 F  0;0,  4;5 Перемещая прямую F вдоль вектора N находим точку пересечения прямой F и многогранника решений в точке C. Данная точка является пересечением прямых L2 и L3. Составляем систему из прямых L2 и L3. x1  3.9 8 x1  5 x 2  40  x 2  1.7 5 x1  6 x 2  30 Fmax  50 * 3.9  40 *1.7  263 Таким образом, для того чтобы получить максимальную прибыль в размере 263 грн., необходимо запланировать производство продукции первого вида 3,9 единицы и 1,7 единиц второго вида. 2.Задача составления рациона. Найти минимальное значение линейной функции F  4 x1  6 x2 при ограничениях 3x1  x 2  9  x1  0, x 2  0  x1  2 x 2  8  x  6 x  12 2  1 Решение Построим многоугольник решений. Для этого в системе координат x1 0x2 на плоскости изобразим граничные прямые. L1  0;9, 3;0 3x1  x 2  9 L1  L2  0;4, 8;0  x1  0, x 2  0  x1  2 x 2  8 L2  L3  0;2, 12;0  x  6 x  12 L  2 3  1 F  0;0,  6;4 Перемещаем прямую F вдоль вектора N до пересечения с многоугольником решений. Пересечение в точке В, которая получена от пересечения прямых L1 и L2. Решая систему уравнений прямых L1 и L2. находим точку (x1, x2). x1  2 3x1  x 2  9  x2  3  x1  2 x 2  8 Fmin  26 Симплексный метод решения задачи линейного программирования Существует такая угловая точка многогранника решений, в которой линейная функция достигает своего наименьшего (наибольшего) значения. В каждой угловой точке многогранника решений соответствует опорный план. Каждый опорный план определяется системой «m» линейно независимых векторов, содержащихся в данной системе из «n», А1, А2, …, Аn. Для отыскания оптимального плана необходимо исследовать только опорные планы. При больших «m» и «n» найти оптимальный план, перебирая все опорные планы задачи, очень трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод, который позволяет, исходя из известного опорного плана задачи, за конечное число шагов получить ее оптимальный план. Каждый из шагов состоит в нахождении нового плана, которому соответствует меньшее значение линейной функции, чем значение этой же функции в предыдущем плане. Процесс продолжают до получения оптимального плана. Если задача не обладает планами или ее линейная функция не ограничена на многограннике решений, то симплексный метод позволяет установить это в процессе решения. Условие оптимальности плана задачи, решаемой на отыскание минимального значения линейной функции. Теорема 1. Если для некоторого вектора Aj выполняется условие Zj – Cj > 0, то план Х0 не является оптимальным, и можно построить такой план Х, для котрого выполняется неравенство Z(X) < Z(X0). Следствие. Если для некоторого плана Х0 разложения всех векторов Аj (j = 1, 2, …, n) в данном базисе удовлетворяют условию Zj – Cj  0, то план Х0 является оптимальным. Условие оптимальности плана задачи, решаемой на отыскание максимального значения линейной функции. Теорема 2. Если для некоторого вектора Aj выполняется условие Zj – Cj < 0, то план Х0 не является оптимальным, и можно построить такой план Х, для котрого выполняется неравенство Z(X) > Z(X0). Следствие. Если для некоторого плана Х0 разложения всех векторов Аj (j = 1, 2, …, n) в данном базисе удовлетворяют условию Zj – Cj  0, то план Х0 является оптимальным. Значения (Zj –Cj) называют оценками плана. Таким образом, для того чтобы план задачи на отыскание минимального значения линейной функции был оптимальным, необходимо и достаточно, чтобы его оценки были положительными и наоборот, для отыскания максимального значения. Пример 1: Найти минимальное значение линейной функции F  x1  x2  3x3 при ограничениях 2 x1  x 2  x3  1  x j  0,  j  1,2,3 4 x1  2 x 2  x3  2 3x  x  5 3  1 Решение: Первоначальный опорный план находится только при неотрицательных правых частях системы ограничений, поэтому умножим на (-1) второе неравенство 2 x1  x 2  x3  1   4 x1  2 x 2  x3  2 x j  0,  j  1,2,3 3x  x  5 3  1 Далее переходим от неравенств к равенствам, прибавляя к левым частям неотрицательные дополнительные переменные х4, х5 и х6. 2 x1  x 2  x3  x 4  1   4 x1  2 x 2  x3  x5  2 3x  x  x  5 3 6  1 Запишем систему уравнений векторной форме 2    1 1  1   0  0  1                x1   4   x 2  2   x3   1  x 4  0   x5 1   x6  0    2  3  0  1   0  0 1   5                Составим симплексную таблицу сj 1 -1 -3 ci А4 А5 А6 А1 А2 А3 А0 А4 1 2 -1 1 1 А5 1 -4 2 -1 2 А6 1 3 1 5 zj — — — — — zj cj — — — — 1 1 3 — Вектора А4 , А5, А6 образуют базис. 1) Рассчитываем элементы строки z j , которые представляют собой сумму произведений элементов столбца c i на элементы соответствующего вектора z1=0*2+0*(-4) +0*3=0 z2=0*(-1) +0*2+0*0=0 z3=0*1+0*(-1) +0*1=0 2) Вычисляем значение элементов строки z j  c j z1  c1  0  1  1`   z 2  c 2  0  (1)  1  Найденный план не является оптимальным, т.к. z1  c1 =-1<0, z 3  c3  0  (3)  3  следовательно, данный план можно улучшить. Среди полученных оценок имеются две положительные z 2  c2  1  0 и z 3  c3  3  0 3) Включаем в базис вектор, которому соответствует max z j  c j   0 , в нашем случае это z 3  c3  3  0 и ему соответствует вектор А3 – данный вектор вводится в базис. 4) Определяем вектор, подлежащий выводу из базиса. Для этого элементы вектора А 0 делим на элементы вектора А3: a 40 1 a60 5   1,   5. a 43 1 a63 1 Находим среди них минимум min(1;5)=1. Элемент а43 называется генеральным. Выводу из базиса подлежит вектор А4, вместо него вводим вектор А3. 5) Ведется пересчет симплексной таблицы, начиная со строки, соответствующей удаленному из базиса вектору А4. Все элементы этой строки делятся на генеральный элемент, после чего рассчитываемая строка получает номер вводимого в базис вектора (в нашем примере: вектор А3). Проведем расчет элементов этой строки (а3j). a 1 ' ' '   0 ; a36  0 a34  44   1 ; a35 1 1 a 43 1 a a a 1 2 1 ' ' ' a31  42   41   2 ; a32  43   1  1 ; a33 a 43 a 43 1 a 43 1 1 a 1 ' a30  40   1 ; a 43 1 Остальные элементы новой симплексной таблицы рассчитываются по формуле: aij'  aij  akj' * aik , где a ij' - определяемые элементы новой симплексной таблицы; a ij - соответствующие элементы предыдущей симплексной таблицы; a kj' - элементы вектор-строки новой симплексной таблицы, соответствующие введенному в базис вектору; aik - элемент вектора-столбца предыдущей симплексной таблицы. сj ci -3 1 -1 — А3 А5 А6 А1 А2 А4 А0 -3 А3 1 2 -1 1 1 А5 1 -2 1 1 3 zj А6 1 1 1 -1 4 — — — — -6 3 -3 — zj cj — — — — -7 4 3 — ' ' a51  a51  a31 * a53  4  2 * (1)  2 ' ' a61  a61  a31 * a63  3  2 *1  1 ' ' a52  a52  a32 * a53  2  (1) * (1)  1 ' ' a62  a62  a32 * a63  0  (1) *1  1 ' ' a54  a54  a34 * a53  0  1* (1)  1 ' ' a64  a64  a34 * a63  0  1*1  1 ' ' a50  a50  a30 * a53  2  1* (1)  3 ' ' a60  a60  a30 * a63  5  1*1  4 Вычисляем z j : z1  (3) * 2  0 * (2)  0 *1  6 z 2  (3) * (1)  0 *1  0 *1  3 z3  (3) *1  0 *1  0 * (1)  3 Вычисляем z j  c j : z1  c1  6  1  7 z 2  c2  3  (1)  4 z3  c3  0  (3)  3 max 4;3=4 Следовательно, в базис вводится вектор А2 Определяем генеральный элемент a50 3 a 4   3 , 60   4 a52 1 a62 1 min 3;4=3 Следовательно, вектор А5 подлежит выводу из базиса, вместо него вводится вектор А2, генеральный элемент а52  1 . Строим новую симплекс таблицу: сj -1 -3 1 ci — А2 А3 А6 А1 А4 А5 А0 -1 А2 1 -2 1 1 3 -3 А3 1 2 1 4 А6 1 3 -2 -1 1 zj — — — — 2 -7 -4 — zj cj — — — — 1 -7 -4 Вычисляем значения элементов введенного в базис вектора a a a a 2 1 ' ' ' '  53   0 ; a 26  56   0 ; a 21 a 22  51   52   1 ; a 23  2 ; a52 1 a52 1 a52 a52 1 1 a a a 1 1 3 ' ' ' a 24  54   1 ; a 25  55   1 ; a 20  50   3 . a52 1 a52 1 a52 1 Вычисляем остальные элементы симплекс таблицы по формуле: aij'  aij  akj' * aik ' ' a32  a32  a22 * a32  1  1* (1)  0 ' ' a62  a62  a22 * a62  1  1*1  0 ' ' a33  a33  a23 * a32  1  0 * (1)  1 ' ' a63  a63  a23 * a62  0  0 *1  0 ' ' a36  a36  a26 * a32  0  0 * (1)  0 ' ' a66  a66  a26 * a62  1  0 *1  1 ' ' a31  a31  a21 * a32  2  (2) * (1)  0 ' ' a61  a61  a21 * a62  1  (2) *1  3 ' ' a34  a34  a24 * a32  1  1* (1)  2 ' ' a64  a64  a24 * a62  1  1*1  2 ' ' a35  a35  a25 * a32  0  1* (1)  1 ' a65  a65  a25 * a62  0  1*1  1 ' ' a30  a30  a20 * a32  1  3 * (1)  4 Вычисляем значения строки z j : ' ' a60  a60  a20 * a62  4  3 *1  1 . z1  1* (2)  (3) * 0  0 * 3  2 z2  1*1  (3) * 2  0 * 0  7 z3  1* 3  (3) *1  0 * (1)  6 . Вычисляем элементы строки z j  c j : — z1  c1  2  1  1 z 2  c2  7  0  7 z3  c3  6  0  6 max=1 Максимум соответствует вектору А1, следовательно, он вводится в базис. Определяем генеральный элемент: а60 1  , а61 =3 – генеральный элемент. а61 3 Вектор А6 подлежит выводу из базиса, а вместо него в базис вводится вектор А1. Строим новую симплексную таблицу: сj ci -3 -1 1 — А3 А2 А1 А5 А4 А6 А0 4 -3 А3 1 1 2 -1 А2 1 1 1 2 1 А1 1 1 zj — — — — zj cj — — — — 3 -1 3  11 3  11 3 -7 -7 3 3 -1 3 -1 3 11 1 3 3 — — Проведем расчет элементов строки а1 j : a a63 0 a 3 ' '  62   0 ; a11  61   1 ;   0 ; a12 a61 3 a61 3 a61 3 a a a 1 1 1 ' ' ' a15  65   64   0 ; a16  66  ;   ; a14 a61 3 a61 3 a61 3 3 a 1 ' a10  60  . a61 3 ' a13  Вычисляем остальные элементы таблицы по формуле aij'  aij  akj' * aik : ' ' a33  a33  a13 * a31  1  0 * 0  1 ' ' a32  a32  a12 * a31  0  0 * 0  0 ' ' a31  a31  a11 * a31  0  1* 0  0  1 ' ' a35  a35  a15 * a31  1     * 0  1  3 ' ' a34  a34  a14 * a31  2  0 * 0  2 1 ' ' a36  a36  a16 * a31  0  * 0  0 3 1 ' ' a30  a30  a10 * a31  4  * 0  4 3 ' ' a23  a23  a13 * a21  0  0 * (2)  0 Рассчитываем элементы строки z j : ' ' a22  a22  a12 * a21  1  0 * (2)  1 ' ' a21  a21  a21 * a21  2  1* (2)  0 1  1 ' ' a 25  a 25  a15 * a 21  1     * (2)  3  3 ' ' a24  a24  a14 * a21  1  0 * (2)  1 1 2 ' ' a26  a 26  a16 * a21  0  * (2)  3 3 1 11 ' ' a20  a 20  a10 * a 21  3  * (2)  . 3 3 1 11  1 z 5  3 *1  (1) *  1 *      3 3  3 z 4  3 * 2  (1) *1  1* 0  7 2 1 1 z 6  3 * 0  (1) *  1 *   . 3 3 3 Рассчитываем элементы строки ( z j  c j ): 11 11 0   3 3 z 4  c4  7  0  7 z 5  c5   х1 , x2 ,..., xn т.к. в строке z j  c j все оценки отрицательные, то достигнут оптимальный план.   1 11  0  0 1   4  x1  ; x2  ; x3  4         3 3 получаем оптимальный план x1  0   x2 1   x3  0   11  3 46 1   0  0  Fmin          1  3  3  Пример 2: Для изготовления различных изделий А, В, С предприятие использует три вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием приведены в таблице: Вид сырья А 18 6 5 Нормы затрат сырья на одно изделие В С 15 12 4 8 3 3 Общее кол-во сырья 360 192 180 I II III Цена данного 9 10 16 изделия в грн. Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида. Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной. Решение: Составим математическую модель задачи. Искомый выпуск изделий обозначим через хi: — изделия А – х1 — изделия В – х2 — изделия С – х3, т.к. имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные х1, х2, х3 должны удовлетворять системе неравенств: 18 x1  15 x2  12 x3  360  6 x1  4 x2  8 x3  192 5 x  3x  3x  180 2 3  1 х1≥0, х2 ≥0, х3≥0 Общая стоимость произведенной продукции составляет F  9 x1  10 x2  16 x3 . Решаем симплексным методом. Ответ: х1=0; х2=8; х3=20 и Fmax=400 грн. и не использовано 96 кг третьего вида. Метод искусственного базиса При решении задач симплексным методом было показано, что если ограничения задачи ЛП содержат единичную матрицу порядка ”m”, то тем самым при неотрицательных правых частях уравнений определен первоначальный план, исходя из которого, с помощью симплексного метода находится оптимальный план. Если ограничения задачи ЛП можно преобразовать к виду АХ≤А0 при А0≥0, то система ограничений всегда содержит единичную матрицу. Многие задачи ЛП, имеющие решения, не содержат единичной матрицы и не приводят к указанному виду. В этом случае для решения задач применяется метод искусственного базиса. Рассмотрим общую задачу ЛП. Найти минимальное значение линейной функции z  c1 x1  c2 x2  ...  cn xn при ограничениях a11x1  a12 x2  ...  a1n xn  b1 a x  a x  ...  a x  b  21 1 22 2 2n n 2 x j  0,  j  1,2,..., n   ........................................ am1 x1  am 2 x2  ...  amn xn  bm где bi  0 и система ограничений не содержит единичной матрицы. Для получения единичной матрицы к каждому равенству прибавим по одной переменной xni  0, i  1, m , которые назовем искусственным и рассмотрим расширенную задачу, связанную с отысканием наименьшего значения линейной функции z  c1 x1  c2 x2  ...  cn xn  Mxn1  Mxn2  ...  Mxnm (1) при ограничениях a11x1  a12 x2  ...  a1n xn  xn1  b1 a x  a x  ...  a x  x  b  21 1 22 2 2n n n 2 2 (2)  .......... .......... .......... .......... ........   am1 x1  am 2 x2  ...  amn xn  xn m  bm хj  0 (j = 1, 2, …, n+m) (3)   Величина М предполагается достаточно большим положительным числом, если задача решается на отыскание минимального значения линейной функции, и достаточно малым отрицательным числом, если находится максимальное значение линейной функции. Единичные векторы Аn+1, An+2, …, An+m, соответствующие искусственным переменным, образуют базис. Теорема 1: Если в оптимальном плане x  x1 , x2 ,..., xn ,0,...,0 расширенной задачи   искусственные переменные xn1  0, i  1, m , то план x  x1 , x2 ,..., xn  является оптимальным планом исходной задачи. Процесс нахождения решения задачи методом искусственного базиса включает следующие основные этапы: 1. Составляют расширенную задачу (1) – (3). 2. Находят опорный план расширенной задачи. 3. С помощью обычных вычислений симплекс-метода исключают искусственные векторы из базиса. В результате либо находят опорный план исходной задачи, либо устанавливают ее неразрешимость. 4. Используя найденный опорный план задачи, либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость. Пример 1: Найти максимальное значение линейной функции z  5x1  3x2  4 x3  x4 при ограничениях  x1  3x2  2 x3  2 x4  3  2 x1  2 x2  x3  x4  3 x j  0,  j  1,2,3,4 Решение: Система ограничений не содержит единичной матрицы. Прибавим к каждому уравнению по одной неотрицательной искусственной переменной (соответственно х5≥0 и х6≥0) и перейдем к расширенной задаче. Найти максимальное значение линейной функции z  5x1  3x2  4 x3  x4  Mx5  Mx6 при ограничениях  x1  3x2  2 x3  2 x4  x5  3  2 x1  2 x2  x3  x4  x6  3  x j  0, j  1,6  или в векторной форме A1 x1  A2 x2  A3 x3  A4 x4  A5 x5  A6 x6  A0 Выберем за базис единичные векторы А5, А6, которые и образуют искусственный базис. Приравнивая свободные неизвестные нулю: х1=х2=х3=х4=0, получаем первоначальный опорный план расширенной задачи x0  0,0,0,0,3,3 , которому соответствует разложение x5 A5  x6 A6  A0 . Составим симплексную таблицу сj ci 5 3 4 -1 -М -М А1 А2 А3 А4 А5 А6 А0 -М А5 1 3 2 2 1 3 -М А6 2 2 1 1 1 3 -5 -3 -4 1 -3 -5 -3 -3 -6 m+1 m+2 zj cj В строку (m+1) — пишется слагаемое независящее от М. В строку (m+2) — пишется слагаемое, зависящее от М. Значения оценок, строк (m+1) и (m+2) находим по формулам: z0  3 * M  3 * M  0  6M z1  c1  1* M  2 * M  5  5  3M z 2  c2  3 * M  2 * M  5  3  5M z3  c3  2 * M  1* M  4  4  3M z 4  c4  2 * M  1* M  1  1  3M z5  c5  M  M  0 z6  c6  M  M  0 Если М заранее не зафиксировано, оценки z j  c j являются линейными функциями величины М, причем функция состоит из двух слагаемых, одно из которых зависит от М, а второе – не зависит. В строке (m+2) имеются отрицательные оценки, поэтому опорный план х0 расширенной задачи не является оптимальным и его можно улучшить. Вычислим max z j  c j  5 , следовательно, вводим в базис вектор А2. Генеральный элемент а52=3. А5 – вектор, исключаемый из базиса. Составим симплексную таблицу сj 5 3 4 -1 -М -М А1 А2 А3 А4 А5 А6 А0 3 1 2 2 1 3 i ci 1 3 А2 1 2 -М А6 4 m+1 zj cj m+2 3 1 3 3 2 3 1 3 1 3 1 1 -4 -2 3 1 3 -3 1 1 5 -1 3 3 3 2 1 1 z 0  с 0  3 *1  1* M  0  3  M z 4  c4  3 *  * M  (1)  3  M 3 3 3 1 4 4 z1  c1  3 *  * M  5  4  M 1 2 5 3 3 3 z5  c5  3 *  * M  (М )  1  М 3 3 3 z2  c2  3 *1  0  3  0 z6  c6  3 * 0  M  (М )  0 2 1 1 z3  c3  3 *  * M  4  2  M 3 3 3 4 max z j  c j  , соответствует вектору А1 – который вводится в базис, исключаем вектор А6. 3 4 Генеральный элемент а61= . Опорный план х01  0;1;0;0;1 . 3 Строим новую симплексную таблицу сj 5 3 4 -1 -М -М i ci 1 3 2 5 m+1 А1 А2 А3 А4 А5 А2 1 3 3 1 А1 1 zj cj m+2 А6 1 А0 3 4 1 4 4 1 4 2 1 2 -3 2 -1 3 6 1 1 3 4 4 3 4 4 3 3  Опорный план х02   ; ;0;0;0  . Данный опорный план является опорным планом и для 4 4  исходной задачи, но не является оптимальным, т.к. в строке (m+1) имеется отрицательная оценка z3  c3  3  0 . Дальнейший процесс проводим только по строке (m+1). Вектора А5 и А6 снова попасть в базис не могут, т.к. они искусственные. Следовательно, в базис вводится вектор А 3, а вектор А2 исключается. 3 Генеральный элемент а23  . 4 Строим новую симплексную таблицу сj 5 3 4 -1 -М -М А1 А2 А3 А4 А5 А6 А0 3 1 1 2 1 1 3 i ci 1 3 А2 4 2 5 А1 1 1 3 1 3 2 3 3 1 zj cj m+1 4 1+М 5 2+М 9 все оценки строки (m+1) больше либо равны нулю. Получили оптимальный опорный план х03  (1;0;1;0) : Z max  9 . Пример 2. Найти максимальное значение линейной функции z  3x1  4 x2  x3  2 x4  x5 при ограничениях  x1  2 x2  3x3  x4  5 x5  5  2 x1  3x2  5 x3  2 x4  7 x5  8 3x  x  2 x  6 x  2 x  6 3 4 5  1 2 xj≥0, (j= 1,5 ). Решение: Для решения задачи используем метод полного исключения, поочередно вводя векторы в базис. Запишем ограничения в векторной форме 1   2 3 1    5 5             х1  2   х2  3   х3   5   х4  2   х5   7    8  3 1    2 6  2   6             Строим первую симплексную таблицу сj 3 4 1 2 -1 i Базис А0 ci А1 А2 А3 А4 А5 1 — — 5 1 2 -3 1 -5 2 — — 8 2 3 -5 2 -7 3 — — 3 1 -2 6 2 6 Введем в базис вектор, у которого aij  1 : — если их несколько, то выбирают любой; — если такого нет, то берут первый, а все элементы строки делят на значение а11 и данный элемент считается генеральным. В данном примере а11=1, вводим в базис вектор А1. Строим новую симплексную таблицу сj 3 4 1 2 -1 i Базис А ci А1 А2 А3 А4 А5 1 А1 3 5 1 2 -3 1 -5 2 — — 1 1 1 3 2 2 2  17 3 7 -1 3 3 Строка вектора записывается в новую таблицу без изменения (т.к. а11=1). Нам необходимо получить а21=0 и а31=0. Умножим элементы строки 2 на  1 и сложим с первой строкой, а полученный результат 2 записываем в строку 2: 1  1  1  1 а22  3 *     2  а24  2 *     1  0 а20  8 *     5  1 2  2  2  2 1 3  1  1  1 а25  7 *     5   а21  2 *     1  0 а23  5 *     3   2 2  2  2  2 3 — — 3   Заполним строку 3 таблицы. 5  1 Умножаем элементы строки 3 на    и сложим с первой строкой, результат запишем в строку  3 3: 5  1  1  1 а34  6 *     1  1 а30  6 *     5  3 а32  1*     2  3  3  3  3 17 7  1  1  1 а35  2 *     5   а31  3 *     1  0 а33  2 *     3   3 3  3  3  3 Введем в базис еще один вектор А2. Правила выбора вектора те же самые, что и для первого вектора, но для рассмотрения выбираем 1 элемент а22, т.к. в нашем примере а22  , то домножим строку 2 на 2. 2 Строим новую таблицу сj 3 4 1 2 -1 i Базис А ci А1 А2 А3 А4 А5 1 А1 3 1 1 -1 1 1 2 А2 4 2 1 -1 -3 1 2 -1 3 3 3 Необходимо чтобы элементы а12=0 и а32=0; для этого строку 2 на (-2) и сложим его с первой строкой, результат записывается в строку 1: а12  1*  2  2  0 а14  0 *  2  1  1 а10  2 *  2  5  1 — 3 2 — 1 а13  1*  2  3  1 3 а15  3 *  2  5  1  5 Для заполнения строки 3 умножим строку 2 на    и сложим с третьей строкой; результат  3 запишем в строку три. 1  5  5 5  5 а34  0 *     1  1 а32  1*      0 а30  2 *     3   3  3 3  3  3 2  5  17  5  5 4 1 а35  3 *       а31  0 *     0  0 а33  1*      3  3  3 3  3 3 3 Введем в базис третий вектор, легче всего ввести в базис вектор А4, т.к. его элемент в строке 3 равен (-1), домножим строку 3 на (-1) и результат запишем в новую таблицу в строку 3. сj 3 4 1 2 -1 i Базис А ci А1 А2 А3 А4 А5 1 А1 3 2 А2 4 3 1 5 2 1 -1 4 3 1 -3 3 2 2 1 3 3 3 32 zj cj  26  26 m+1 3 3 3 Выполним преобразования, приводимые к тому, чтобы элементы а24=0 и а14=0, но т.к. а24=0, то строка заполняется из предыдущей таблицы без изменений. Для заполнения строки 1 данной таблицы домножим строку три на (-1) и сложим с первой строкой; результат записывается в строку 1: 3 А4 2 1 а14  1*  1  1  0 а12  0 *  1  0  0 1 4 а10   *  1  1  3 3 а11  0 *  1  1  1 2 1 а15  *  1  1  3 3 2 5 а13   *  1  1   3 3 Выполним расчет оценок ( z j  c j ) строки (m+1): 2 1 2 32 z0  с0  3 *  4 * 2  2 *  2  8   3 3 3 3 z1  c1  3 *1  4 * 0  2  0  3  0 z2  c2  3 * 0  4 *1  2 * 0  4  0 2 4 26  5 z3  c3  3 *     4 * (1)  2 *  1  5  4   1   3 3 3  3 z4  c4  3 * 0  4 * 0  2 *1  2  0 2 4 30 4  1 z5  c5  3 *     4 * (3)  2 *  1  1  12  1      26 3 3 3 3  3 Среди оценок ( z j  c j ) строки (m+1) имеются две отрицательные оценки, следовательно, план 1  4 х0   ;2;0; ;0  не является оптимальным. Продолжим решение. 3  3 26 max z j  c j   , соответствующий вектору А3, который вводится в базис. 3 Определим вектор, выводимый из базиса. Для этого элементы вектора А0 делим на элементы вектора А3 и выбираем среди частных минимальное. 2 min=1, генеральный элемент а43= , следовательно в базис вводится вектор А4. 3 Строим новую симплексную таблицу сj 3 4 1 2 -1 i Базис А0 ci А1 А2 А3 А4 А5 1 А1 3 2 А2 4 5 3 А3 1 1 3 2 1 5 1 3 1 3 2 39 zj cj m+1 2 Произведем расчет элементов строки введенного вектора А3: a a 1 2 1 2 ' ' a30  40  :  a31  41  0 :  0 a43 3 3 2 a43 3 a a 2 2 2 3 ' ' a33  43  :  1 a34  44  1 :  a43 3 2 a43 3 3 2 2 2 -2 2 1 13 a42 2  0:  0 a43 3 a 2 2 ' a35  45  :  1 a43 3 3 ' a32  ' ' Вычисляем остальные элементы симплексной таблицы по формуле: aij  aij  akj * aik 2 1  5 2 5 9  *      3 2  3 3 6 3  5 ' ' a11  a11  a31 * a13  1  0 *     1  3  5 ' ' a12  a12  a32 * a13  0  0 *     0  3 ' ' a10  a10  a30 * a13  5  5 ' ' a13  a13  a33 * a13    1*     0 3  3 3  5 5 ' ' a14  a14  a34 * a13  0  *     2  3 2 1  5 1 5 ' ' a15  a15  a35 * a13   1*       2 3  3 3 3 1 5 ' ' a20  a20  a30 * a23  2  * (1)  2 2 ' ' a21  a21  a31 * a23  0  0 * (1)  0 ' ' a22  a22  a32 * a23  1  0 * (1)  1 ' ' a23  a23  a33 * a23  1  1* (1)  0 2 3 ' ' a24  a24  a34 * a23  0  * (1)  3 2 ' ' a25  a25  a35 * a23  3  1* (1)  2 Вычисляем оценки ( z j  c j ) строки (m+1): 5 1 39 z0  с0  3 * 3  4 *  1*  2 2 2 5 3 3 15 3 z4  c4  3 *  4 *  1 *  2   6   2  13 2 2 2 2 2 z5  c5  3 * 2  4 * (2)  1*1  1  0 Среди оценок ( z j  c j ) отрицательных значений нет, следовательно, достигнут оптимальный план х04  3;4;1;0;0 , z max  39 2 Геометрическая интерпретация симплексного метода В простейшем случае симплексный процесс может быть интерпретирован как движение по соседним угловым точкам многогранника решений, связанных с уменьшением (увеличением) значения линейной функции. Две угловые точки называются соседними, если они расположены на одном ребре многогранника решений. Пусть имеется задача на отыскание максимального значения линейной функции z  c1 x1  c2 x2 и на рисунке 1 изображен многоугольник K и ее решений. Допустим, что в процессе преобразования системы ограничений построен первоначальный опорный план, соответствующий угловой точке А. Тогда прямая c1 x1  c2 x2  const проходит через точку А, и z имеет значение z(A). Включение вектора в базис по min(zj-cj) приводит к тому, что прямая c1 x1  c2 x2  const проходит через точкуQ, и z принимает значение z(Q), причем z(Q)> z(A). В результате последующей итерации приходим к точке f, в которой линейная функция достигает максимального значения. Если в результате исходного опорного плана была принята точка С, то алгоритм симплексного метода приводит в точке D, Е, F, т.е. для нахождения оптимального решения требуется четыре итерации (4 симплексных таблицы). Таким образом, количество итераций в симплексном процессе определяется первоначальным опорным планом и количеством угловых точек, встречающихся на пути движения прямой с1х1  с2 х2  const от первоначального плана до оптимального. Двойственность в линейном программировании Нами было рассмотрено решение задач ЛП, что в принципе, является главным моментом при изучении ЛП. Однако имеется еще ряд вопросов, на которые необходимо ответить: Как проверить факт существования решения задачи линейного программирования? С помощью симплекс-метода можно определить, имеет ли решение данная задача, но эта проверка сводится фактически к процессу решения задачи, т.е. можно долго решать задачу симплекс-методом и, в конце концов, убедиться в отсутствии решения. Хотелось бы иметь более экономные способы проверки факта существования решения. Другой вопрос – получение условий оптимальности, с помощью которых можно было бы определить, является ли данный план оптимальным или нет (не пренебрегая к процедуре симплекс-метода). Хотелось бы иметь аппарат для проведения качественных исследований задачи ЛП. Для ответов на поставленные вопросы полезной оказалась теория двойственности. Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей в нахождении максимального значения функции При ограничениях F = c1x1 + c2x2 + … + cnxn a11x1 + a12x2 + … + a1nxn  b1 a21x1 + a22x2 + … + a2nxn  b2 ………………………………. ak1x1 + ak2x2 + … + aknxn  bk ………………………………. am1x1 + am2x2 + … + amnxn  bm xj  0 (j = 1, 2, …, n) (1) (2) (3) Определение. Задача, состоящая в нахождении минимального значения функции При ограничениях F* = b1u1 + b2u2 + … + bmum a11u1 + a21u2 + … + an1un  c1 a12u1 + a22u2 + … + an2un  c2 ………………………………. a1ku1 + a2ku2 + … + amkun  ck ………………………………. a1nu1 + a2nu2 + … + amnun  cm (4) (5) ui  0 (i = 1, 2, …, m) (6) называется двойственной по отношению к задаче (1) – (3). Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственной парой. Особенности двойственной задачи: 1. если прямая задача является задачей максимизации, то двойственная задача будет задачей минимизации, и наоборот. 2. коэффициенты целевой функции прямой задачи с1 , с2 ,..., сn становятся свободными членами ограничений двойственной задачи. 3. свободные члены ограничений прямой задачи b1 , b2 ,..., bm становятся коэффициентами целевой функции двойственной задачи 4. матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи 5. знаки неравенств в ограничениях изменяются на обратные 6. число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи. Переменные u1 , u 2 ,..., u m двойственной задачи иногда называют «теневыми ценами». Двойственную задачу выгоднее решать, чем исходную прямую, если прямой задаче при малом количестве переменных (m>n) имеется большое количество ограничений. Связь между оптимальными решениями прямой и двойственной задачи устанавливается следующими теоремами теории двойственности: Теорема 1. Если x 0 и u 0 - допустимые решения прямой и двойственной задач, т.е. если A x  A0 и A u  c , то c x0  A0u 0 , т.е. значения целевой функции прямой задачи никогда не превышают значений целевой функции двойственной задачи. Теорема 2. Если x 0 и u 0 - допустимые решения прямой и двойственной задачи и если c x0  A0 u 0 , то x 0 , u 0 оптимальные решения этих задач. Теорема 3. Если в оптимальном решении прямой задачи какой-то ресурс используется не полностью, то его «теневая цена» должна быть равна нулю, т.е. A i  X опт  bi  0  U iооп  0 ,    где A i  - i-я строка матрицы ограничений прямой задачи. Теорема 4. Прямая и двойственная задачи имеют оптимальные решения тогда и только тогда, когда обе они имеют допустимые решения. Теорема 5. Допустимый вектор x 0 оптимален тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение u 0 , что с х0  A0u 0 . Рассмотрим пример. Завод производит три вида продукции x1 , x2 , x3 , каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пусть с1 , с2 , с3 - прибыль от реализации единицы соответствующего вида продукции. Определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль. Эта задача записывается так: Найти max c1 x1  c2 x2  c3 x3  (1) при ограничениях a11 x1  a12 x 2  a13 x3  b1  a 21 x1  a 22 x 2  a 23 x3  b2 , a x  a x  a x  b 32 2 33 3 3  31 1 где a1 j , a2 j , a3 j - время, необходимое для обработки единицы j-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j=1,2,3); b1 , b2 , b3 - недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков. Обозначим u1 , u 2 , u3 - цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогда a11u1  a21u 2  a31u3 - можно трактовать как расходы на изготовление единицы продукции первого вида; a12u1  a22u 2  a32u3 - расходы на изготовление единицы продукции второго вида; a13u1  a23u 2  a33u3 - расходы на изготовление единицы продукции третьего вида. Для величин расходов выполняются следующие соотношения a11u1  a 21u 2  a31u 3  c1  (2) a12u1  a 22u 2  a32u 3  c 2 a u  a u  a u  c 23 2 33 3 3  13 1 Учитывая, что b1 , b2 , b3 - использованный ресурс машинного времени для каждого из станков, b1u1  b2 u 2  b3u3 - суммарные расходы на производство. Требуется найти u1 , u 2 , u3 удовлетворяющие условиям (2), при которых минимизируются суммарные расходы на производство (3) min g u   b1u1  b2 u 2  b3u3 причем u1  0, u 2  0, u3  0 . Пример: Исходная задача ЛП имеет вид. Найти max f x1 , x2   c1 x1  c2 x2  4 x1  3x2 при ограничениях  1 * x1  0 * x 2  4000  0 * x1  1 * x 2  6000  2 1 * x1  x 2  6000 3  Для нее двойственная задача будет иметь вид. Найти max g u1 , u 2   min 4000u1  6000u 2  6000u3  при ограничениях 1 * u1  0 * u 2  1 * u 3  4   2 0 * u1  1 * u 2  * u 3  3  3  Решаем обе задачи. 1. Решаем прямую задачу. Добавим в условия ограничений балансирующие переменные x3 , x4 , x5 и перепишем задачу. Найти max f x1 , x2   c1 x1  c2 x2  4 x1  3x2   x1  x3  4000  при ограничениях  x 2  x 4  6000  2  x1  x5  6000 3  Составляем симплексную таблицу. Базис A3 , A4 , A5 . сj 4 3 А0 А1 А2 А3 А4 А5 I ci 1 А3 4000 1 1 2 А4 6000 1 1 3 А5 6000 1 2 3 1 -4 -3 M+1 zj cj В базис вводим вектор А1, т.к. max   4 ,  3   4 . Из базиса выводится вектор А3, т.к.  4000 6000  min  ;   4000 . Генеральный элемент a13  1 . 1   1 Составляем новую симплексную таблицу сj 4 3 А0 А1 А2 А3 А4 А5 I ci 1 4 А1 4000 1 1 2 А4 6000 1 1 3 А5 2000 2 3 -1 1 16000 -3 4 zj cj M+1 aij'  aij  akj' * aik   a50  a10  * a51  6000  4000 *1  2000 a50   a51  a11  * a51  1  1*1  0 a51 2 2   a52  a12  * a51   0 *1  a52 3 3   a53  a13  * a51  0  1*1  1 a53   a54  a14  * a51  0  0 *1  0 a54   a55  a15  * a51  1  0 *1  1 a55 В базис вводим вектор A2 , т.к. max   3   3 . Из базиса выводится вектор A5 , т.к.  4000 6000 2000    3000 . Генеральный элемент a  2 . min  ; ; 52 2  3 1  0 3   Составляем новую симплексную таблицу сj 4 3 А0 А1 А2 А3 А4 А5 А1 4000 1 1 А4 3000 3 1 3 3 А2 3000 1 3 25000 9 I ci 1 4 2 3 zj cj M+1 2 3 2 1 2 2 2 2 a  aij  a * aik , k=2. ' ij ' kj   a40  a20  * a42  6000  3000 *1  3000 a40   a41  a21  * a42  0  0 *1  0 a41   a42  a22  * a42  1  1*1  0 a42   a10  a20  * a12  4000  3000 * 0  4000 a10   a11  a21  * a12  1  0 * 0  1 a11   a12  a22  * a12  0  1* 0  0 a12 3  3   a 43  a 23  * a 42  0     *1  a 43 2  2   a44  a24  * a42  1  0 *1  1 a44 3 3   a 45  a25  * a 42  0  *1   a 45 2 2 z 0  c0  4 * 4000  0 * 3000  3 * 3000  25000  3   a13  a 23  * a12  1     * 0  1 a13  2   a14  a24  * a12  0  0 * 0  0 a14   a15  a25  * a12  1  0 * 0  0 a15 z1  c1  4 *1  0 * 0  3 * 0  4  0 3 9 1  3 z 3  c3  4 * 1  0 *  3 *     4    2 2 2  2 max z j  c j   1 . В базис вводится вектор A3 . 2  4000 3000 3000    2000 . Из базиса выводится вектор A . Разделим элементы min  ; ; 4 3  1  3  2 2   3 вектора-строки A4 на генеральный элемент a 43  . 2   Составляем новую симплексную таблицу сj 4 3 А0 А1 А2 А3 А4 А5 1 i ci 1 4 А1 2000 1 2 2 А3 2000 1 2 3 3 А2 6000 1 26000 M+1 zj cj 3 3 -1 1 1 4 3 aij'  aij  akj' * aik , k=3.   a10  a30  * a13  4000  2000 *1  2000 a10   a11  a31  * a13  1  0 *1  1 a11   a12  a32  * a13  0  0 *1  0 a12   a13  a33  * a13  1  1*1  0 a13 2 2   a14  a34  * a13  0  *1   a14 3 3   a15  a35  * a13  0  1*1  1 a15  3   a 20  a30  * a 23  3000  2000 *     6000 a 20  2  3   a 21  a31  * a 23  0  0 *     0 a 21  2  3   a 22  a32  * a 23  1  0 *     1 a 22  2 3  3   a 23  a33  * a 23    1 *     0 a 23 2  2 2  3   a 24  a34  * a 23  0  *     1 a 24 3  2 3  3   a 25  a35  * a 23   1 *     0 a 25 2  2 z 0  c0  4 * 2000  0 * 2000  3 * 6000  26000 2 1  2 z 4  c4  4 *     0 *  3 *1  0  3 3  3 z5  c5  4 *1  0 * (1)  3 * 0  4 max f x1 , x2   26000, x0  2000;6000;0;0;0 2. Решим двойственную задачу. Для решения задачи введем балансирующие переменные u 4 ,u 5 и перепишем задачу. Найти min g u1 , u 2 , u3   4000u1  6000u 2  6000u3 При ограничениях u1  u 3  u 4  4   2 u 2  3 u 3  u 5  3 Пусть u1 ,u 2 будут базисными. Построим симплексную таблицу. сj 4000 6000 6000 А0 А1 А2 А3 А4 А5 1 -1 3 -1 2000 -4000 -6000 i ci 1 4000 А1 4 1 2 6000 А2 3 1 32000 zj cj M+1 2 z 4  c4  1* 4000  0  4000 z 0  c0  1 * 4000  * 6000  6000  2000 3 max z j  c j   2000 . В базис вводим вектор A3 . 2 z5  c5  1* 6000  0  6000 4 3    4 . Из базиса выводится вектор A . Генеральный элемент a  1 . min  ; 13 1  1 2  3  Составим новую симплексную таблицу сj 4000 6000 6000 i ci 1 6000 2 6000 M+1 А0 А1 А2 А3 А4 А5 А3 4 1 1 -1 А2 1 2 3 1 2 3 -1 -2000 -2000 -6000 zj cj 3 26000 aij'  aij  akj' * aik , k=3. 2 1  3 3 2 2   a21  a31  * a 23  0  1 *   a 21 3 3 2   a 22  a32  * a23  1  0 *  1 a 22 3 2 2   a 23  a33  * a 23   1 *  0 a 23 3 3 2 2   a 24  a34  * a 23  0  (1) *  a24 3 3 2   a25  a35  * a 23  1  0 *  1 a25 3   a 20  a30  * a23  3  4 * a 20 1 z 0  c0  4 * 6000  * 6000  0  26000 3 2 z1  c1  1 * 6000  * 6000  4000  2000 3 z 2  c2  0 * 6000  6000  6000  0 2 z 4  c4  1 * 6000  * 6000  0  2000 3 z5  c5  6000 min g u1 , u 2 , u3   26000 , т.е. получили, что max f x1 , x2   min g u1 , u 2 , u3   26000 . Выполнено условие теоремы 2.