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

Решение задач  линейного программирования. 
 
Переход к КЗЛП. 
F(X) = 13x₁ + 10x₂ + 11x₃ → min при ограничениях: 
3x₂ + 3x₃≥2 
3x₁ + 2x₃≥2 
Для приведения ЗЛП к канонической форме необходимо: 
1. Поменять знак у целевой функции. 
Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). 
В 1-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.  
0x₁ + 3x₂ + 3x₃-1x₄ + 0x₅ = 2 
3x₁ + 0x₂ + 2x₃ + 0x₄-1x₅ = 2 
F(X) = - 13x₁ - 10x₂ - 11x₃ 
Переход к СЗЛП. 
Расширенная матрица системы ограничений-равенств данной задачи:

0 3 3 -1 0 2 3 0 2 0 -1 2

 
Приведем систему к единичной  матрице методом жордановских преобразований. 
1. В качестве базовой переменной выбираем x₂. 
Разрешающий элемент РЭ=3. 
Строка, соответствующая переменной x₁, получена в результате деления всех элементов строки x₁ на разрешающий элемент РЭ=3 
На месте разрешающего элемента получаем 1. 
В остальных клетках столбца x₁ записываем нули. 
Все остальные элементы определяются по правилу прямоугольника. 
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. 
НЭ = СЭ - (А*В)/РЭ 
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. 
Представим расчет каждого элемента в виде таблицы:

0 : 3	3 : 3	3 : 3	-1 : 3	0 : 3	2 : 3
3-(0 • 0):3	0-(3 • 0):3	2-(3 • 0):3	0-(-1 • 0):3	-1-(0 • 0):3	2-(2 • 0):3

 
Получаем новую матрицу:

0	1	1	-1/3	0	2/3
3	0	2	0	-1	2

 
2. В качестве базовой переменной  выбираем x₁. 
Разрешающий элемент РЭ=3. 
Строка, соответствующая переменной x₂, получена в результате деления всех элементов строки x₂ на разрешающий элемент РЭ=3 
На месте разрешающего элемента получаем 1. 
В остальных клетках столбца x₂ записываем нули. 
Все остальные элементы определяются по правилу прямоугольника. 
Представим расчет каждого элемента в виде таблицы:

0-(3 • 0):3	1-(0 • 0):3	1-(2 • 0):3	-1/3-(0 • 0):3	0-(-1 • 0):3	2/3-(2 • 0):3
3 : 3	0 : 3	2 : 3	0 : 3	-1 : 3	2 : 3

 
Получаем новую матрицу:

0	1	1	-1/3	0	2/3
1	0	2/3	0	-1/3	2/3

 
Поскольку в системе имеется единичная  матрица, то в качестве базисных переменных принимаем X = (2,1). 
Соответствующие уравнения имеют вид: 
x₂ + x₃ - ¹/₃x₄ = ²/₃ 
x₁ + ²/₃x₃ - ¹/₃x₅ = ²/₃ 
Выразим базисные переменные через остальные: 
x₂ = - x₃ + ¹/₃x₄+²/₃ 
x₁ = - ²/₃x₃ + ¹/₃x₅+²/₃ 
Подставим их в целевую функцию: 
F(X) = - 13(- ²/₃x₃ + ¹/₃x₅+²/₃) - 10(- x₃ + ¹/₃x₄+²/₃) - 11x₃ 
или 
F(X) = 7²/₃x₃ - 3¹/₃x₄ - 4¹/₃x₅-15¹/₃ → max 
Система неравенств: 
- x₃ + ¹/₃x₄+²/₃ ≥ 0 
- ²/₃x₃ + ¹/₃x₅+²/₃ ≥ 0 
Приводим систему неравенств к следующему виду: 
x₃ - ¹/₃x₄ ≤ ²/₃ 
²/₃x₃ - ¹/₃x₅ ≤ ²/₃ 
F(X) = 7²/₃x₃ - 3¹/₃x₄ - 4¹/₃x₅-15¹/₃ → max 
Упростим систему. 
x₁ - ¹/₃x₂ ≤ ²/₃ 
²/₃x₁ - ¹/₃x₃ ≤ ²/₃ 
F(X) = 7²/₃x₁ - 3¹/₃x₂ - 4¹/₃x₃-15¹/₃ → max

 

 

 

 

 

 

 

Транспортная  задача. 
 
Математическая модель транспортной задачи: 
F = ∑∑c_ijx_ij, (1) 
при условиях: 
∑x_ij = a_i, i = 1,2,…, m, (2) 
∑x_ij = b_j, j = 1,2,…, n, (3) 
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	Запасы
1	4	10	11	7	30
2	8	6	3	5	60
3	9	12	1	2	10
Потребности	40	20	10	30

 
Проверим необходимое и достаточное  условие разрешимости задачи. 
∑a = 30 + 60 + 10 = 100 
∑b = 40 + 20 + 10 + 30 = 100 
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. 
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	4	10	11	7	30
2	8	6	3	5	60
3	9	12	1	2	10
Потребности	40	20	10	30

 
Этап I. Поиск первого  опорного плана. 
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. 
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j. 
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. 
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. 
Искомый элемент равен 1 
Для этого элемента запасы равны 10, потребности 10. Поскольку минимальным является 10, то вычитаем его. 
x₃₃ = min(10,10) = 10.

4	10	x	7	30
8	6	x	5	60
x	x	1	x	10 - 10 = 0
40	20	10 - 10 = 0	30	0

 
 
Искомый элемент равен 4 
Для этого элемента запасы равны 30, потребности 40. Поскольку минимальным является 30, то вычитаем его. 
x₁₁ = min(30,40) = 30.

4	x	x	x	30 - 30 = 0
8	6	x	5	60
x	x	1	x	0
40 - 30 = 10	20	0	30	0

 
 
Искомый элемент равен 5 
Для этого элемента запасы равны 60, потребности 30. Поскольку минимальным является 30, то вычитаем его. 
x₂₄ = min(60,30) = 30.

4	x	x	x	0
8	6	x	5	60 - 30 = 30
x	x	1	x	0
10	20	0	30 - 30 = 0	0

 
 
Искомый элемент равен 6 
Для этого элемента запасы равны 30, потребности 20. Поскольку минимальным является 20, то вычитаем его. 
x₂₂ = min(30,20) = 20.

4	x	x	x	0
8	6	x	5	30 - 20 = 10
x	x	1	x	0
10	20 - 20 = 0	0	0	0

 
 
Искомый элемент равен 8 
Для этого элемента запасы равны 10, потребности 10. Поскольку минимальным является 10, то вычитаем его. 
x₂₁ = min(10,10) = 10.

4	x	x	x	0
8	6	x	5	10 - 10 = 0
x	x	1	x	0
10 - 10 = 0	0	0	0	0

 

	1	2	3	4	Запасы
1	4[30]	10	11	7	30
2	8[10]	6[20]	3	5[30]	60
3	9	12	1[10]	2	10
Потребности	40	20	10	30

 
2. Подсчитаем число занятых клеток  таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план  является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно: 
F(x) = 4*30 + 8*10 + 6*20 + 5*30 + 1*10 = 480 
Искомый элемент равен 2 
Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его. 
x₃₄ = min(10,30) = 10.

4	10	11	7	30
8	6	3	5	60
x	x	x	2	10 - 10 = 0
40	20	10	30 - 10 = 20	0