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

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

φi (х1, х2, …, хп) <= bi, i=1,2,…,m (1) и обращающие в максимум (минимум) целевую функцию Z = f ((х1, х2, …, хп) à max (2)

Понятие экономико-математической модели

Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта. Эта модель выражает закономерности… Процедура экономико-математ моделирования заменяет дорогостоящие и трудоемкие…

Примеры построения ЭММ экономических задач линейного программирования

Задача об использовании ресурсов (задача планирования производства).

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет макс. ЭММ задачи: Х1 и Х2 – число единиц продукции П1 и П2 соответственно.

Задача о раскрое материалов.

Необходимо найти план раскроя, обеспечивающий макс число комплектов. Составим ЭММ задачи: Обозначим Хi – число единиц материала раскраиваемых i-ым способом, и Х – число изготавливаемых комплектов изделий.…

Система m линейных уравнений с n переменными

  а11*Х1 + а12*Х2 + …+ а1j*Xj + …+ а1n*Xn = В1 а21*Х1 + а22*Х2 + …+ а2j*Xj + … + а2n*Xn = В2

Геометрический смысл решений неравенств, уравнений и их систем

Пример: 3х1 – 4х2 + 12 <= 0

А11х1 + а12х2 +… + a1nxn = b1

при n=3 является плоскостью, а при n>3 – ее обобщением в n – мерном пространстве – гиперплоскостью, можно обобщить вышесформулированную теорему на случай трех и более переменных.

 

Теорема 2. Множество решений совместной системы m линейных неравенств с двумя переменными

а11*Х1 + а12*Х2 <= В1

а21*Х1 + а22*Х2 <= В2

………………………….

аm1*Х1 + аm2*Х2 <= Вm

Является выпуклым многоугольником (или выпуклой многоугольной областью).

  Пример: Построить множество решений системы неравенств -5х1 + 4х2 <= 20 (I)

Свойства задач ЛП

Будем рассматривать каноническую задачу, в которой система ограничений – система уравнений. Теорема 4. Множество всех допустимых решений системы ограничений ЗЛП (задачи… Теорема 5. Если задача ЛП имеет оптимальное решение, то линейная функция принимает макс (мин) значение в одной из…

Геометрический метод решения задач ЛП

Рассмотрим задачу в стандартной форме (1.4) – (1.6) Найти такой план Х = (Х1, Х2, …, Хn) выпуска продукции, удовлетворяющий…    

Симплексный метод

Число перебираемых ДБР можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь, чтобы… Предположим, точка А – исходное ДБР (допустимое базисное решение). Из чертежа видно, что от А выгодно перейти к В, а…

Нахождение оптимума линейной функции

Решим симплексным методом задачу: F=2x1 + 3х2 à maxпри ограничениях: х1 + 3х2 <= 18

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

Если выбранные переменные имеют те же знаки, что и соответствующие им свободные члены, то полученное БР будет ДБР. Если получено не ДБР, то М-метод. Будет рассмотрен дальше.

1 шаг. Осн – х3, х4, х5, х6.

Неосн – х1, х2.

Х3 = 18 – х1 – 3х2

Х4 = 16 – 2х1 – х2 (1)

Х5 = 5 – х2

Х6 = 21– 3х1

Неосновные = 0àХ1 =(0; 0; 18; 16; 5; 21) соответствует вершине О(0; 0).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2. При решении Х1 значение функции F(X1) = 0. Функцию можно увеличить за счет увеличения любой из неосновных переменных, входящих в уравнение для функции с положительным коэффициентом. Это можно осуществить перейдя к такому новому ДБР, в котором эта переменная будет основной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). Одна из переменных, при этом из основных – в неосновные. Геометрически – к соседней вершине. В данном примере и х1 и х2 м можно. Выберем х2 – больший коэффициент.

Система (1) накладывает ограничения на рост переменной х2. Т.к. необходимо сохранять допустимость решений, т.е. все переменные неотрицательны, то должны выполняться неравенства (х1 при этом = 0 как неосновная):

 

Х3 = 18 – 3х2 >= 0 Х4 = 16 – х2 >= 0 Х5 = 5 – х2 >= 0 Х6 = 21 >= 0

откуда

Х2 <= 18/3 Х2 <= 18/1 Х2 <= 5/1

 

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

Граница - ¥:

§ Последнее уравнение системы не ограничивает рост переменной х2, т.к. эта переменная не входит в него (входит с 0 коэффициентом).

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

§ Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член = 0, а переводимая переменная имеет знак +.

При свободном члене = 0, а переводимая переменная имеет знак – уравнение ограничивает рост переменной 0.

В данном примере наибольшее возможное значение для х2 = min{18/3; 16/1; 5/1; ¥} = 5. При х2 = 5 переменная х5 обращается в 0 и переходит в неосновные.

Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна) называется разрешающим. В данном случае – 3. выделяется рамкой в системе ограничений.

 

2 шаг. Осн – х2, х3, х4, х6.

