4. Новые коэффициенты, не стоящие в строке и столбце разрешающего элемента (
), равны частному от деления разности произведения коэффициентов главной и побочной диагонали на разрешающий элемент.
Например, чтобы найти новый коэффициент вместо а/40 = 12, строим прямоугольник, главная диагональ которого составлена коэффициентом а/40= 12 и разрешающим элементом а/31, а побочная – а/30 и а/41 (рис. 3.11).
а/30 а/31
а/40 а/41
Рис. 3.11
Тогда
Аналогично определяем новый коэффициент вместо 
= 0. Прямоугольник для него включает , 
, 
, 
.
В табл. 3.11 опорное решение отсутствует, так как три свободных члена имеют отрицательные значения.
По изложенным выше правилам ищем разрешающий элемент в строке отрицательного свободного члена у5. Этим элементом будет 
= –1, так как при делении свободных членов на соответствующие коэффициенты столбца х2 наименьшее положительное частное получено при делении на коэффициент .
По данным правилам делаем преобразования, т. е. находим новые коэффициенты симплексной таблицы № 2. При этом базисную переменную у5 поменяем местами с небазисной основной переменной х2. Таким образом, получаем симплексную таблицу № 3 (табл. 3.12).
В столбце х2 табл. 3.11 все коэффициенты имеют отрицательные знаки. И этим коэффициентам в столбце свободных членов соответствуют отрицательные значения. В данном случае в качестве разрешающего элемента можно взять коэффициент, от деления на который получили наибольшее положительное частное. При подобном подходе опорное решение получается быстрее, но поскольку такие ситуации бывают нечасто, то его нахождение продолжаем обычным способом.
Т а б л и ц а 3.12. Симплексная таблица № 3
Базисные переменные | Свободные члены, | Небазисные переменные | |||
y3 | y5 | y3 | y4 | ||
y1 | -17,6 | -1,2 |
| -0,3 | -0,2 |
y2 | -1,76 | -0,13 | -0,05 | -0,033 | -0,02 |
x1 | 7 | -1 | 0 | 0 | 0 |
y4 | 5 | 1 | 0 | 0 | 0 |
x2 | 10 | 0 | -1 | 0 | 0 |
y6 | 40 | 0 | 0 | 1 | 0 |
y7 | 60 | 0 | 0 | 0 | 1 |
F | 126,0 | -12,0 | -4,2 | -2,4 | -1,2 |
Так как в табл. 3.12 опорное решение отсутствует, то продолжаем его поиск.
Выбираем любой из двух оставшихся отрицательных свободных членов. Например, –17,6. Первый отрицательный коэффициент в его строке 
= –1,2 не является разрешающим, так как от деления на него меньшее положительное частное не получается. Проверка показывает, что 
= –0,5. Коэффициент является разрешающим. При этом в равной мере разрешающим может быть также и коэффициент во второй строке (
= –0, 05 ) , так как полученные частные одинаковы:
Заменяем небазисную переменную у5 базисной у1 и делаем преобразования (табл. 3.13).
Т а б л и ц а 3.13. Симплексная таблица № 4
Базисные переменные | Свободные члены,
| Небазисные переменные | |||
y3 | y1 | х3 | x4 | ||
y5 | 35,2 | 2,4 | -2,0 | 0,6 | 0,4 |
y2 | 0,000 | -0,010 | -0,100 | -0,033 | 0,000 |
x1 | 7 | -1 | 0 | 0 | 0 |
y4 | 5 | 1 | 0 | 0 | 0 |
x2 | 45,2 | 2,4 | -2,0 | 0,6 | 0,4 |
y6 | 40 | 0 | 0 | 1 | 0 |
у7 | 60 | 0 | 0 | 0 |
|
F | 272,54 | -1,92 | -8,40 | 0,12 | 0,48 |
Итак, опорное решение (план) получено при следующих значениях основных переменных: x1 =7,0; х2=45,2; дополнительных – у5 = 35,2; y2 = 0; у4 = 5; у6 = 40; у7 = 60 и F = 272,54 у. е.
Таким образом, после подстановки значений x1 и х2 в систему неравенств (3.6) все условия будут выполнены.
Поиск оптимального решения. Опорное решение является оптимальным, если коэффициенты целевой функции F-строки будут отрицательными (или нулевыми) при поиске минимума или положительными (или нулевыми) при поиске максимума (за исключением свободного члена F-строки). В данном случае оптимальное решение (минимум функции) отсутствует, так как здесь имеются положительные коэффициенты.
Поиск оптимального решения начинается с определения разрешающего столбца. Разрешающим столбцом при поиске минимума функции будет являться тот, в строке целевой функции которого находится наибольший положительный коэффициент, а при поиске максимума функции – наибольший по абсолютной величине отрицательный коэффициент.
В данном случае в F-строке для переменной х4 имеется наибольший положительный коэффициент (0,48). Следовательно, столбец х4 является разрешающим. Чтобы найти разрешающий элемент, делим столбец свободных членов на соответствующие коэффициенты разрешающего столбца. Разрешающим будет элемент, от деления на который получается меньшее положительное частное. В данном случае таковым будет 
= 1 , так как
Меняем местами переменные х4 и у7 и определяем по изложенным выше правилам новые коэффициенты (табл. 3.14).
Т а б л и ц а 3.14. Симплексная таблица № 5
Базисные переменные | Свободные члены, | Небазисные переменные | |||
y3 | y1 |
| у7 | ||
y5 | 11,2 | 2,4 | -2,0 | -0,4 | |
y2 | 0,00 | -0,01 | -0,10 | -0,03 | 0,00 |
x1 | 7 | -1 | 0 | 0 | 0 |
y4 | 5 | 1 | 0 | 0 | 0 |
х2 | 21,2 | 2,4 | -2,0 | 0,6 | -0,4 |
y6 | 40,00 | -4,00 | 3,30 | 1,00 | 0,66 |
Х4 | 60 | 0 | 0 | 0 | 1 |
F | 243,74 | -1,92 | -8,40 | 0,12 | -0,48 |
х3Оптимальное решение здесь отсутствует, так как в F-строке столбца х3 имеется положительный коэффициент. Этот столбец будет разрешающим. По отношению значений столбца свободных членов и соответствующих коэффициентов столбца x3 определяем, что разрешающим будет коэффициент 
= 0,6 .
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
Основные порталы (построено редакторами)