Пусть х1-количество продукции вида А, ед, х2 - количество продукции вида Б, ед , х3 - количество продукции вида В, ед, х4 - количество продукции вида Г, ед запланированных к производству. Для их изготовления потребуется ( х1 +2х2+х3) единиц сырья I, (х1 +х2+2х3+х4) единиц сырья II, (х1 +3х2+3х3+2х4) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
х1 +2х2+х3≤18х1 +х2+2х3+х4≤30х1 +3х2+3х3+2х4≤40
По смыслу задачи переменные хi ≥ 0, i=1,2,3,4
Суммарная прибыль : F = 12х1 +7х 2+18x3+10x4 →max.
переход к канонической форме x1+2x2+x3+x5 = 18 x1+x2+2x3+x4+x6 = 30 x1+3x2+3x3+2x4+x7 = 40 За ведущий выберем столбец 3, так как -18 наименьший элемент в F строке.
За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для второй строки является наименьшим.
элемент , aik - элемент разрешающего столбца, arj - элемент разрешающей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x5 18 1 2 1 0 1 0 0 18
x6 30 1 1 2 1 0 1 0 15
x7 40 1 3 3 2 0 0 1 40/3
F(X) 0 -12 -7 -18 -10 0 0 0
Элементы разрешающей строки делим на разрешающий элемент и записываем в соответствующей по номеру строке новой таблицы: , при i = r.Все остальные элементы новой таблицы рассчитываем по формулам:
,при i ≠ r
где - элемент новой симплекс-таблицы, aij, - элемент предыдущей симплекс-таблицы, ark – разрешающий.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x5 14/3 2/3 1 0 -2/3 1 0 -1/3 7
x6 10/3 1/3 -1 0 -1/3 0 1 -2/3 10
x3 40/3 1/3 1 1 2/3 0 0 1/3 40
F(X) 240 -6 11 0 2 0 0 6
В строке F есть отрицательный элемент, значит, полученный план не оптимален. За ведущий выберем столбец 1, так как -6 наименьший элемент в F строке. За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для третьей строки является наименьшим.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x1 7 1 3/2 0 -1 3/2 0 -1/2 -
x6 1 0 -3/2 0 0 -1/2 1 -1/2 -
x3 11 0 1/2 1 1 -1/2 0 1/2 11
F(X) 282 0 20 0 -4 9 0 3
В строке F есть отрицательный элемент, значит, полученный план не оптимален. За ведущий выберем столбец 4, так как -4 наименьший элемент в F строке. За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для третьей строки является наименьшим.
Базис B x1 x2 x3 x4 x5 x6 x7
x1 18 1 2 1 0 1 0 0
x6 1 0 -3/2 0 0 -1/2 1 -1/2
x4 11 0 1/2 1 1 -1/2 0 1/2
F(X) 326 0 22 4 0 7 0 5
В строке F нет отрицательных элементов, значит, полученный план оптимален.
Оптимальный план можно записать так: x1 = 18, x2 = 0, x3 = 0, x4 = 11 F(X) = 12*18 + 7*0 + 18*0 + 10*11 = 326
В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы второго сорта в количестве 1 ед.
Значит необходимо выпускать только изделия вида А и Г в количестве 18 и 11 ед соответственно, чтобы получить максимальную прибыль в размере 326 ден ед
2)
Исходная задача I
Двойственная задача II
x1 ≥ 0 ↔ y1+y2+y3≥12
x2 ≥ 0 ↔ 2y1+y2+3y3≥7
x3 ≥ 0 ↔ y1+2y2+3y3≥18
x4 ≥ 0 ↔ y2+2y3≥10
12x1+7x2+18x3+10x4 → max
↔ 18y1+30y2+40y3 → min
x1+2x2+x3≤18 ↔ y1 ≥ 0
x1+x2+2x3+x4≤30 ↔ y2 ≥ 0
x1+3x2+3x3+2x4≤40 ↔ y3 ≥ 0
двойственная задача линейного программирования будет иметь вид:Z(Y)=18Y1+30Y2+40Y3 (min)
Ограничения:
1Y1 + 1Y2 + 1Y3
≥ 12
2Y1 + 1Y2 + 3Y3
≥ 7
1Y1 + 2Y2 + 3Y3
≥ 18
0Y1 + 1Y2 + 2Y3
≥ 10
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
Задача 1( исходная)
Первоначальные переменные Дополнительные переменные
х1 х2 x3 x4 x5 x6 x7
y4 y5 y6 y7 y1 y2 y3
Дополнительные переменные Первоначальные переменные
Задача 2(двойственная)
Они находятся в последней строке симплекс таблицы.
Fmax(18,0,0,11)=326
Zmin(7,0,5)=326
3) Значение 0 в столбце x1 означает, что использование x1 - выгодно. Значение 22> 0 в столбце x2 означает, что использование x2 - не выгодно. Значение 4> 0 в столбце x3 означает, что использование x3 - не выгодно. Значение 0 в столбце x4 означает, что использование x4 - выгодно. Значение 7 в столбце x5 означает, что теневая цена (двойственная оценка) равна y1=7. Значение 0 в столбце x6 означает, что теневая цена (двойственная оценка) равна y2=0. Значение 5 в столбце x7 означает, что теневая цена (двойственная оценка) равна y3=5.
4) Чувствительность решения к изменению коэффициентов целевой функции. Так как любые изменения коэффициентов целевой функции оказывают влияние на оптимальность полученного ранее решения, то наша цель - найти такие диапазоны изменения коэффициентов в целевой функции (рассматривая каждый из коэффициентов отдельно), при которых оптимальные значения переменных остаются неизменными. Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов. Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений: Вариант расчета №1.
2 1/2
1 1
1 -1/2
0 1/2
12+Δ c1
10+Δ c4
Отсюда получаем условие устойчивости: 2Δc1+1/2Δc4+29≥0 Δc1+Δc4+22≥0 Δc1-1/2Δc4+7≥0 1/2Δc4+5≥0 Затем последовательно находим интервалы устойчивости: Δc1≠0, Δc4=0, Δc1≥-29/2, Δc1≥-22, Δc1≥-7 Δc4≠0, Δc1=0, Δc4≥-58, Δc4≥-22, Δc4≤14, Δc4≥-10 Таким образом, 1-й параметр может быть уменьшен на 4 или увеличен на ∞. Интервал изменения равен: (c1 - ∆c-1; c1 + ∆c1+) [12-4; 12+∞] = [8;∞] Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится. Верхняя граница для: ∆c2+ ∆c2+ = |max[yk/dk2]| для dk2<0. Таким образом, 2-й коэффициент может быть увеличен на 4. ∆c2- = +∞ Интервал изменения равен: (c2 - ∆c2-; +∞) [7-∞;7+4] = [-∞;11] Верхняя граница для: ∆c3+ ∆c3+ = |max[yk/dk3]| для dk3<0. Таким образом, 3-й коэффициент может быть увеличен на 7. ∆c3- = +∞ Интервал изменения равен: (c3 - ∆c3-; +∞) [18-∞;18+7] = [-∞;25] 4-й параметр целевой функции может изменяться в пределах: ∆c4- = min [yk/d4k] для d4k>0. ∆c4+ = |max[yk/d4k]| для d4k<0. Таким образом, 4-й параметр может быть уменьшен на 4 или увеличен на 14. Интервал изменения равен: (c4 - ∆c-4; c4 + ∆c4+) [10-4; 10+14] = [6;24] Если значение c4 будет лежать в данном интервале, то оптимальный план не изменится. Найдем интервалы устойчивости ресурсов. Вариант расчета №1. При этом условие устойчивости двойственных оценок задачи исходит из выражения: X1=X0+ΔX=A-1(B+ΔB) в которой компоненты вектора X1 должны быть неотрицательны, т.е. все xj≥0. На этом основании для нашей задачи можно записать:
x1
x6
x4
= 1 0 0
-1/2 1 -1/2
-1/2 0 1/2
18+Δ b1
30+Δ b2
40+Δ b3
Отсюда получаем условие устойчивости: Δb1+18≥0 -1/2Δb1+Δb2-1/2Δb3+1≥0 -1/2Δb1+1/2Δb3+11≥0 Затем последовательно находим интервалы устойчивости: Δb1≠0, Δb2=Δb3=0, Δb1≥-18, Δb1≤2, Δb1≤22 Δb2≠0, Δb1=Δb3=0, Δb2≥-1 Δb3≠0, Δb1=Δb2=0, Δb3≤2, Δb3≥-22 Для корректного решения задачи необходимо ввести еще дополнительные ограничения, вытекающие из экономического содержания решаемой задачи. Предельные значения (нижняя и верхняя границы) изменения каждого из ресурсов, для которых двойственные оценки остаются неизменными, определяются еще и таким образом. Вариант расчета №2. 1-й запас может изменяться в пределах: ∆b1- = min[xk/dk1] для dk1>0. ∆b1+ = |max[xk/dk1]| для dk1<0. Таким образом, 1-й запас может быть уменьшен на 18 или увеличен на 2. Интервал изменения равен: (b1 - ∆b1-; b1 + ∆b1)+ [18-18; 18+2] = [0;20] Нижняя граница для: ∆b2- ∆b2- = min[xk/dk2] для dk2>0. Таким образом, 2-й запас может быть уменьшен на 1. 2-й вид ресурса в оптимальном плане недоиспользован, является недефицитным. Увеличение данного ресурса приведет лишь к росту его остатка. При этом структурных изменений в оптимальном плане не будет, так как двойственная оценка y2 = 0. Другими словами, верхняя граница b2+ = +∞ ∆b2+ = +∞ Интервал изменения равен: (b2 - ∆b2-; +∞) [30-1; +∞] = [29;+∞] 3-й запас может изменяться в пределах: ∆b3- = min[xk/dk3] для dk3>0. ∆b3+ = |max[xk/dk3]| для dk3<0. Таким образом, 3-й запас может быть уменьшен на 22 или увеличен на 2. Интервал изменения равен: (b3 - ∆b3-; b3 + ∆b3)+ [40-22; 40+2] = [18;42] В оптимальный план не вошла основная переменная x2, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок: x2 может изменяться в пределах: -2/3 ≤ x2 ≤ 9
Поэтому при увеличении запасов первого сырья на 4 единицы, второго сырья на 3 единицы и уменьшении запасов сырья третьего типа на 3 единицы план увеличится на 13 ед. Включение в план изделия Д нецелесообразно, так как прибыль уменьшиться на 236 ден ед
Нужно полное решение этой работы?
Решение
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 40 + 20 + 40 = 100 ∑b = 25 + 10 + 20 + 30 + 15 = 100 Суммарная потребность груза равна запасам груза у поставщиков. модель транспортной задачи является закрытой. Поиск первого опорного плана.
Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A1B2 и равен 3. Запасы поставщика A1 составляют 40 ед. Потребность потребителя B2 составляет 10 ед. От поставщика A1 к потребителю B2 будем доставлять 10 ед.
Мы полностью исчерпали запасы потребителя B2 . Вычеркиваем столбец 2 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.
B1 B2 B3 B4 B5 Запасы
A1 5 3[10] 4[20] 6 4[10] 40
A2 3[20] 4 10 5 7 20
A3 4[5] 6 9 3[30] 4[5] 40
Потребности 25 10 20 30 15
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 3*10 + 4*20 + 4*10 + 3*20 + 4*5 + 3*30 + 4*5 = 340 Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 3; 0 + v2 = 3; v2 = 3 u1 + v3 = 4; 0 + v3 = 4; v3 = 4 u1 + v5 = 4; 0 + v5 = 4; v5 = 4 u3 + v5 = 4; 4 + u3 = 4; u3 = 0 u3 + v1 = 4; 0 + v1 = 4; v1 = 4 u2 + v1 = 3; 4 + u2 = 3; u2 = -1 u3 + v4 = 3; 0 + v4 = 3; v4 = 3
v1=4 v2=3 v3=4 v4=3 v5=4
u1=0 5 3[10] 4[20] 6 4[10]
u2=-1 3[20] 4 10 5 7
u3=0 4[5] 6 9 3[30] 4[5]
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj≤ cij. Минимальные затраты составят: F(x) = 3*10 + 4*20 + 4*10 + 3*20 + 4*5 + 3*30 + 4*5 = 340
2)
B1 B2 B3 B4 B5 Запасы
A1 5 30[5] 4[20] 6 4[15] 40
A2 3[20] 4 10 5 7 20
A3 4[5] 6[5] 9 3[30] 4 40
Потребности 25 10 20 30 15
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 30*5 + 4*20 + 4*15 + 3*20 + 4*5 + 6*5 + 3*30 = 490 Улучшение опорного плана.
v1=28 v2=30 v3=4 v4=27 v5=4 Запасы
u1=0 5[+] 30[5][-] 4[20] 6 4[15] 40
u2=-25 3[20] 4 10 5 7 20
u3=-24 4[5][-] 6[5][+] 9 3[30] 4 40
Потребности 25 10 20 30 15
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (1;1): 0 + 28 > 5; ∆11 = 0 + 28 - 5 = 23 > 0 (1;4): 0 + 27 > 6; ∆14 = 0 + 27 - 6 = 21 > 0 (2;2): -25 + 30 > 4; ∆22 = -25 + 30 - 4 = 1 > 0 max(23,21,1) = 23 Выбираем максимальную оценку свободной клетки (1;1): 5 Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,1 → 1,2 → 3,2 → 3,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
. у = min (3, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
v1=5 v2=30 v3=4 v4=27 v5=4 Запасы
u1=0 5[5][+] 30[0][-] 4[20] 6 4[15] 40
u2=-2 3[20][-] 4[+] 10 5 7 20
u3=-24 4 6[10] 9 3[30] 4 40
Потребности 25 10 20 30 15
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (1;4): 0 + 27 > 6; ∆14 = 0 + 27 - 6 = 21 > 0 (2;2): -2 + 30 > 4; ∆22 = -2 + 30 - 4 = 24 > 0 (2;4): -2 + 27 > 5; ∆24 = -2 + 27 - 5 = 20 > 0 max(21,24,20) = 24 Выбираем максимальную оценку свободной клетки (2;2): 4 Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,2 → 2,1 → 1,1 → 1,2). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
v1=5 v2=6 v3=4 v4=3 v5=4 Запасы
u1=0 5[5] 30 4[20] 6 4[15] 40
u2=-2 3[20][-] 4[0][+] 10 5 7 20
u3=0 4[+] 6[10][-] 9 3[30] 4 40
Потребности 25 10 20 30 15
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (3;1): 0 + 5 > 4; ∆31 = 0 + 5 - 4 = 1 > 0 Выбираем максимальную оценку свободной клетки (3;1): 4 Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,1 → 3,2 → 2,2 → 2,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
