Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида

Формулируем модель
Данному варианту соответствуют следующие числа:
Таблица 1
i 1 2 3 4 5 6 7 8 9 10 11 12
3 6 7 9 3 7 4 1 4 2 8 6 4
Таблица 2
i 13 14 15 16 17 18 19 20 21 22 23 24
5 6 9 1 5 6 1 9 3 2 1 5
с учетом условий:
b1=r+p
b2=p+g
b3=g+w
Таблица 3
i
1 2 3 4 5 6
a11 a12 a13 a14 a15 a16
6 7 9 3 7 4
i
7 8 9 10 11 12
a21 a22 a23 a24 a25 a26
1 4 2 8 6 4
i
13 14 15 16 17 18
a31 a32 a33 a34 a35 a36
5 6 9 1 5 6
Таблица 4
i
3 6 9 12 15 18
с1 с2 с3 с4 с5 с6
9 4 2 4 9 6
Таблица 5
i
19 20 21 22
r p g
1 9 3 2
Модель целочисленного программирования имеет вид:
9x1+4x2+2x3+4x4+9x5+6x6→max
6x1+7x2+9x3+3x4+7x5+4x6≤10
x1+4x2+2x3+8x4+6x5+4x6≤12
5x1+6x2+9x3+x4+5+6x6≤5
xj≥0
2. Постановка задачи:
Предприятие производит три вида шоколадных конфет: «Аленка», «Ромашка», «Пилот», «Ласточка», «Мак» и «Ирис», затрачивая при этом какао-масло, соевую муку и сахар. Данные о расходе ресурсов на каждый вид конфет приведены в таблице.
Продажа каждого вида конфет приносит следующую прибыль за 1 кг:
«Аленка» - 9 у.е
«Ромашка» - 4 у.е
«Пилот» - 3 у.е
«Ласточка» - 4 у.е
«Мак» - 9 у.е
«Ирис» - 6 у.е
Предприятие также ограничено в ресурсах. Запасы какао-масла составляют 10 кг, соевой муки – 12 кг, сахара – 5 кг.
Необходимо определить такую комбинацию произведенных конфет, при которой предприятие получит наибольшую прибыль при имеющихся ресурсах.
Продукция Объем ресурсов предприятия, кг
Аленка Ромашка Пилот Ласточка Мак Ирис
Какао-масло 6 7 9 3 7 4 10
Соевая мука 1 4 2 8 6 4 12
Сахар 5 6 9 1 5 6 5
Стоимость единицы товара, у.е
9 4 2 4 9 6 max
3. Оптимальное решение модели:
В 1-м неравенстве смысла (≤) вводим базисную переменную x7. В 2-м неравенстве смысла (≤) вводим базисную переменную x8. В 3-м неравенстве смысла (≤) вводим базисную переменную x9.
6x1+7x2+9x3+3x4+7x5+4x6+x7 = 10
x1+4x2+2x3+8x4+6x5+4x6+x8 = 12
5x1+6x2+9x3+x4+5x5+6x6+x9 = 5
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
6 7 9 3 7 4 1 0 0 10
1 4 2 8 6 4 0 1 0 12
5 6 9 1 5 6 0 0 1 5
1. В качестве базовой переменной можно выбрать x7.
2. В качестве базовой переменной можно выбрать x8.
3. В качестве базовой переменной можно выбрать x9.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (7,8,9).
Соответствующие уравнения имеют вид:
6x1+7x2+9x3+3x4+7x5+4x6+x7 = 10
x1+4x2+2x3+8x4+6x5+4x6+x8 = 12
5x1+6x2+9x3+x4+5x5+6x6+x9 = 5
Выразим базисные переменные через остальные:
x7 = -6x1-7x2-9x3-3x4-7x5-4x6+10
x8 = -x1-4x2-2x3-8x4-6x5-4x6+12
x9 = -5x1-6x2-9x3-x4-5x5-6x6+5
Определим максимальное значение целевой функции
F(X) = 9x1+4x2+2x3+4x4+9x5+6x6
при следующих условиях-ограничений.
6x1+7x2+9x3+3x4+7x5+4x6+x7+10=10
x1+4x2+2x3+8x4+6x5+4x6+x8+12=12
5x1+6x2+9x3+x4+5x5+6x6+x9+5=5
Расширенная матрица системы ограничений-равенств данной задачи:
6 7 9 3 7 4 1 0 0 10
1 4 2 8 6 4 0 1 0 12
5 6 9 1 5 6 0 0 1 5
1. В качестве базовой переменной можно выбрать x7.
2. В качестве базовой переменной можно выбрать x8.
3. В качестве базовой переменной можно выбрать x9.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (7,8,9).
Выразим базисные переменные через остальные:
x7 = -6x1-7x2-9x3-3x4-7x5-4x6+10
x8 = -x1-4x2-2x3-8x4-6x5-4x6+12
x9 = -5x1-6x2-9x3-x4-5x5-6x6+5
Подставим их в целевую функцию:
F(X) = 9x1+4x2+2x3+4x4+9x5+6x6
6x1+7x2+9x3+3x4+7x5+4x6+x7=10
x1+4x2+2x3+8x4+6x5+4x6+x8=12
5x1+6x2+9x3+x4+5x5+6x6+x9=5
Решим систему уравнений относительно базисных переменных: x7, x8, x9
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,0,0,0,10,12,5)
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x7 10 6 7 9 3 7 4 1 0 0
x8 12 1 4 2 8 6 4 0 1 0
x9 5 5 6 9 1 5 6 0 0 1
F(X0) 0 -9 -4 -2 -4 -9 -6 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai5
и из них выберем наименьшее:
min (10/7 , 12/6 , 5/5 ) = 1
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9 min
x7 10 6 7 9 3 7 4 1 0 0 10/7
x8 12 1 4 2 8 6 4 0 1 0 2
x9 5 5 6 9 1 5 6 0 0 1 1
F(X1) 0 -9 -4 -2 -4 -9 -6 0 0 0 0
Вместо переменной x9 в план 1 войдет переменная x5.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x7 3 -1 -7/5 -18/5 8/5 0 -22/5 1 0 -7/5
x8 6 -5 -16/5 -44/5 34/5 0 -16/5 0 1 -6/5
x5 1 1 6/5 9/5 1/5 1 6/5 0 0 1/5
F(X1) 9 0 34/5 71/5 -11/5 0 24/5 0 0 9/5
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.
Разрешающий элемент равен (64/5) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9 min
x7 3 -1 -7/5 -18/5 8/5 0 -22/5 1 0 -7/5 15/8
x8 6 -5 -16/5 -44/5 34/5 0 -16/5 0 1 -6/5 15/17
x5 1 1 6/5 9/5 1/5 1 6/5 0 0 1/5 5
F(X2) 9 0 34/5 71/5 -11/5 0 24/5 0 0 9/5 0
Вместо переменной x8 в план 2 войдет переменная x4.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x7 27/17 3/17 -11/17 -26/17 0 0 -62/17 1 -4/17 -19/17
x4 15/17 -25/34 -8/17 -22/17 1 0 -8/17 0 5/34 -3/17
x5 14/17 39/34 22/17 35/17 0 1 22/17 0 -1/34 4/17
F(X2) 186/17 -55/34 98/17 193/17 0 0 64/17 0 11/34 24/17
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю . 3-ая строка является ведущей. Разрешающий элемент равен (15/34) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9 min
x7 27/17 3/17 -11/17 -26/17 0 0 -62/17 1 -4/17 -19/17 9
x4 15/17 -25/34 -8/17 -22/17 1 0 -8/17 0 5/34 -3/17 -
x5 14/17 39/34 22/17 35/17 0 1 22/17 0 -1/34 4/17 28/39
F(X3) 186/17 -55/34 98/17 193/17 0 0 64/17 0 11/34 24/17 0
Вместо переменной x5 в план 3 войдет переменная x1.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x7 19/13 0 -11/13 -24/13 0 -2/13 -50/13 1 -3/13 -15/13
x4 55/39 0 14/39 1/39 1 25/39 14/39 0 5/39 -1/39
x1 28/39 1 44/39 70/39 0 34/39 44/39 0 -1/39 8/39
F(X3) 472/39 0 296/39 556/39 0 55/39 218/39 0 11/39 68/39
Индексная строка не содержит отрицательных элементов - найден оптимальный план
Оптимальный план можно записать так:
x1 = 28/39, x2 = 0, x3 = 0, x4 = 116/39, x5 = 0, x6 = 0, x7 = 16/13, x8 = 0, x9 = 0
F(X) = 9*28/39 + 4*0 + 2*0 + 4*116/39 + 9*0 + 6*0 = 124/39
Окончательный вариант системы уравнений:
F = 12.1-7.59x2-14.26x3-1.41x5-5.59x6-0.28x8-1.74x9
x7 = 1.46+0.85x2+1.85x3+0.15x5+3.85x6+0.23x8+1.15x9
x4 = 1.41-0.36x2-0.0256x3-0.64x5-0.36x6-0.13x8+0.0256x9
x1 = 0.72-1.13x2-1.79x3-0.87x5-1.13x6+0.0256x8-0.21x9
Оптимальный план можно записать так:
x1 = 0.718, x2 = 0, x3 = 0, x4 = 1.41, x5 = 0, x6 = 0
F(X) = 9•0.718 + 4•0 + 2•0 + 4•1.41 + 9•0 + 6•0 = 12.103
Таким образом, очередная база равна B2 = <7, 4, 1>. Небазисные переменные следующие: N2 = <5, 2, 3, 6, 8, 9>
4. Предположим, что коэффициент при x2 получает положительное приращение δ, т.е. становится равным 4+δ.
9x1+4+δx2+2x3+4x4+9x5+6x6=0
При выполнении каждой итерации симплексного алгоритма мы прибавляли к строке целевой функции одну из остальных строк, предварительно умножив последнюю на некоторую константу. Следовательно, на заключительной итерации строка целевой функции системы уравнений (F) запишется в виде:
F-72339-δx2-141039x3-52339x6-12439=0
Если δ>72339 , то коэффициент при x2 примет отрицательное значение. В этом случае прежнее решение уже не является оптимальным, так как в базис следует включить x2.
Аналогично для небазисных переменных:
3: δ>141039
5: δ>1,41
6: δ>52339
8: δ>0,28
9: δ>1,74
Переменные х8 и х9 являются дополнительно введенными.
- Определим, в каких пределах могут меняться коэффициенты для базисных переменных в выражении для целевой функции, не нарушая оптимальности прежнего базиса.
F = 12.1-7.59x2-14.26x3-1.41x5-5.59x6-0.28x8-1.74x9
x7 = 1.46+0.85x2+1.85x3+0.15x5+3.85x6+0.23x8+1.15x9
x4 = 1.41-0.36x2-0.0256x3-0.64x5-0.36x6-0.13x8+0.0256x9
x1 = 0.72-1.13x2-1.79x3-0.87x5-1.13x6+0.0256x8-0.21x9
Для переменной х1:
F-δx1-72339-δx2-141039x3-52339x6-12439=0
Так как считаем, что x1 по-прежнему входит в базис, необходимо исключить x1 из строки F. Для этого умножим строку 1 на δ и прибавим к строке 0. В результате строка 0:
F+-29639-δ539x2+55639-δ3139x3+21839-δ539x6=12439-δ2839
Отсюда следует, что при выполнении условия 556/31≤ δ полученное решение остается оптимальным. δ>556/31 − коэффициент при x3 принимает отрицательное значение