1. Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида:
j=16cjxj→max
j=16cijxj≤bi
xj≥0
где все параметры модели должны быть определены из следующих условий:
2 Придумать оригинальную содержательную постановку задачи, которой соответствует модель из п.1.
3. Найти оптимальное решение модели, сформированной в п.1.
4. Произвести анализ на чувствительность модели, сформированной в п.1.
- Определить, в каких пределах могут меняться коэффициенты при небазисных переменных в выражении для целевой функции, не нарушая оптимальности прежнего базиса.
- То же, но только для базисных переменных.
- Записать систему неравенств, описывающую допустимую в смысле сохранения оптимальности прежнего решения, область одновременных изменений коэффициентов при базисных переменных в выражении для целевой функции. Построить эту область графически.
- Найти пределы, в которых могут меняться константы в правых частях соотношений в п.1, не нарушая оптимальности прежнего решения.
- Пусть в правых частях первых двух ограничений в п.1 константы b1 и b2 могут одновременно быть изменены. Найти систему неравенств, при выполнении которой прежнее решение остается оптимальным. Изобразить допустимую область графически.
5. Двойственная задача. Записать для задачи, сформированной в п.1, двойственную задачу.
6. Найти оптимальное решение двойственной задачи.
Используя двойственную модель определить, в каких интервалах могут меняться коэффициенты при небазисных переменных в выражении для целевой функции, не нарушая оптимальности прежнего решения.
7. Пусть вводятся новые управляемые переменные x10 и x11. Коэффициенты при x10 и x11 записаны в табл.6. Целесообразен ли ввод данных переменных?
На основе содержательной постановки, предложенной согласно п.2, предложить содержательную постановку динамической задачи. Плановый период составляет три единицы времени. Записать соответствующую модель линейного программирования, используя символические (буквенные) обозначения параметров модели.
Решение
Формулируем модель
Данному варианту соответствуют следующие числа:
Таблица 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 принимает отрицательное значение
Задать вопрос
на новый заказ в Автор24.
