Каноническая форма ЗЛП - задача линейного программирования вида ax = b где a - матрица коэффициентов, b - вектор ограничений.

Назначение сервиса . Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную x j не наложено ограничение, то она заменяется на разность дополнительных переменных, x j = x j1 - x j2 , x j1 ≥ 0, x j2 ≥ 0.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10

Как привести задачу линейного программирования к канонической форме

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

Математическая модель называется канонической , если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис , определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b i ≥ 0).

Переменные, входящие в одно из уравнений системы с коэффициентом один и отсутствующие в других уравнениях называются базисными неизвестными , а все другие - свободными .

Решение системы называется базисным , если в нем свободные переменные равны 0, и оно имеет вид:
X баз = (0, 0; b 1 , …, b m), f(X баз) = c 0

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

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

Понятие допустимого решения, области допустимых решений, оптимального решения задачи линейного программирования .
Определение 1 . Вектор X, удовлетворяющий системе ограничений ЗЛП, в том числе и условиям неотрицательности, если они имеются, называется допустимым решением ЗЛП.
Определение 2 . Совокупность всех допустимых решений образует область допустимых решений (ОДР) ЗЛП.
Определение 3 . Допустимое решение, для которого целевая функция достигает максимума (или минимума), называется оптимальным решением.

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x 1 + 3x 2 → max при ограничениях:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x 3 , x 4 , x 5 , x 6 , которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x 3 . Во 2-ом неравенстве смысла (≤) вводим базисную переменную x 4 . В третьем неравенстве вводим базисную переменную x 5 . В 4-м неравенстве - базисную переменную x 6 . Получим каноническую форму модели:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Пример №2 . Найти два опорных решения системы
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2

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

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

• если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
• если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
• если некоторая переменная x j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
  x 3 = x 3 + - x 3 - , где x 3 + , x 3 - ≥ 0 .

Пример 1 . Приведение к канонической форме задачи линейного программирования:

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x 1 = x 1 " - x 7 , где x 1 " ≥ 0, x 7 ≥ 0 .

Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 " ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Условие оптимальности базисного плана канонической задачи ЛП. Симплекс-метод и его сходимость.

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

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

Значение целевой функции при этом перемещении для задач на максимум не убывает.

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

Опорным решением называется базисное неотрицательное решение.

Алгоритм симплексного метода

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

2. Находим исходное опорное решение и проверяем его на оптимальность.
Для этого заполняем симплексную таблицу 1.
Все строки таблицы 1-го шагазаполняем по данным системы ограничений и целевой функции.

Возможны следующие случаи при решении задач на максимум:

1. Если все коэффициенты последней строки симплекс-таблицы Dj ³ 0, то найденное

решение оптимальное.

2 Если хотя бы один коэффициент Dj £ 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем , так как F(X) ® ¥ , т.е.целевая функция не ограничена в области допустимых решений.

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

4. Если отрицательных коэффициентов в последней строке несколько, то в столбец базисной переменной (БП) вводят ту переменную , которой соответствует наибольший по абсолютной величине отрицательный коэффициент.

5. Если хотя бы один коэффициент Dk < 0 ,то k - тый столбец принимаем за ведущий.

6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.

7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.

Заполняем симплексную таблицу 2:

· заполняем базисный столбец нулями и единицей

· переписываем ведущую строку, разделив ее на ведущий элемент

· если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы

· остальные коэффициенты находим по правилу “прямоугольника”

Получаем новое опорное решение, которое проверяем на оптимальность:

Если все коэффициенты последней строки Dj ³ 0, то найденное решение максимальное.

Если нет, то заполняем симплексную таблицу 8-го шага и так далее.

Если целевая функция F(X) требует нахождения минимального значения , то критерием оптимальности задачи является неположительность коэффициентов Dj при всех j = 1,2,...n.

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

Легко заметить, что проблемы со сходимостью симплекс-ме­тода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения от­ношения

