Стандартное и каноническое представление задачи линейного программирования. Симплекс метод

ИсследованиеОпераций – теория принятия оптимальных решений: создаёт мат модель изучаемой системы (процесса) и выбирает оптимальное решение. Если в мат модели все функции линейные, то получаем ЗЛП.

Общая постановка задачи: задана целевая функция: F=c₁x₁+c₂x₂+…+c_nx_n, нужно найти при каком наборе переменных х₁, х₂,…, х_n, она – к max (min). Переменными x_j {j = 1..n} можем управлять => управляемые параметры. Параметрами b_i {i = 1..m} управлять не можем => система ограничений:

а₁₁х₁ + а₁₂х₂ + … а_1nx_n ≤ = ≥ b₁

а₂₁х₁ + а₂₂х₂ + … а_2nx_n ≤ = ≥ b₂

……..

а_m1х₁ + а_m2х₂ + … а_mnx_n ≤ = ≥ b_m

Для построения решения ЗЛП нужно приводить к стандартному виду:

1) целевая функция подлежит минимизации F→min 2) все ограничения записаны в виде равенств 3) правые части неотрицательны b_j ≥ 0 4) значение всех переменных не отрицательны x_j ≥ 0

Неравенства могут быть превращены в равенства путём присоединения искусственных переменных x_n+I – избыточных (если ≥, то – x_n+i) или остаточных (если ≤, то + x_n+i) а₁₁х₁ + а₁₂х₂ + … а_1nx_n + х_n+1 = b₁ Увеличивается число переменных задачи. Канонич.вид: станд вид + 5) в кажд. ур-ии есть базисная переменная, кот. присутсв. только в этом ур-ии с коэф. +1, в др. ур-х её нет. Если занулить свободные переменные, то базисные переменные дают допустимое решение. Пример:

общий вид: f = 2x₁ – 4x₂ + 5x₃ → max

4x₁ – 2x₂ – x₃ ≤ 5

– 3x₁ + x₂ + 8x₃ ≥ – 3

x₁, x₂, x₃ ≥ 0

переводим в стандартный: g = – f = –2x₁ + 4x₂ – 5x₃ + 0x₄ + 0x₅ → min

4x₁ – 2x₂ – x₃ + x₄ + 0= 5

3x₁ – x₂ – 8x₃ + 0 + x₅ = 3

x₁, x₂, x₃, x₄, x₅≥ 0

в данном случае сразу получили и канонич вид: x₄, x₅ – базисные переменные, x₁, x₂, x₃ – свободные переменные. Начальное допустимое решение на данном шаге {x₁ = 0, x₂ = 0, x₃ = 0, x₄ = 5, x₅ = 3}, g(0, 0, 0, 5, 3) = 0

Симплекс метод: вершины перебир-ся не произвольно, а так, что кажд. следующ. вершина улучшает знач-е целевой ф-ии. Стандартный вид: 1) все огр-я записны в виде рав=в; 2) правые части рав-в >=0; 3) переменные >=0; 4) F к min. Канонич.вид: 5) в кажд. ур-ии есть переменная, кот. присутсв. только в этом ур-ии с коэф. +1, в др. ур-х её нет. Одноэтапный СМ: для канонич вида. 1) Строим таблицу, 2) выбираем min эл-т и з F – ведущ столбец. 3) выбираем ведущ. строку с пом-ю сравнения отношений правых частей рав-в к эл-м ведущ столбца, из >0 выбираем min, получаем ведущ строку. 4) Эл-ты столбика кроме ведущего превращаем в 0. Далее с (1) пока все коэф-ты F не станут >=0. Двухэтапн. СМ для неканонич. вида: 1) приводим ЗЛП к канонич виду, т.е. решаем вспомогат задачу СМ. F’=(b1+b2+…+bm)+(a11+a21+…+am1)x1+(a12+a22+a32+…+am2)x2…+(a1n+a2n+…+amn)xn. 2) Решение получ задачи СМ.

Пример

Решить симплекс-методом

Найти

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

Решение.

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

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

Составим целевую функцию вспомогательной задачи

Построим симплекс-таблицу

| x1 x2 x3 x4 |своб

---------------------------------

| 1 1 -3 1 |7

| 1 3 1 0 |15

---------------------------------

F | -1 1 3 0 |0

F1 | -2 -4 2 -1 |-22

Ведущий столбец – 2 (т.к. минимальный отрицательный -4)

Ведущая строка – 2 (т.к 15/3 меньше, чем 7/1)

Ведущий элемент равен 3.

