Отыскание опорного и оптимального решения злп с использованием табличного алгоритма с заменой базисных переменных.

Алгоритм составления симплексных таблиц (СТ), рассмотрим на примере решения задачи отыскания max.

Пример 2.6

Линейная функция:

F=2x₁+3x₂→max

Система ограничений

x₁+3x₂≤18

2x₁+x₂≤16

x₂≤5

3x₁≤21

x₁, x₂≥0

 

1. Приведем эту систему к каноническому виду, введя дополнительные переменные х₃, х₄, х₅, х₆:

 

х₁+3х₂+х₃=18

2х₁+х₂+х ₄=16

х₂+х₅=5

3х₁+х₆=21

 

Целевую функцию представим в виде:

F-2x₁-3x₂=0;

 

2. Заполняем первую симплексную таблицу: в ней х₃, х₄, х₅, х₆ – основные переменные (базис). Последняя строка называется оценочной.

Таблица №1.

 

←разрешающая строка

 

 

↑

разрешающий столбец

 

3. Проверяем выполнение критерия функции на max – первый опорный план не оптимальный, так как в F коэффициенты при x₁ и x₂ < 0

 

4. Выбираем наибольший по модулю отрицательный коэффициент F, который определяет разрешающий столбец.(второй столбец)

 

5. Делим свободные члены на коэффициенты разрешающего столбца, определяем оценочные отношения. И выбираем строку в качестве разрешающей, где это отношение минимальное min {6,16,5,∞}=5. На пересечении разрешающего столбца и разрешающей строки находиться разрешающий элемент a₂₃ = 1.

Для построения таблицы №2 в качестве основной переменной мы выбираем х₂, так как она образует разрешающей столбец таблице 1.

Переход к новому плану осуществляется пересчетом симплексной таблице (СТ) методом Жордана Гаусса.

 

Таблица №2.

 

 

← разрешающая строка

 

↑

разрешающий столбец

 

Построение 2^ой таблицы:

1)Заменим переменные в базисе с х₅ на х_2.

2)Делим элементы разрешающей строки х₅ (табл.1) на разрешающий элемент, результаты занесем в строку х_2, но в таблицу №2.

3)В остальных клетках разрешающегося столбца (табл.1) записываем 0.

4)Остальные клетки заполняем по правилу прямоугольника:

	НЭ=СТЭ-(А´В)/РЭ

 

НЭ- новый элемент.

СТЭ- старый элемент.

РЭ- разрешающий элемент.

А,В- эл-ты старого плана, образующие прямоугольник со старым эл-том и разрешающим элементом.

СТЭ А

 

 

В РЭ

 

b₁=18-(3х5)/1=3

а₁₁=1-(3х0)/1=1

b₂=16-(1х5)/1=11 и т.д.

Критерии оптимальности опять не выполнен, так как F имеет коэффициент -2<0

- наибольший отрицательный по модулю коэффициент |-2| определяет разрешающий столбец x₁

- min (3;11/2;∞;7)=3. Следовательно, 1^ая строка разрешающая а₁₁ - разрешающий элемент.

 

Таблица №3

 

← разрешающая строка

 

 

↑

разрешающий столбец

В таблице 3 критерий оптимальности вновь не выполнен. Разрешающий столбец x₅, разрешающая строка x₄, разрешающий элемент 5.

1)х₁ вместо х_3.

2)В строке х₁ делим все на 1.

 

Таблица №4

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4	х5	х6
х1				-1/5	3/5
Х5				-2/5	1/5
х2				2/5	-1/5
х6				3/5	-9/5
F				4/5	3/5

 

Новая СТ№4 – критерий оптимальности выполнен – оптимальное базисное решение X(6,4,0,0,1,3)

F=24 =max

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

Прибыль принимает максимальное значение F_max=24 при реализации 6 единиц продукции P₁ (x₁=6) и 4 единиц продукции P₂(x₄=4). Дополнительные переменные x₃, x₄, x₅, x₆ показывают остатки ресурсов каждого вида. При оптимальном плане производства x₃=x₄=0, то есть остатки ресурсов S₃ и S₄ равны 0, а остатки ресурсов S₅ и S₆ равны соответственно 1 и 3 единицам.

Выполнить самостоятельно.

В соответствии с индивидуальным заданием №1 решить задачу максимизации с использованием симплексных таблиц. Вариант задания выбирается по номеру зачетной книжки:

-предпоследняя цифра - № столбца

-последняя цифра – № строки

Пример: Симплексным методом решить задачу максимизации.

F(x)=5x₁-x₂→max

2x₁-x₂+x₃≤3

3x₁+2x₂≤6

x₁≥0; x₂≥0

1. Переведем систему ограничений в канонический вид, введя выравнивающие (базисные) неизвестные – x₃ и x₄.

Задача принимает следующий вид:

2x₁-x₂+x₃=3

3x₁+2x₂=6

x₁=x₂=x₃=x₄=0

F-5x₁+x₂=0

