Автор работы: Пользователь скрыл имя, 16 Декабря 2013 в 21:10, лабораторная работа
Полностью целочисленная задача линейного программирования с двумя переменными и теремя ограничениями (без учета не отрицательности и целочисленности переменных). Решить задачу методом отсечений аналитическим и графическим способом, построив на графике соответствующие отсечения. Решить исходную задачу графически, указав в ОДР все целочисленные точки и построив линию уровня. Осуществить промежуточную и итоговую проверку через «Поиск решения» в Excel.
Оптимальный план можно записать так:
х1 =16/7
x2 =12/7
x4 =43/7
F(X)=3•16/7 +1•12/7 =66/7
В полученном оптимальном плане присутствуют дробные числа.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 6/7, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5 - q16•x6≤0
q1 = b1 - [b1] = 16/7 - 1 = 6/7
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 1/7 - 0 = 1/7
q14 = a14 - [a14] = 0 - 0 = 0 q15 = a15 - [a15] = 2/7 - 0 = 2/7 q16 = a16 - [a16] = 0 - 0 = 0
Дополнительное ограничение имеет вид:
6/7-1/7x3-2/7x5≤0
Преобразуем полученное неравенство в уравнение:
6/7-1/7x3-2/7x5+ x7 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
0 |
x1 |
16/7 |
1 |
0 |
1 /7 |
0 |
2 /7 |
0 |
0 |
x2 |
12/7 |
0 |
1 |
-2 /7 |
0 |
3 /7 |
0 |
0 | |
x4 |
43/7 |
0 |
0 |
-3 /7 |
1 |
31/7 |
-1 |
0 | |
x7 |
-6 /7 |
0 |
0 |
-1 /7 |
0 |
-2 /7 |
0 |
1 | |
Индексная строка |
F(X0) |
-10M |
-3-5M |
-1-4M |
0 |
1M |
0 |
0 |
0 |
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 4-ая строка, а
переменную x7 следует вывести из базиса.
В строку θ заносим следующие величины:
[ - ; - ;1/7:-1/7; - ;12/7:-2/7; - ; - ;] = [ - ; -;-1; - ;-41/2; - ; - ;]
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих
строки и столбца находится
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
|
16/7-(-6/7 •1/7):-1/7 |
1-(0 •1/7):-1/7 |
0-(0 •1/7):-1/7 |
1 /7-(-1/7 •1/7):-1/7 |
0-(0 •1/7):-1/7 |
2 /7-(-2/7 • 1/7):-1/7 |
0-(0 • 1/7):-1/7 |
0-(1 • 1/7):-1/7 |
|
12/7-(-6/7 •-2/7):-1/7 |
0-(0 •-2/7):-1/7 |
1-(0 •-2/7):-1/7 |
-2 /7-(-1/7 •-2/7):-1/7 |
0-(0 •-2/7):-1/7 |
3 /7-(-2/7 •-2/7):-1/7 |
0-(0 • -2/7):-1/7 |
0-(1 •-2/7):-1/7 |
|
43/7-(-6/7 •-3/7):-1/7 |
0-(0 •-3/7):-1/7 |
0-(0 •-3/7):-1/7 |
-3 /7-(-1/7 •-3/7):-1/7 |
1-(0 •-3/7):-1/7 |
31/7-(-2/7 •-3/7):-1/7 |
-1-(0 • -3/7):-1/7 |
0-(1 •-3/7):-1/7 |
|
-6 /7 : -1/7 |
0 : -1/7 |
0 : -1/7 |
-1 /7 : -1/7 |
0 : -1/7 |
-2 /7 : -1/7 |
0 : -1/7 |
1 : -1/7 |
|
66/7-(-6/7 •1/7):-1/7 |
0-(0 •1/7):-1/7 |
0-(0 •1/7):-1/7 |
1 /7-(-1/7 •1/7):-1/7 |
0-(0 •1/7):-1/7 |
12/7-(-2/7 •1/7):-1/7 |
10000-(0 •1/7):-1/7 |
0-(1 • 1/7):-1/7 |
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
0 |
x1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
x2 |
3 |
0 |
1 |
0 |
0 |
1 |
0 |
-2 | |
x4 |
7 |
0 |
0 |
0 |
1 |
4 |
-1 |
-3 | |
x3 |
6 |
0 |
0 |
1 |
0 |
2 |
0 |
-7 | |
Индексная строка |
F(X0) |
-10M |
-3-5M |
-1-4M |
0 |
1M |
0 |
0 |
0 |
Решение получилось целочисленным.
Нет необходимости применять ме
Оптимальный целочисленный план можно записать так:
x1 =1
x2 =3
x4 =7
x3 =6
F(X) = 6
Информация о работе Лабораторная работа по "Экономико-математическому моделированию"