Курсовая работа: Решение задач линейного программирования симплекс-методом

Рассмотрим алгоритм перехода к следующим симплекс-таблицам:

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

Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае – это -8. Из этого следует, что столбец х2 становится ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из полученных делений выбираем минимальное, у нас это будет 25. То есть строка, в которой получилось минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.

Страницы: 1, 2, 3, 4