Курсовая работа: Решение задач линейного программирования симплекс методом
2) Столбец, содержащий наибольший положительный элемент в строке решения.
3) Если столбец удовлетворяет условию max(Cj min bj /aij ) при решении на max, и m in (Cj min bj /aij ) при решении задач на min.
Cj – коэффициент целевой функции в столбце j, aij – коэффициент в столбце j и строке i.
Решение задачи
Определим максимальное значение целевой функции F(X) = 3500 x1 +3200 x2 +1500 x3 при следующих условиях ограничений.
4 x1 + 2 x2 + 5 x3 <=190
5 x1 + 3 x2 + 4 x3 <=320
7 x1 + 9 x2 + 5 x3 <=454
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
4x1 + 2x2 + 5x3 + 1x4 + 0x5 + 0x6 = 190
5x1 + 3x2 + 4x3 + 0x4 + 1x5 + 0x6 = 320
7x1 + 9x2 + 5x3 + 0x4 + 0x5 + 1x6 = 454
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4 , x5 , x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,190,320,454)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.
| X1 | X2 | X3 | X4 | X5 | X6 | св. чл. |
| 4 | 2 | 5 | 1 | 0 | 0 | 190 |
| 5 | 3 | 4 | 0 | 1 | 0 | 320 |
| 7 | 9 | 5 | 0 | 0 | 1 | 454 |
| -3500 | -3200 | -1500 | 0 | 0 | 0 | 0 |
Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1 , так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x1
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.