3. Решение задачи симплексным методом с искусственным базисом

78 вариант

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

В неравенства с ограничениями больше или равно вводится искусственная переменная, которая обозначается “у” с коэффициентом 1.

В целевую функцию при решении задач на минимум “у” вводится с оценкой +М.

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

Формальным признаком оптимальности является отсутствие в целевой функции положительных коэффициентов при условии минимума.

5Х₁ + 3Х₂ + Х₃ → min

2Х₁ – Х₂ + 3Х₃ ≥ 99

Х₁ + Х₂ ≥ 58

3Х₁ + 2Х₂ - 4Х₃ ≥ 20

4Х₁ – 2Х₂ + Х₃ ≥ 78

Приведение задачи к канонической форме:

2Х₁ – Х₂ + 3Х₃ – S₁ + Y₁ = 99

Х₁ + Х₂ – S₂ + Y₂ = 58

3Х₁ + 2Х₂ - 4Х₃ – S₃ + Y₃ = 20

4Х₁ – 2Х₂ + Х₃ – S₄ + Y₄ = 78

Z = 5Х₁ + 3Х₂ + Х₃ – S₁ – S₂ – S₃ – S₄ + MY₁ + MY₂ + MY₃ + MY₄ → min

Таблица 1 – Первый базисный план

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			5	3	1	0	0	0	0
М	У1	99	2	-1	3	-1	0	0	0
М	У2	58	1	1	0	0	-1	0	0
М	У3	20	3	2	-4	0	0	-1	0
М	У4	78	4	-2	1	0	0	0	-1
Индексная строка	Z	0	-5	-3	-1	0	0	0	0
			10М	0	0	-М	-М	-М	-М

↑

Находим главную строку: 99 /2 = 49,5; 58/1 = 58; 20/3 = 6,67; 78/4 = 19,5; отсюда следует главный элемент = 3.

Таблица 2 - Улучшенный базисный план

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			5	3	1	0	0	0	0
М	У1	85,67	0	-2,33	5,67	-1	0	0	0
М	У2	51,33	0	0,33	1,33	0	-1	0,33	0
5	Х1	6,67	1	0,67	-1,33	0	0	-0,33	0
М	У4	51,33	0	-4,67	6,33	0	0	1,33	-1
Индексная строка	Z	33,33	0	0,33	-7,67	0	0	-1,67	0
			5	-6,67М+ 3,35	13,33М-6,65	-М	-М	1,66М- 6,65	-М

↑

Находим главную строку: 85,67 /5,67 = 15,11; 51,33/1,33 = 38,59; 6,67/(-1,33) = (-5,01); 51,33/6,33 = 8,11; отсюда следует главный элемент = 6,33.

Таблица 3 - Улучшенный базисный план

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			5	3	1	0	0	0	0
М	У1	39,69	0	1,85	0	-1	0	-1,19	0,90
М	У2	40,54	0	1,31	0	0	-1	0,05	0,21
5	Х1	17,45	1	-0,31	0	0	0	-0,05	-0,21
7,67	Х3	8,11	0	-0,74	1	0	0	0,21	-0,16
Индексная строка	Z	95,53	0	-5,33	0	0	0	-0,06	-1,21
			5	3,16М- 7,22	7,67	-М	-М	-1,14М+ 1,36	1,11М- 1,08

↑

Находим главную строку: 39,69 /1,85 = 21,45; 40,54/1,31 = 30,95; 17,45/(-1,31) = (-56,29); 8,11/(-0,74) = (-10,96); отсюда следует главный элемент = 1,85.

Таблица 4 - Улучшенный базисный план

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			5	3	1	0	0	0	0
5,33	Х2	21,45	0	1	0	-0,54	0	-0,64	0,49
М	У2	12,44	0	0	0	0,71	-1	0,89	-0,43
5	Х1	24,10	1	0	0	-0,17	0	-0,25	-0,06
7,67	Х3	23,99	0	0	1	-0,40	0	-0,27	0,20
Индексная строка	Z	209,88	0	0	0	-2,88	0	-3,49	1,38
			5	5,33	7,67	0,71М- 6,8	-М	0,89М- 6,73	-0,43М+ 3,81

↑

Находим главную строку: 21,45 /(-0,64) = (-33,52); 12,44/0,89 = 13,98; 24,10/(-0,25) = (-96,4); 23,99/(-0,27) = (-88,85); отсюда следует главный элемент = 0,89.

Таблица 5 - Улучшенный базисный план

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			5	3	1	0	0	0	0
5,33	Х2	30,40	0	1	0	-0,03	-0,72	0	0,18
3,49	S2	13,98	0	0	0	0,80	-1,12	1	-0,48
5	Х1	27,59	1	0	0	0,03	-0,28	0	-0,18
7,67	Х3	27,76	0	0	1	-0,18	-0,30	0	0,07
Индексная строка	Z	258,66	0	0	0	-0,10	-3,92	0	-0,31

Ответ: Полученный базисный план оптимальный.

4.Составить двойственную задачу по отношению к заданной прямой Одновременно с решением прямой задачи линейного программирования решается двойственная задача. Искомой величиной двойственной задачи является двойственная оценка.

Двойственная задача обеспечивает расчет двойственных оценок.

Составить двойственную задачу по отношению к заданной прямой:

100Х₁ + 250Х₂ + 150Х₃ → maх

Х₁ + Х₂ + Х₃ ≤ 240

210Х₁ + 104Х₂ + 478Х₃ ≤ 140

280Х₁ - 190Х₂ ≤ 0

Х₁ + Х₃ ≤ 177

Матрица двойственной задачи строится путем транспонирования или замещения матрицы прямой задачи.

Алгоритм транспортирования:

1. неизвестными величинами в двойственной задаче являются У_m. Если в прямой задаче было m ограничений по ресурсам, то в двойственной задаче будет m количества неизвестных величин

2. столбец матрицы прямой задачи становится строкой двойственной задачи

3. оценки переменных функции цели становятся свободными членами, свободные члены становятся коэффициентами функции цели

4. тип ограничения меняется на обратный

5. если прямая задача решается на mах функции, то двойственная задача будет на min

Х₁ + Х₂ + Х₃ ≤ 240

210Х₁ + 104Х₂ + 478Х₃ ≤ 140

280Х₁ - 190Х₂ ≤ 0

Х₁ + Х₃ ≤ 177

1) У₁ + 210У₂ +280У₃ + У₄ ≥ 100

2) У₁ + 104У₂ -190У₃ + 0У₄ ≥ 250

3) У₁ + 478У₂ +0У₃ + У₄ ≥ 150

4) У₁ + 0У₂ + 0У₃ + 0У₄ ≥ 0

5) 0У₁ + У₂ + 0У₃ + 0У₄ ≥ 0

6) 0У₁ +0У₂ +У₃+ 0У₄ ≥ 0

7) 0У₁ +0У₂ +0У₃ + У₄ ≥ 0

1) У₁ + 210У₂ +280У₃ + У₄ ≥ 100

2) У₁ + 104У₂ -190У₃ ≥ 250

3) У₁ + 478У₂ + У₄ ≥ 150

4) У₁ ≥ 0

5) У₂ ≥ 0

6) У₃ ≥ 0

7) У₄ ≥ 0

240У₁ + 140У₂ + 0У₃ +177У₄ → min

240У₁ + 140У₂ +177У₄ → min