Симплекс-метод. Поиск наибольшего значения
Вариант 1.1. Для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 т. Количество сырья каждого вида, необходимое для производства единицы цемента первого вида соответственно равны: 12, 4 и 3. Для цемента второго вида: 3, 5 и 14. Прибыль от реализации цемента первого вида составляет 6 у.е., от цемента второго вида - 4 у.е. Составить план, обеспечивающий наибольшую прибыль производству:
а) записать математическую модель;
б) решить задачу графическим методом;
в) решить задачу симплекс-методом;
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.
Решение:
а) математическая модель;
x1 – производство цемента первого вида;
x2 – производство цемента второго вида;
12x1 + 3x2 ≤ 264
4x1 + 5x2 ≤ 136
3x1 + 14x2 ≤ 266
x1 ≥ 0, x2 ≥ 0
Целевая функция:
6x1 + 4x2 → max
б) решим задачу графическим методом;
Необходимо найти максимальное значение целевой функции F = 6X1+4X2 => max, при системе ограничений:
12x1+3x2≤264 (1)
4x1+5x2≤136 (2)
3x1+14x2≤266 (3)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 6X1+4X2 => max.
Построим прямую, отвечающую значению функции F = 0: F = 6X1+4X2
= 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует
максимальное решение, поэтому двигаем прямую до последнего касания обозначенной
области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения
прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых:
12x1+3x2≤264
4x1+5x2≤136
Решив систему уравнений, получим:
x1 = (264-3x2)/12
4(264-3x2)/12+5x2 = 136
x1 = 19, x2 = 12
Откуда найдем максимальное значение целевой функции:
F(X) = 6*19 + 4*12 = 162
Таким образом, чтобы получить максимальную прибыль необходимо выпускать 19 т. цемента 1-го вида, и 12 т. цемента 2-го вида.
в) решить задачу симплекс-методом;
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 6x1+4x2 при следующих условиях-ограничений.
12x1+3x2≤264
4x1+5x2≤136
3x1+14x2≤266
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
12x1 + 3x2 + 1x3 + 0x4 + 0x5 = 264
4x1 + 5x2 + 0x3 + 1x4 + 0x5 = 136
3x1 + 14x2 + 0x3 + 0x4 + 1x5 = 266
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,264,136,266)
|
План |
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
|
0 |
x3 |
264 |
12 |
3 |
1 |
0 |
0 |
|
|
x4 |
136 |
4 |
5 |
0 |
1 |
0 |
|
|
x5 |
266 |
3 |
14 |
0 |
0 |
1 |
|
Индексная строка |
F(X0) |
0 |
-6 |
-4 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
|
План |
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
|
1 |
x3 |
264 |
12 |
3 |
1 |
0 |
0 |
22 |
|
|
x4 |
136 |
4 |
5 |
0 |
1 |
0 |
34 |
|
|
x5 |
266 |
3 |
14 |
0 |
0 |
1 |
88.67 |
|
Индексная строка |
F(X1) |
0 |
-6 |
-4 |
0 |
0 |
0 |
0 |
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 12 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x1
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=12
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (12), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
|
План |
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
|
2 |
x1 |
22 |
1 |
0.25 |
0.0833 |
0 |
0 |
88 |
|
|
x4 |
48 |
0 |
4 |
-0.3333 |
1 |
0 |
12 |
|
|
x5 |
200 |
0 |
13.25 |
-0.25 |
0 |
1 |
15.09 |
|
Индексная строка |
F(X2) |
132 |
0 |
-2.5 |
0.5 |
0 |
0 |
0 |
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x2
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
|
План |
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
|
3 |
x1 |
19 |
1 |
0 |
0.1042 |
-0.0625 |
0 |
|
|
x2 |
12 |
0 |
1 |
-0.0833 |
0.25 |
0 |
|
|
x5 |
41 |
0 |
0 |
0.8542 |
-3.31 |
1 |
|
Индексная строка |
F(X3) |
162 |
0 |
0 |
0.2917 |
0.625 |
0 |
Оптимальный план можно записать так:
x1 = 19
x2 = 12
x5 = 41
F(X) = 6*19 + 4*12 = 162
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.
Составим двойственную задачу к прямой задаче.
12y1+4y2+3y3≥6
3y1+5y2+14y3≥4
264y1+136y2+266y3 => min
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 0.29
y2 = 0.62
y3 = 0
Z(Y) = 264*0.29+136*0.62+266*0 = 162
2. На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.
|
Поставщик |
В1 |
В2 |
В3 |
В4 |
Запасы груза |
|
А1 |
4 |
6 |
19 |
21 |
100 |
|
А2 |
29 |
4 |
8 |
6 |
150 |
|
А3 |
7 |
11 |
13 |
14 |
200 |
|
Потребности |
220 |
80 |
75 |
75 |
|
Решение:
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
|
1 |
2 |
3 |
4 |
Запасы |
|
1 |
4 |
6 |
19 |
21 |
100 |
|
2 |
29 |
4 |
8 |
6 |
150 |
|
3 |
7 |
11 |
13 |
14 |
200 |
|
Потребности |
220 |
80 |
75 |
75 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 100 + 150 + 200 = 450
∑ b = 220 + 80 + 75 + 75 = 450
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
|
|
1 |
2 |
3 |
4 |
Запасы |
|
1 |
4 |
6 |
19 |
21 |
100 |
|
2 |
29 |
4 |
8 |
6 |
150 |
|
3 |
7 |
11 |
13 |
14 |
200 |
|
Потребности |
220 |
80 |
75 |
75 |
|
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Искомый элемент равен 4
Для этого элемента запасы равны 100, потребности 220. Поскольку минимальным является 100, то вычитаем его.
|
4 |
x |
x |
x |
0 |
|
29 |
4 |
8 |
6 |
150 |
|
7 |
11 |
13 |
14 |
200 |
|
120 |
80 |
75 |
75 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 150, потребности 80. Поскольку минимальным является 80, то вычитаем его.
|
4 |
x |
x |
x |
0 |
|
29 |
4 |
8 |
6 |
70 |
|
7 |
x |
13 |
14 |
200 |
|
120 |
0 |
75 |
75 |
0 |
Искомый элемент равен 6
Для этого элемента запасы равны 70, потребности 75. Поскольку минимальным является 70, то вычитаем его.
|
4 |
x |
x |
x |
0 |
|
x |
4 |
x |
6 |
0 |
|
7 |
x |
13 |
14 |
200 |
|
120 |
0 |
75 |
5 |
0 |
Искомый элемент равен 7
Для этого элемента запасы равны 200, потребности 120. Поскольку минимальным является 120, то вычитаем его.
|
4 |
x |
x |
x |
0 |
|
x |
4 |
x |
6 |
0 |
|
7 |
x |
13 |
14 |
80 |
|
0 |
0 |
75 |
5 |
0 |
Искомый элемент равен 13
Для этого элемента запасы равны 80, потребности 75. Поскольку минимальным является 75, то вычитаем его.
|
4 |
x |
x |
x |
0 |
|
x |
4 |
x |
6 |
0 |
|
7 |
x |
13 |
14 |
5 |
|
0 |
0 |
0 |
5 |
0 |
Искомый элемент равен 14
Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.
|
4 |
x |
x |
x |
0 |
|
x |
4 |
x |
6 |
0 |
|
7 |
x |
13 |
14 |
0 |
|
0 |
0 |
0 |
0 |
0 |
|
|
1 |
2 |
3 |
4 |
Запасы |
|
1 |
4[100] |
6 |
19 |
21 |
100 |
|
2 |
29 |
4[80] |
8 |
6[70] |
150 |
|
3 |
7[120] |
11 |
13[75] |
14[5] |
200 |
|
Потребности |
220 |
80 |
75 |
75 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u3 + v1 = 7; 4 + u3 = 7; u3 = 3
u3 + v3 = 13; 3 + v3 = 13; v3 = 10
u3 + v4 = 14; 3 + v4 = 14; v4 = 11
u2 + v4 = 6; 11 + u2 = 6; u2 = -5
u2 + v2 = 4; -5 + v2 = 4; v2 = 9
|
|
v1=4 |
v2=9 |
v3=10 |
v4=11 |
|
u1=0 |
4[100] |
6 |
19 |
21 |
|
u2=-5 |
29 |
4[80] |
8 |
6[70] |
|
u3=3 |
7[120] |
11 |
13[75] |
14[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;2): 0 + 9 > 6; ∆12 = 0 + 9 - 6 = 3
(3;2): 3 + 9 > 11; ∆32 = 3 + 9 - 11 = 1
max(3,1) = 3
Выбираем максимальную оценку свободной клетки (1;2): 6
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
|
|
1 |
2 |
3 |
4 |
Запасы |
|
1 |
4[100][-] |
6[+] |
19 |
21 |
100 |
|
2 |
29 |
4[80][-] |
8 |
6[70][+] |
150 |
|
3 |
7[120][+] |
11 |
13[75] |
14[5][-] |
200 |
|
Потребности |
220 |
80 |
75 |
75 |
|
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
|
|
1 |
2 |
3 |
4 |
Запасы |
|
1 |
4[95] |
6[5] |
19 |
21 |
100 |
|
2 |
29 |
4[75] |
8 |
6[75] |
150 |
|
3 |
7[125] |
11 |
13[75] |
14 |
200 |
|
Потребности |
220 |
80 |
75 |
75 |
|
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u3 + v1 = 7; 4 + u3 = 7; u3 = 3
u3 + v3 = 13; 3 + v3 = 13; v3 = 10
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u2 + v2 = 4; 6 + u2 = 4; u2 = -2
u2 + v4 = 6; -2 + v4 = 6; v4 = 8
|
|
v1=4 |
v2=6 |
v3=10 |
v4=8 |
|
u1=0 |
4[95] |
6[5] |
19 |
21 |
|
u2=-2 |
29 |
4[75] |
8 |
6[75] |
|
u3=3 |
7[125] |
11 |
13[75] |
14 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui+ vi <= cij.
Минимальные затраты составят:
F(x) = 4*95 + 6*5 + 4*75 + 6*75 + 7*125 + 13*75 = 3010