Решение задач линейного программирования симплекс-методом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
м программировании.
1.2 Решение задач линейного программирования симплекс-методом
Задача ЛП в общем виде может быть записана так:
(c, x) ? max
Ax = b,
где c =(c1,c2,...,cn)T мерный вектор-столбец коэффициентов; x =(x1,x2,...,xn)T мерный вектор-столбец неизвестных; A =(aij),m n матрица коэффициентов; B =(b1,b2,...,bm) вектор-столбец коэффициентов.
В этом случае мы имеем дело с неотрицательными решениями системы уравнений.
Любая задача линейного программирования с помощью элементарных преобразований может быть приведена к каноническому виду.
F(x)=c1x1+c2x2+...+cnxn ->max(min)
a11x1+a12x2+...+a1nxn +х n +1 = b1
a21x1+a22x2+...+a2nxn+х n +2 = b2 (3)
.......................
am1x1+am2x2+...+amnxn+х n +т = bm
xi?0 (i=1..n),
где F(x) целевая функция; х1, х2,…, хn базисные переменные; остальные переменные называются свободными.
Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам.
Таблица 1 Система ограничений и целевая функция
Базисные переменныеСвободные членыX 1X 2…X nX n+1X n+2…Xn+mX n+1b1a 11a 12…a 1n10…0X n+2b2a 21a 22…a 2n01…0…………………………X n+mb ma m1a m2…a mn00…1F(x)0-c1-c2…-cn00…0
Рассмотрим алгоритм перехода к следующим симплекс-таблицам:
1. Выбираем ключевой столбец. Это столбец соответствующий минимально отрицательному (максимально положительному) элементу последней (индексной) строке:
Если отрицательных элементов в индексной строке нет, то план оптимальный.
2. В ключевом столбце выбираются положительные коэффициенты, если таких нет, то задача не имеет решений;
3. Выбираем ключевую строку:
Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответствующего свободного члена к этому элементу минимальна.
Ключевой элемент это элемент, стоящий на пересечении ключевого столбца и ключевой строки;
4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;
5. В новой таблице:
5.1 Все элементы ключевой строки делятся на ключевой элемент.
5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.
5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.
5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.
5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.
6. Переход к шагу 1.
Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.
2. Постановка задачи
Для изготовления изделий двух видов склад может отпустить металла не более 150 кг, причем на изделие первого вида расходуется пять килограмм, а на изделие второго вида три килограмма. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий первого вида требуется изготовить не более 20 штук, а изделий второго вида не более 25 штук, причем одно изделие первого вида стоит 7 руб., а изделие второго вида стоит 8 руб.
3. Решение поставленной задачи
x1 количество изделий первого вида.
x2 количество изделий второго вида.
F(x) целевая функция.
5x1 + 3x2 =150
x1 20
x2 25
x1, x2?0
F(x) = 7x1 +8x2 max
Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:
5x1 + 3x2+x3 =150
x1+x4=20
x2+x5 =25
x1, x2, x3, x4, x5?0
F(x)= 7x1 +8x2 +x3 +x4 +x5
x3, x4, x5 базисные переменные; x1, x2 свободные переменные.
Составим симплекс таблицу, соответствующую каноническому виду:
Таблица 2 Итерация 1
БазисСвободные чл.X 1X 2X 3X 4X 5X 315053100X 42010010X 52501001F(x)0-7-8000
Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае это -8. Из этого следует, что столбец х2 становится ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из полученных делений выбираем минимальное, у нас это будет 25. То есть строка, в которой получилось минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.
Строим новую таблицу, следуя алгоритму, приведенному выше.
Таблица 3 Итерация 2
БазисСвободныеX 1X 2X 3X 4X 5X 3755010-3X 42010010X 22501001F(x)200-70008
Таблицу 3 проверяем на оптимальность таким же способом, что и изначальную таблицу. Находим ключевой элемент в таблице 3, и затем заново пересчитываем новую таблицу.
Таблица 4 Итерация 3
БазисСвободныеX 1X 2X 3X 4X 5X 115100,20-0,6X 4500-0,210,6X 22501001F(x)305001,403,8
В нашем случае таблица 4 стала окончательным решением, так как в последней строке нет отрицательных чисел, из этого следует, что мы нашли оптимальный способ решение поставленной задачи.
X 1=15; X 2=25; Fmax=305.
Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день.
4. Алгоритм программы
Блок-схема симплекс-метода
Вычислительная процед?/p>