2. Заполняем первую симплексную таблицу. В ней x₃, x₄ – основные переменные (базис).

Таблица 1.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
x3		2	-1			3/2
x5
F		-5

 

 

← разрешающая строка

 

 

↑

разрешающий столбец

 

3. Проверяем выполнение критерия на max – первый опорный план не оптимальный, т.к. в F коэффициент при х₁<0

4. Выбираем наибольший по модулю отрицательный коэффициент F, который определяет разрешающий столбец.

5. Делим свободные члены на коэффициенты разрешающего столбца (определяем оценочные отношения). Выбираем разрешающую строку, где это отношение минимально

 

Min (3, 2)= 3

2 2

Разрешающий элемент будет а₁₁=2

Для построения таблицы 2 в качестве основной переменной выбираем х₁, т.к. она образует разрешающий столбец таблицы 1.

 

Таблицы 2.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
х1	3/2		-1/2	1/2		-3
х4	3/2		7/2	-3/2		3/7
F	15/2		-3/2	5/2

 

 

← разрешающая строка

 

↑

разрешающий столбец

Построение таблицы №2.

1. Заменим переменные в базисе с х₃ на х₁.

2. Делим элементы разрешающей строки (табл.1) на разрешающий элемент, результаты занесем в строку х₁ в табл. №2.

3. В остальных клетках разрешающего столбца (табл. 1) записываем 0.

4. Остальные клетки заполняем по правилу прямоугольника

НЭ=СТЭ-(АхВ)/РЭ

 

СТЭ А

 

 

В РЭ

 

5. Критерий эффективности опять не выполнен, т.к. F имеет два коэффициента - 3 < 0

Построение таблицы №3

Таблицы 3.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
х1	12/7			2/7	1/7
х2	3/7			-1/7	2/7
F	57/7			13/7	3/7

 

Из таблицы 3 видно – критерий оптимальности выполнен.

Оптимальные базисные решения Х^*=(12, 3,0,0)

7 7

F=5x₁-x₂=5x 12 - 3 = 57

7 7 7

 

 

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ №1

	0,1,2	3,4,5,6	7,8,9
	f(x)=3x1-2x2; 2x1+x2≤2; x1+2x2≤2; x1,x2≥0;	f(x)=4x1+8x2; x1+x2≤3; x1+2x2≤2; x1,x2≥0;	f(x)=-4x1+8x2; 3x1+5x2≤15; x1-x3≤1; x1,x2≥0;
	f(x)=3x1-2x2; -x1+2x2≤2; 2x1-x2≤2; x1,x2≥0;	f(x)=-x1+6x2; 4x1+3x2≤12; -x1+x2≤1; x1,x2≥0;	f(x)=-x1+6x2; x1+x2≤3; -2x1+x2≤2; x1,x2≥0;
	f(x)=x1+6x2; 3x1+4x2≤12; -x1+x2≤2; x1,x2≥0;	f(x)=2x1+6x2; 3x1+4x2≤12; x1+2x2≤2; x1,x2≥0;	f(x)=8x1+12x2; 2x1+x2≤4; 2x1+5x2≤10; x1,x2≥0;
	f(x)=8x1+12x2; -3x1+2x2≤0; 4x1+3x2≤12; x1,x2≥0;	f(x)=3x1-2x2; 2x1+x2≤2; 2x1+3x2≤6; x1,x2≥0;	f(x)=6x1+4x2; x1+2x2≤2; -2x1+x2≤0; x1,x2≥0;
	f(x)=6x1+4x2; 3x1+2x2≤6; 3x1+x2≤3; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤1; 3x1+2x2≤6; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤2; 3x1+4x2≤12; x1,x2≥0;

 

Пример. Решить следующую задачу максимизации

F(x)=5x₁-x₂→max

2x₁-x₂+x₃≤3

3x₁+2x₂≤6

x₁≥0; x₂≥0

 

Запишем систему в каноническом виде

1) 2x₁-x₂+x₃=3

2) 3x₁+2x₂=6

3) x₁=0; x₂=0

 

Решение. В системе координат Х₁ОХ₂ построим ОДР.

Из первого уравнения:

При Х₁=0 X₂=-3 → (X₁,X₂)=(0,-3) прямая (1)

При Х₂=0 Х₁= 3 → (X₁,X₂)=(3, 0)

2 2

 

Из второго уравнения:

При Х₁=0 X₂=3 → (X₁,X₂)=(0,3) прямая (2)

При Х₂=0 Х₁=2 → (X₁,X₂)=(2, 0)

 

Из условия (3) (Х₁, Х₂)=(0,0) Х₁=0 – прямая (3)

Х₂=0 – прямая (4)

 

Для определения с какой стороны прямых ОДР все точки удовлетворяют неравенствам возьмем точку (1,1). Таким образом, ОДР лежит внутри АВСD.

Для определения точки выхода, строим прямую:

F(x)=5x₁-x₂=0