Неосн – х1, х5.

Х2 = 5 – х5

Х3 = 18 – х1 – 3(5 – х5)

Х4 = 16 – 2х1 – (5 – х5) (2)

Х6 = 21– 3х1

или

Х2 = 5 – х5

Х3 = 3 – х1 + 3 х5

Х4 = 11 – 2х1 + х5

Х6 = 21– 3х1

 

Неосновные = 0àХ2 =(0; 5; 3; 11; 0; 21) соответствует вершине А(0; 5).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 2х1+ 3(5 – х5) = 15+ 2х1 – 3х5. При решении Х2 значение функции F(X2) = 15. Изменение значения линейной функции можно определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в целевой функции (изменение F = 5 * 3 =15.

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

Система (2) определяет наибольшее возможное значение для х1 = min{¥; 3/1; 11/2; 21/3} = 3. второе уравнение – разрешающее, переменная х3 обращается в 0 и переходит в неосновные, при этом приращение целевой функции = 3*2 = 6.

 

3 шаг. Осн – х1, х2, х4, х6.

Неосн – х3, х5.

Выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения. После преобразования получаем:

Х1 = 3 – х3 + 3 х5

Х2 = 5 – х5

Х4 = 5 + 2х3 - 5х5 (3)

Х6 = 12 + 3х3 – 9х5

 

Неосновные = 0àХ3 =(3; 5; 0; 5; 0; 12) соответствует вершине В(3; 5).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 2(3 – х3 +3х5) + 3(5 – х5) = 21- 2х3 + 3х5. При решении Х3 значение функции F(X3) = 21.

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

При определении наибольшего возможного значения для х5, которую переводим в основные, обратить внимание, что первое уравнение системы (3) не дает ограничения на рост х5, т.к. свободный член и коэффициент при х5 имеют одинаковые знаки. Система (3) определяет наибольшее возможное значение для х5 = min{¥; 5; 1; 12/9} = 1. Третье уравнение – разрешающее, переменная х4 обращается в 0 и переходит в неосновные, при этом приращение целевой функции = 1*3 = 3.

 

4 шаг. Осн – х1, х2, х5, х6.

Неосн – х3, х4.

Выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения. После преобразования получаем:

Х1 = 6 + 1/5х3 – 3/5х4

Х2 = 4 – 2/5х3 + 1/5х4

Х5 = 1 + 2/5х3 – 1/5х4 (3)

Х6 = 3 – 3/5х3 + 9/5х4

 

Неосновные = 0àХ4 =(6; 4; 0; 0; 1; 3) соответствует вершине С(6; 4).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 24 – 4/5х3 – 3/5х4. При решении Х4 значение функции F(X4) = 24.

Значение F4 является оптим, т.к. нет положительных коэффициентов при неосновных переменных.

Вспоминая экономический смысл всех переменных, можно сделать следующие выводы:

§ Прибыль предприятия примет макс значение 24 руб. при реализации 6 ед. продукции первого вида (х1 = 6) и 4 ед. продукции второго вида (х2 = 4).

§ Дополнительные переменные х3, х4, х5 и х6 показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптим плане производства х3 = х4 = 0, т.е. остатки первого и второго ресурсов равны 0, а остатки третьего и четвертого ресурсов равны соответственно 1 и 3 единицам.

 

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

При отыскании мин лин функции Z возможны два пути:

1) отыскать макс лин функции F, полагая, что F = - Z и учитывая, что Zmin = - Fmax;

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

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

Замечание. На каждом шаге симплексного метода какая-либо неосновная переменная переводится в основные, при этом каждое уравнение системы ограничении определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение. Могут встречаться различные случаи оценки роста неосновной переменной, которые зависят от знаков и значений свободного члена и коэффициентов при переводимой переменной. Введем обозначения:

Xi – переводимая неосновная переменная;

Bj– свободный член;

Aij – коэффициент при Xi;

Сформулируем все возможные случаи оценки роста Xi в уравнении Xj = Bj + … + AijXi + … :

1) Хi = ½Bj/Aij½, если Bj и Aij разного знака и Aij не = 0, Bj не = 0.

2) Хi = ¥, если Bj и Aij одного знака и Aij не = 0, Bj не = 0.

3) Хi = 0, если Bj = 0 и Aij > 0.

4) Хi = ¥, если Bj = 0 и Aij < 0.

5) Хi = ¥, если Aij = 0.

Особые случаи симплексного метода

Решим симплексным методом задачу: F=3x1 + 3х2 à maxпри ограничениях: х1 + х2 <= 8

Симплексные таблицы

I. После введения добавочных переменных систему уравнений и лин функцию записывают в виде, который называется расширенной системой: (Слайд 2) а11*Х1 + а12*Х2 + … + а1n*Xn + Xn+1 = В1 а21*Х1 + а22*Х2 + … + а2n*Xn + Xn +2 = В2 …………………………………………………………….