Проведем шаг симплекс-метода. Получим таблицу

| x1 x2 x3 x4 |своб

---------------------------------

| 2/3 0 -10/3 1 |2

х2 | 1/3 1 1/3 0 |5

---------------------------------

F |-4/3 0 8/3 0 |-5

F1 |-2/3 0 10/3 -1 |-2

Ведущий столбец – 4 (т.к. минимальный отрицательный -1)

Ведущая строка – 1

Ведущий элемент равен 1.

Проведем шаг симплекс-метода. Получим таблицу

| x1 x2 x3 x4 |своб

---------------------------------

х4 | 2/3 0 -10/3 1 |2

х2 | 1/3 1 1/3 0 |5

---------------------------------

F |-4/3 0 8/3 0 |-5

F1 | 0 0 0 0 |0

В строке вспомогательной целевой функции получены нули, значит, приведение к каноническому виду завершено. Выпишем начальное допустимое базисное решение: Х = (0, 5, 0, 2), F=5

Отбросим вспомогательную целевую функцию, получим таблицу

| x1 x2 x3 x4 |своб

---------------------------------

х4 | 2/3 0 -10/3 1 |2

х2 | 1/3 1 1/3 0 |5

---------------------------------

F |-4/3 0 8/3 0 |-5

Продолжим решение одноэтапным симплекс-методом, получим ответ

hmax = 7 при Х = (13, 0, 2)

19,

Транспортаня задача

Это задача ЗЛП имеющая структуру. Пусть имеется М поставщиков и п потребителей. Известны возможности поставщиков оформелнные в виде матрицы.

-предложение;

Известна стоимость перевозки еденицы товара от каждого поставщика к каждому потребителю

-стоимость матрицы

Товар у всех поставщиков одинаковый, а потому каждому потребителю товар может быть доставлен от любого поставщика. Требуется составить план перевозок(кому от кого и сколько везем) требуется чтобы возможности поставщиков были использ. требов потреб. Были удовл.

Составим матем модель задачи:

Х=-матрица перевозок план перевозок

F=c11x11+c12x12+..+c1nx1n+c21x21+c22x22+..+c2n+x2n+m+cm1xm1+cm2xm2+..+cmnxmn->min

x11+x12+..+x1n=a1

x21+x22+..+x2n=a2 определяет ……………………………….. возможности

Xm1+xm2+..+xmn=am использования поставщиков

X11+x21+..+xm1=b1

X12+x22+…+xm2=b2

………………………………….

X1n+x2n+…+xmn=bn

Xij>=0

Мат модель транспортной задачи

Как любая ЗЛП –транспортной задачи разрешается решение симплекс методом. Т.к. задача поставл в стандартной форме, то она треб решения двухэтапн. Симпл. Методом, но в виду большого кол-ва переменных(m*n имеется и при приведении к кононич форме введем еще l+n перем.

Реш транспортной задачи симплекс методом не рационально, т.о. разработали спец метод – метод потенциалов.

1, составить какой нить план перевозок

2, оценка плана на оптимальность

3, перераспределение перевозок

m=3 (30 40 60)

n=4 (10 50 30 40)

C= 1. Составление нач плана

До сост нач плана проверить задачу на сбалансированность. Задача называется сбалансированной(закрытой) если суммарный спрос равен сумаррному предложению

∑аi=∑bj

∑аi<∑bj То вводится (m+1) фиктивный поставщик предложение которого равно ∑bi-∑аj к стоимости перевозок от этого поставщика любому потребителю =0.

∑аi>∑bj то вводится (n+1) фиктивный потребитель спрос которого раверн ∑аi-∑bj и перевозки которого =0.

∑аi=30+40+60=130

∑bj=10+50+30+40=130 => задача сбалансированна

Методы составления начального плана

1, метод северо западного угла. Матрицу перевозок организуем в виде таблицы

			-	-
	-			-
	-	-

В таблице перевозок выбираем С-3 Клетка и в нее осуществляется максимально возможная поставка. *Метод С-З угла не учитывается стоимость перевозок и дает начальный план далекий от оптимального.

F=20*2+20*3+30*4+10*1+20*1+40*4=390

2, метод минимальной стоимости. В клетку с мин стоимостью доставки осуществл максимальная доставка

	10(2)	-(3)	-(4)	20(2)
	-(2)	-(4)	30(1)	10(1)
	-(3)	50(1)	-(1)	10(4)

В скобках количетво доставок

F=10*2+20*2+30*1+10*1+50*1+10*4=190

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