5x₁=x₂→ x₁=x₂=0 при x₁=1, x₂=5

Строим нулевую линию уровня целевой функции.

Строим нормальный вектор q (5.-1)

Передвигая линию уровня целевой функции параллельно себе, по вектору q, фиксируем ее крайнее положение (т.В), которая принадлежит прямым (1) и (2).

2x₁-x₂+x₃=3

3x₁+2x₂=6

 

x₁= 12 x₂= 3, т.е. Х^*=(12, 3)

7 7 7 7

F(Х^*)=5х 12 - 3 = 57

7 7 7

 

 

2.8Двойственные задачи линейного программирования (ДЗЛП).

Рассмотрим пример 2.6 и пример 2.5 и представим их в виде таблице

 

Задача 1 (исходная)	Задача 2 (двойственная)
F=2x1+3x2→max при ограничениях: x1+3x2≤18 2x1+x2≤16 x2≤5 3x1≤21 x1, x2≥0 Составить такой план выпуска продукции X=(x1, х2) при котором прибыль при реализации будет max. В общем виде задача запишется: n F=∑Cjxj→max, j=1 при ограничениях: n j=1,2…m ∑aijхi≤ bi i=1,2…n j=1	Z=18 y1+16y2+5y3+21y4→min при ограничениях: y1+2y2+3y4≥2 3y1+y2+y3≥3 y1, y2, y3, y4≥0 Найти такой набор цен ресурсов Y=(y1,y2,y3,y4), при котором общие затраты на ресурсы будут минимальны. В общем виде задачу запишем: m Z=∑ biyi →min, i=1 при ограничениях: m j=1,2…m ∑ aijyi≤ cj i=1,2…n i=1

 

Из таблице видно, что задачи 1 и 2 обладают следующими свойствами:

1) В задаче 1 ищут max, во 2 ищут min.

2) Коэффициенты целевой ф-ции 1-ой задачи являются свободными членами системы ограничения 2-ой задачи.

3) Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤, а в задаче минимизации вида ≥.

4) Матрицы коэффициентов в системе ограничения обеих задач являются транспонированными друг другу.

Для 1 3 18

задачи 1 A₁= 2 1 16

0 1 5

3 0 21

2 3 F

 

 

Для

задачи 2 A’₁= 1 2 0 3 2

3 1 1 0 21

18 16 5 21 Z

 

 

 

 

5) Число неравенств в системе ограничений 1-ой задачи совпадает с числом переменных 2-ой задачи.

6) условие не отрицательности переменных есть в обеих задачах.

Две задачи, обладающие указанными свойствами, называются симметричными взаимно – двойственными задачами.

2.9Алгоритм составления двойственных ЗЛП:

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

1) Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут max целевой функции, то все неравенства системы ограничений привести к виду ≤, а если ищут min – к виду ≥. Для этого неравенства, в которых это требование не выполняется, умножить на (-1).

2) Составить расширенную матрицу системы A₁.

₃₎ Найти матрицу A₁, транспонированную к матрице A_1.

4) Сформулировать двойственную ЗЛП

Этот алгоритм можно проиллюстрировать следующим примером:

Составить задачу двойственную следующей задаче:

F=14x₁+10x₂+14x₃+11x₄→max

Система ограничений:

4х₁+2х₂+2х₃+3х₄≤35

х₁+х₂+2х₃+3х₄≤30

3х₁+х₂+2х₃+х₄≥40*

х₁≥0

х₂≥0

х₃≥0

х₄≥0

 

Решение:

Алгоритм	Конкретные ситуации данного алгoритма
1.Все неравенства системы ограничений привести к виду ≤;   2.Составить расширенную матрицу системы А1, в которую включить: - матрицу коэффициентов переменных системы ограничений. - столбец свободных членов. - строку коэффициентов при переменных линейной функции.   3.Найти матрицу A'1 транспонированную к матрице А1.   4.Сформулировать двойственную задачу на основании полученной матрицы A'1	Приведем третье неравенство к виду: -3х1-х2-2х3-х4≤-40     4 2 2 3 35 А1= 1 1 2 3 30 -3 -1 -2 -1 -40 14 10 14 11 F   4 1 -3 14 2 1 -1 10 A'1 = 2 2 -2 14 3 3 -1 11 35 30 -40 Z   Z=35y1+30y2-40y3→min 4y1+y2-3y3≥14 2y1+y2-y3≥10 2y1+2y2-2y3≥14 3y1+3y2-y3≥11 y1≥0; y2≥0; y3≥0

Выполнить самостоятельно:

1. Составить ДЗЛП следующей задачи

F=-x₁+2x₂→max

При ограничении: 2x₁-x₂≥1

-x₁+4x₂≤24

x₁ -x₂≤3

x₁ +x₂≥5

2. Составить ДЗЛП, используя исходные данные таблицы №1. Вариант задания выбирается по номеру зачетной книжки

–предпоследняя цифра - № строки

–последняя цифра - № столбца.

3.Теорема двойственности