будут достигнуты для нескольких строк таблицы Т (q) одновре­менно. Тогда на следующей итерации столбец b(β(q+1)) будет со­держать нулевые элементы.

Задачи МП

Общей ЗЛП называют <,=,>=}bi (i=1,n) (2) при условии xj>

Симметрической < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Канонической смешенной .

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Геометрическая интерпретация целевой функции и ограничения ЗЛП. Геометрическая формулировка ЗЛП.

Пусть дана задача f=c1x1+c2x2-max (1)

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

План задачи (х1,х2) – точка на плоскости. Каждое неравенство с-мы 2 предст. собой полуплоскость. Полуплоскость –выпуклое множество. Выпуклым наз-ся множество в которым точки отрезка соединяющие (х1 и х2) принадлежащие этому множеству то же принадлежат множеству. С-ма 2 представляет собой пересечение полуплоскостей. При пересечении могут получиться:

1)выпуклая многоугольная замкнутая область.

2) выпуклая открытая многоугольная область

3) единственная точка

4) пустое множество

5) луч и отрезок

Геометрическая интерпретация целевой функции: ф-ция 1 представляет собой семейство параллельных прямых, которые наз-ют линиями уровня(линиями постоянного значения целевой функции). Частные производные функции по х1 и х2 показывают скорость возрастания целевой функции вдоль координат осей. Вектор-градиент показывает направление найскорейшего возрастания целевой функции.Для задачи 1-3 вектор-градиент = (с1;с2) Выходит из точки (0,0) и направлен в точку с координатами (с1;с2). Вектор-градиент перпендикулярен линиям уровня. Пересечение полуплоскастей принято наз-ть областью допустимых рещений(ОДР) .

Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.

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

БП		СП -Xm+1 -Xm+2 -Xn
х1	b1o	b11 b12 b1n-m
х2	b2o	b21 b22 b2n-m
хm	bm	bm1 bm2 bmn-m
f	boo	bo1 bo2 bon-m

Алгоритм симплекс-метода.

1. привести модель задачи к канонической форме;

2. найти начальный опорный план;

3. записать задачу в симпл. таблицу;

5. перейти к новому опорному плану, к новой симп. таблице. Для того чтобы перейти к новому опорному плану достаточно заменить одну базисную переменную свободной. Переменную, включаемую в базис и соответствующей ей разрешающий столбец определяют по наибольшему по модулю отрицательному элементу f-строки. Переменную, исключающую из базиса и соответствующую ей разрешающую строку определяют по наименьшему симплексному отношению, т.е. отношению элементов единичного столбца к соответствующему элементу разрешающего столбца. Симплексное отношение – величина неотрицательная. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент, относительно которого выполняется симплексное преобразование по след. правилу: 1. элементы разрешающей строки делятся на разрешающий элемент; 2. элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; 3. остальные элементы таблицы перещитываются по правилу прямоугольника.:

bij bis bkj=(bkj*bis-bij*bks)/bi

Ая теорема двойственности.

если одна из двойственных задач имеет оптим план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограничена на множестве планов, то в двойственной задаче система ограничений несовместна.

Теорема о ранге матрицы ТЗ.

Ранг матрицы А трансп.задачи на единицу меньше числа уравнений: r(A)=m+n-1.

39. Алгоритм построения начального опорного плана ЗЛП.

Для нахождения начального опорного плана можно предложить следующий алгоритм:

1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1.

		-x1 ….. -xn
0=	a1o	a11 …. a1n
…..	…..	………………………..
0=	amo	am1 ….. amn
f=		-c1 …. -cn

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

40. Алгоритм построения оптимального опорного плана ЗЛП.

Начальный опорный план Хо исследуется на оптимальность.

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

Алгоритм метода Гомори.

1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2

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

(n-m,s=1)∑ {αkm+1}Xm+1≥{βk}

3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом

4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2.

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

Различные формы записи ЗЛП (общая, каноническая, симметрическая)

