Планируется покупка книг для семейной библиотеки. Муж читает только классическую прозу и фантастику, жена – стихи (классику), старший сын – фантастику, а младшему сыну собираются покупать энциклопедии. Муж хочет, чтобы из купленных книг не менее 10 были для него, причём и муж и жена рассчитывают от 2 до 7 книг для чтения каждый. Жена надеется, что и классическая проза ей тоже будет интересна, поэтому она согласна купить поэзии не более того количества, в котором будет куплена прозаическая классика. Также договорились, что книг, которые собираются читать муж и старший сын, будет ровно половина от общего числа купленных книг. Всего собираются купить не более 30 книг. Стоимость книг (в среднем):
– классическая проза – 30 руб. и стихи – 20 руб.;
– фантастика – 15 руб.;
– энциклопедии – по 70 руб.
Сколько и каких книг нужно купить, чтобы с минимальными расходами удовлетворить пожелания всех членов семьи?
Решение
Обозначим переменные (количество книг, шт.):
х1 – классическая проза;
х2 – стихи;
х3 – фантастика;
х4– энциклопедии.
F(x)=30х1+20х2+15х3+70х4 – целевая функция, имеющая следующее содержание: расходы на покупку книг для семейной библиотеки должны быть минимальными;
х1+х3>10 – предпочтения мужа: не менее 10 книг должны составлять классическая проза и фантастика;
х2<х1 – предпочтения жены: поэзии должно быть не больше, чем прозаической классики;
х1+х3=1/2(х1+х2+х3+х4) – классической прозы и фантастики должно быть ровно половина от общего числа покупаемых книг;
х1+х2+х3+х4<30 – всего планируется покупка не более 30 книг;
х1>2 – классической прозы должно быть не менее 2 книг;
х1<7 – классической прозы должно быть не более 7 книг;
х2>2– поэзии должно быть не менее 2 книг;
х2<7– поэзии должно быть не более 7 книг;
х3>2– фантастики должно быть не менее 2 книг;
х3<7– фантастики должно быть не более 7 книг;
х1>0, х2>0, х3>0, х4>0, – искомые количества закупаемых книг не должны быть отрицательными.
х1 – целое, х2 – целое, х3 – целое, х4 – целое – искомые количества закупаемых книг должно быть целым.
Математическая модель задачи имеет вид:
F(X) = 30x1+20x2+15x3+70x4 → min
x1+x3≥10,-x1+x2≤0,0.5x1-0.5x2+0.5x3-0.5x4=0,x1+x2+x3+x4≤30,x1≥2,x1≤7,x2≥2,x2≤7,x3≥2,x3≤7,
х1>0,
х2>0,
х3>0,
х4>0,
х1 – целое,
х2 – целое,
х3 – целое,
х4 – целое.
Решим задачу симплекс-методом с использованием симплекс-таблицы.
Для построения опорного плана 1 систему неравенств приводим к системе уравнений путем введения дополнительных переменных (переходим к канонической форме).
В 1-м неравенстве смысла (≥) ведем неотрицательную базисную переменную x5 со знаком минус. В 2-м неравенстве смысла (≤) ведем неотрицательную базисную переменную x6. В 4-м неравенстве смысла (≤) ведем неотрицательную базисную переменную x7. В 5-м неравенстве смысла (≥) ведем неотрицательную базисную переменную x8 со знаком минус. В 6-м неравенстве смысла (≤) ведем неотрицательную базисную переменную x9. В 7-м неравенстве смысла (≥) ведем неотрицательную базисную переменную x10 со знаком минус. В 8-м неравенстве смысла (≤) ведем неотрицательную базисную переменную x11. В 9-м неравенстве смысла (≥) ведем неотрицательную базисную переменную x12 со знаком минус. В 10-м неравенстве смысла (≤) ведем неотрицательную базисную переменную x13.
x1+x3-x5 = 10-x1+x2+x6 = 00.5x1-0.5x2+0.5x3-0.5x4 = 0x1+x2+x3+x4+x7 = 30x1-x8 = 2x1+x9 = 7x2-x10 = 2x2+x11 = 7x3-x12 = 2x3+x13 = 7Расширенная матрица системы ограничений-равенств данной задачи:
1 0 1 0 -1 0 0 0 0 0 0 0 0 10
-1 1 0 0 0 1 0 0 0 0 0 0 0 0
0.5 -0.5 0.5 -0.5 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 30
1 0 0 0 0 0 0 -1 0 0 0 0 0 2
1 0 0 0 0 0 0 0 1 0 0 0 0 7
0 1 0 0 0 0 0 0 0 -1 0 0 0 2
0 1 0 0 0 0 0 0 0 0 1 0 0 7
0 0 1 0 0 0 0 0 0 0 0 -1 0 2
0 0 1 0 0 0 0 0 0 0 0 0 1 7
Приводим систему к единичной матрице методом жордановских преобразований.
1
. В качестве базовой переменной можно выбрать x5.
Получим новую матрицу:
-1 0 -1 0 1 0 0 0 0 0 0 0 0 -10
-1 1 0 0 0 1 0 0 0 0 0 0 0 0
0.5 -0.5 0.5 -0.5 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 30
1 0 0 0 0 0 0 -1 0 0 0 0 0 2
1 0 0 0 0 0 0 0 1 0 0 0 0 7
0 1 0 0 0 0 0 0 0 -1 0 0 0 2
0 1 0 0 0 0 0 0 0 0 1 0 0 7
0 0 1 0 0 0 0 0 0 0 0 -1 0 2
0 0 1 0 0 0 0 0 0 0 0 0 1 7
2. В качестве базовой переменной можно выбрать x6.3. В качестве базовой переменной можно выбрать x7.4. В качестве базовой переменной можно выбрать x8.Получим новую матрицу:
-1 0 -1 0 1 0 0 0 0 0 0 0 0 -10
-1 1 0 0 0 1 0 0 0 0 0 0 0 0
0.5 -0.5 0.5 -0.5 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 30
-1 0 0 0 0 0 0 1 0 0 0 0 0 -2
1 0 0 0 0 0 0 0 1 0 0 0 0 7
0 1 0 0 0 0 0 0 0 -1 0 0 0 2
0 1 0 0 0 0 0 0 0 0 1 0 0 7
0 0 1 0 0 0 0 0 0 0 0 -1 0 2
0 0 1 0 0 0 0 0 0 0 0 0 1 7
5. В качестве базовой переменной можно выбрать x9.6. В качестве базовой переменной можно выбрать x10.Получим новую матрицу:
-1 0 -1 0 1 0 0 0 0 0 0 0 0 -10
-1 1 0 0 0 1 0 0 0 0 0 0 0 0
0.5 -0.5 0.5 -0.5 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 30
-1 0 0 0 0 0 0 1 0 0 0 0 0 -2
1 0 0 0 0 0 0 0 1 0 0 0 0 7
0 -1 0 0 0 0 0 0 0 1 0 0 0 -2
0 1 0 0 0 0 0 0 0 0 1 0 0 7
0 0 1 0 0 0 0 0 0 0 0 -1 0 2
0 0 1 0 0 0 0 0 0 0 0 0 1 7
7. В качестве базовой переменной можно выбрать x11.8. В качестве базовой переменной можно выбрать x12.Получим новую матрицу:
-1 0 -1 0 1 0 0 0 0 0 0 0 0 -10
-1 1 0 0 0 1 0 0 0 0 0 0 0 0
0.5 -0.5 0.5 -0.5 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 30
-1 0 0 0 0 0 0 1 0 0 0 0 0 -2
1 0 0 0 0 0 0 0 1 0 0 0 0 7
0 -1 0 0 0 0 0 0 0 1 0 0 0 -2
0 1 0 0 0 0 0 0 0 0 1 0 0 7
0 0 -1 0 0 0 0 0 0 0 0 1 0 -2
0 0 1 0 0 0 0 0 0 0 0 0 1 7
9. В качестве базовой переменной можно выбрать x13.10. В качестве базовой переменной можно выбрать x4.
Разрешающий элемент РЭ=-0.5. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x4 на разрешающий элемент РЭ=-0.5. На месте разрешающего элемента Получим 1. В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
-1 0 -1 0 1 0 0 0 0 0 0 0 0 -10
-1 1 0 0 0 1 0 0 0 0 0 0 0 0
-1 1 -1 1 0 0 0 0 0 0 0 0 0 0
2 0 2 0 0 0 1 0 0 0 0 0 0 30
-1 0 0 0 0 0 0 1 0 0 0 0 0 -2
1 0 0 0 0 0 0 0 1 0 0 0 0 7
0 -1 0 0 0 0 0 0 0 1 0 0 0 -2
0 1 0 0 0 0 0 0 0 0 1 0 0 7
0 0 -1 0 0 0 0 0 0 0 0 1 0 -2
0 0 1 0 0 0 0 0 0 0 0 0 1 7
Т.к. в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (5,6,4,7,8,9,10,11,12,13).
Выразим базисные переменные через остальные:x5 = x1+x3-10x6 = x1-x2x4 = x1-x2+x3x7 = -2x1-2x3+30x8 = x1-2x9 = -x1+7x10 = x2-2x11 = -x2+7x12 = x3-2x13 = -x3+7Подставим их в целевую функцию:F(X) = 30x1+20x2+15x3+70(x1-x2+x3)илиF(X) = 100x1-50x2+85x3
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x5 следует ввести переменную x3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13
x3 10 1 0 1 0 -1 0 0 0 0 0 0 0 0
x6 0 -1 1 0 0 0 1 0 0 0 0 0 0 0
x4 10 0 1 0 1 -1 0 0 0 0 0 0 0 0
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0
x8 -2 -1 0 0 0 0 0 0 1 0 0 0 0 0
x9 7 1 0 0 0 0 0 0 0 1 0 0 0 0
x10 -2 0 -1 0 0 0 0 0 0 0 1 0 0 0
x11 7 0 1 0 0 0 0 0 0 0 0 1 0 0
x12 8 1 0 0 0 -1 0 0 0 0 0 0 1 0
x13 -3 -1 0 0 0 1 0 0 0 0 0 0 0 1
∆ -850 15 -50 0 0 85 0 0 0 0 0 0 0 0
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x13 следует ввести переменную x1.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13
x3 7 0 0 1 0 0 0 0 0 0 0 0 0 1
x6 3 0 1 0 0 -1 1 0 0 0 0 0 0 -1
x4 10 0 1 0 1 -1 0 0 0 0 0 0 0 0
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0
x8 1 0 0 0 0 -1 0 0 1 0 0 0 0 -1
x9 4 0 0 0 0 1 0 0 0 1 0 0 0 1
x10 -2 0 -1 0 0 0 0 0 0 0 1 0 0 0
x11 7 0 1 0 0 0 0 0 0 0 0 1 0 0
x12 5 0 0 0 0 0 0 0 0 0 0 0 1 1
x1 3 1 0 0 0 -1 0 0 0 0 0 0 0 -1
∆ -895 0 -50 0 0 100 0 0 0 0 0 0 0 15
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x10 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13
x3 7 0 0 1 0 0 0 0 0 0 0 0 0 1
x6 1 0 0 0 0 -1 1 0 0 0 1 0 0 -1
x4 8 0 0 0 1 -1 0 0 0 0 1 0 0 0
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0
x8 1 0 0 0 0 -1 0 0 1 0 0 0 0 -1
x9 4 0 0 0 0 1 0 0 0 1 0 0 0 1
x2 2 0 1 0 0 0 0 0 0 0 -1 0 0 0
x11 5 0 0 0 0 0 0 0 0 0 1 1 0 0
x12 5 0 0 0 0 0 0 0 0 0 0 0 1 1
x1 3 1 0 0 0 -1 0 0 0 0 0 0 0 -1
∆ -795 0 0 0 0 100 0 0 0 0 -50 0 0 15
Выразим базисные переменные через остальные:x3 = -x13+7x6 = x5-x10+x13+1x4 = x5-x10+8x7 = -2x5+10x8 = x5+x13+1x9 = -x5-x13+4x2 = x10+2x11 = -x10+5x12 = -x13+5x1 = x5+x13+3Подставим их в целевую функцию:F(X) = 30(x5+x13+3)+20(x10+2)+15(-x13+7)+70(x5-x10+8)илиF(X) = 100x5-50x10+15x13+795x3+x13=7-x5+x6+x10-x13=1x4-x5+x10=82x5+x7=10-x5+x8-x13=1x5+x9+x13=4x2-x10=2x10+x11=5x12+x13=5x1-x5-x13=3При вычислениях значение Fc = 795 временно не учитываем.Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 0 -1 1 0 0 0 1 0 0 -1
0 0 0 1 -1 0 0 0 0 1 0 0 0
0 0 0 0 2 0 1 0 0 0 0 0 0
0 0 0 0 -1 0 0 1 0 0 0 0 -1
0 0 0 0 1 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 -1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 0 0 -1 0 0 0 0 0 0 0 -1
Решим систему уравнений относительно базисных переменных: x3, x6, x4, x7, x8, x9, x2, x11, x12, x1
Полагая, что свободные переменные равны 0, получим опорный план 1: X0 = (3,2,7,8,0,1,10,1,4,0,5,5,0)
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13
x3 7 0 0 1 0 0 0 0 0 0 0 0 0 1
x6 1 0 0 0 0 -1 1 0 0 0 1 0 0 -1
x4 8 0 0 0 1 -1 0 0 0 0 1 0 0 0
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0
x8 1 0 0 0 0 -1 0 0 1 0 0 0 0 -1
x9 4 0 0 0 0 1 0 0 0 1 0 0 0 1
x2 2 0 1 0 0 0 0 0 0 0 -1 0 0 0
x11 5 0 0 0 0 0 0 0 0 0 1 1 0 0
x12 5 0 0 0 0 0 0 0 0 0 0 0 1 1
x1 3 1 0 0 0 -1 0 0 0 0 0 0 0 -1
∆ 0 0 0 0 0 -100 0 0 0 0 50 0 0 -15
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10↓ x11 x12 x13 min
x3 7 0 0 1 0 0 0 0 0 0 0 0 0 1 -
←x6 1 0 0 0 0 -1 1 0 0 0 1 0 0 -1 1
x4 8 0 0 0 1 -1 0 0 0 0 1 0 0 0 8
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0 -
x8 1 0 0 0 0 -1 0 0 1 0 0 0 0 -1 -
x9 4 0 0 0 0 1 0 0 0 1 0 0 0 1 -
x2 2 0 1 0 0 0 0 0 0 0 -1 0 0 0 -
x11 5 0 0 0 0 0 0 0 0 0 1 1 0 0 5
x12 5 0 0 0 0 0 0 0 0 0 0 0 1 1 -
x1 3 1 0 0 0 -1 0 0 0 0 0 0 0 -1 -
∆ 0 0 0 0 0 -100 0 0 0 0 50 0 0 -15 0
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13↓ min
x3 7 0 0 1 0 0 0 0 0 0 0 0 0 1 7
x10 1 0 0 0 0 -1 1 0 0 0 1 0 0 -1 -
x4 7 0 0 0 1 0 -1 0 0 0 0 0 0 1 7
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0 -
x8 1 0 0 0 0 -1 0 0 1 0 0 0 0 -1 -
←x9 4 0 0 0 0 1 0 0 0 1 0 0 0 1 4
x2 3 0 1 0 0 -1 1 0 0 0 0 0 0 -1 -
x11 4 0 0 0 0 1 -1 0 0 0 0 1 0 1 4
x12 5 0 0 0 0 0 0 0 0 0 0 0 1 1 5
x1 3 1 0 0 0 -1 0 0 0 0 0 0 0 -1 -
∆ -50 0 0 0 0 -50 -50 0 0 0 0 0 0 35 0
БП B x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13
x3 3 0 0 1 0 -1 0 0 0 -1 0 0 0 0
x10 5 0 0 0 0 0 1 0 0 1 1 0 0 0
x4 3 0 0 0 1 -1 -1 0 0 -1 0 0 0 0
x7 10 0 0 0 0 2 0 1 0 0 0 0 0 0
x8 5 0 0 0 0 0 0 0 1 1 0 0 0 0
x13 4 0 0 0 0 1 0 0 0 1 0 0 0 1
x2 7 0 1 0 0 0 1 0 0 1 0 0 0 0
x11 0 0 0 0 0 0 -1 0 0 -1 0 1 0 0
x12 1 0 0 0 0 -1 0 0 0 -1 0 0 1 0
x1 7 1 0 0 0 0 0 0 0 1 0 0 0 0
∆ -190 0 0 0 0 -85 -50 0 0 -35 0 0 0 0
Т.к
Задать вопрос
на новый заказ в Автор24.