Задачи МП : определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т.д.

Общей ЗЛП называют задачу максимизации (минимизации) линейной функции f=Σcj*xj-max(min) (1) при линейных ограничениях ∑aij *xj{=<,=,>=}bi (i=1,n) (2) при условии xj>=0(j=1,n1), xj-произвольное (j=n1+1,n)(3) где cj,aij, bi-постоянные числа.

Симметрической формой записи ЗЛП наз-ся задача максимизации функции (1) при линейных ограничениях в неравенствах со знаком < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > либо = и неотрицательных переменных. Канонической формой записи ЗЛП наз-ся задача максимальной функции (1) при линейных ограничениях равенствах и неотрицательных переменных. Любая другая форма называется смешенной .

min f(x) = -max(-f(x))

Преобразование нерав-ва в уравнение и наоборот осущ-ся на основе Леммы: всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот. Всякому решению x1…xn,xn+1 уравнения 6 и неравенства 7 соответствует решение x1…xn неравенства 5.

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

: Задачи линейного программирования (ЗЛП)

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

2. Виды задач линейного программирования

3. Формы записи ЗЛП

4. Каноническая форма задач линейного программирования

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

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

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

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

Рисунок 1 - Экстремум целевой функции

Математическая модель ЗЛП записывается следующим образом:

max (или min) Z=z(X),(1)

ОДР может быть представлена системой линейных уравнений или неравенств.

Вектор Х=(х 1 , х 2 , .... x п) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции -- через Z*=z(X*).

Виды задач линейного программирования

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

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

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b 1 , b 2 , ..., b т). Известны также технологические коэффициенты a ij , которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции. Эффективность выпуска единицы j-и продукции характеризуется прибылью p j .

Требуется определить план выпуска продукции Х=(х 1 , х 2 , ..., x п), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

при ограничениях

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

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

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

1) максимум прибыли

2) минимум затрат на производство

3) максимум выпуска в стоимостном выражении (выручки от реализации продукции)

Пример. Предприятие может изготовлять четыре вида продукции 1, 2, 3 и 4. Сбыт любого ее объема обеспечен. Предприятие располагает в течение квартала трудовыми ресурсами в 100 человеко-смен, полуфабрикатами массой 260 кг, станочным оборудованием в 370 станко-смен. Нормы расхода ресурсов и прибыль от единицы каждого вида продукции представлены в табл.1.

Необходимо:

а) составить математическую модель задачи определения плана выпуска продукции, при котором достигается максимум прибыли;

б) решить задачу с требованием комплектации, чтобы количество единиц третьей продукции было в 3 раза больше количества единиц первой;

в) выяснить оптимальный ассортимент при дополнительных условиях: первого продукта выпускать не менее 25 единиц, третьего -- не более 30, а второго и четвертого -- в отношении 1:3.

Таблица 1

Исходные данные

Математическая модель задачи:

целевая функция:

max: Z=40x 1 +50x 2 +100x 3 +80x 4

при ограничениях:

а) на трудовые ресурсы:

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100;

на полуфабрикаты:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

на станочное оборудование:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

условие неотрицательности:

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

3x 1 =x 3 , т.е 3x 1 x 3 =0;

в) граничные условия и условие комплектации представим так: х 1 ?25,

х 3 ?30, 3*х 2 =х 4 .

Задача о размещении заказов или загрузке взаимозаменяемых групп оборудования . Речь идет о распределения заказов между m (i=1,…, m) предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказов. Требуется составить такой план размещения заказов, при котором задание было бы выполнено, а показатель эффективности достигал экстремального значения.

Сформулируем задачу математически. Пусть на т однородных группах оборудования нужно изготовить п видов продукции. План выпуска каждого вида продукции на определенный период задан набором х j (j=1,2, …п). Мощность каждого вида оборудования ограничена и равна b i . Известна технологическая матрица A=||a ij ||, где a ij --число единиц j-ой продукции, выпускаемой в единицу времени на i-м оборудовании. Матрица С - матрица затрат, где c ij --затраты, связанные с выпуском единицы j-й продукции на i-м оборудовании. Х -- вектор объема выпускаемой продукции.

Модель задачи примет следующий вид:

целевая функция -- минимизация расходов на реализацию всех заказов

при ограничениях:

а) по мощности оборудования

б) на выпуск продукции

в) условие неотрицательности

Данную задачу называют распределительной или задачей распределения.

Если по некоторым видам продукции допускается превышение плана, то ограничение (б) примет вид

В качестве целевой прибыли также можно принять:

а) максимум прибыли

б) минимум затрат станочного времени

Т.к. любая модель содержит упрощающие предпосылки, для корректного применения полученных результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее существенным упрощением в рассмотренных моделях является предположение о прямопропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат a ij . Очевидно, что это допущение далеко не всегда выполняется. Так объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно - в зависимости от изменения программы производства Х. К другим упрощающим предпосылкам относятся предположения о независимости цен j от объемов x j , что справедливо лишь для определенных пределов их изменения. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления усовершенствования модели.

Формы записи ЗЛП

Существует 3 формы записи ЗЛП:

1) в виде функций

max(или min)Z=,max(или min)Z=,

2) векторная форма

(скалярное произведение векторов)

при ограничениях

A 1 х 1 +A 2 х 2 +..+A n x n = B

Где векторы

С = (С 1, С 2 .. С n), Х = (Х 1, Х 2 .. Х n), и.

3) матричная форма

при ограничениях

где С = (с 1 , с 2 ,…с n),

Каноническая форма задач линейного программирования

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные x j налагаются условия неотрицательности, то она называется задачей линейного программирования в канонической форме или канонической задачей линейного программирования (КЗЛП).

при ограничениях

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

Правила приведения ЗЛП к каноническому виду:

1) если в ограничениях правая часть отрицательная, то следует умножить это ограничение на -1;

2) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

3) если некоторая переменная xk не имеет ограничений по знаку, то она заменяется в целевой функции и во всех ограничениях разностью между двумя новыми неотрицательными переменными: xk=x * k - xl, где l - сводный индекс, x * k>=, xl>=0.

Рассмотрим пример. Приведем к канонической форме:

Введем в каждое уравнение системы ограничений выравнивающие переменные х 4 , х 5 , х 6 . Система запишется в виде равенств, причем в первое и третье уравнение системы ограничений переменные х 4 , х 6 вводятся в левую часть со знаком «+», а во второе уравнение вводится х 5 со знаком «-».

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

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

Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

оптимизационный симплексный линейный программирование

Задача линейного программирования вида ax = b где a - матрица коэффициентов, b - вектор ограничений.
Пример :

В каждой задаче ЛП ищутся значения переменных при условии, чтобы:

• эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
• при этих значениях целевая функция обращалась бы в минимум или максимум.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

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

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

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, можно перейти к системе ограничений:

Эти дополнительные переменные y i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i -го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y 1 = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y <18. В этом случае y 1 приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из пункта 3.3.2, x = 12, y = 6, мы можем из системы ограничений (3.9) сделать вывод, что y 1 = y 2 = y 3 = 0, а y 4 = 12 – 6 = 6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т.д.
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о смеси. Система ограничений имеет вид:
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y 1 , y 2 , y 3 ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные y i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y 1 будет означать количество излишнего вещества А в смеси, y 2 –количество излишков вещества В в смеси, y 3 – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (– F). Посмотрите на рисунок: если в какой-то точке x = x 0 функция y = F (x ) достигает своего максимума, то функция y = –F (x ), симметричная ей относительно оси OX , в этой же точке x 0 достигнет минимума, причем F max = – (–F min) при x = x 0 .

Вывод. Для представления задачи ЛП в канонической форме необходимо:

• неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
• если целевая функция F →max (максимизируется), она заменяется на функцию –F → min (которая минимизируется).