Федеральное агентство
Государственное образовательное учреждение
высшего профессионального образования
"Воронежская государственная лесотехническая академия"
"Методы оптимизации в расчетах на ЭВМ"
Симплексный метод
Методические указания и задания для студентов 3 курса специальности
150200(190601) – Автомобили и автомобильное хозяйство
Воронеж 2007
УДК 519.8
Котко, Л.А. Симплексный метод. Методические указания и задания для студентов 3 курса специальности 150200(190601) – Автомобили и автомобильное хозяйство / Л.А. Котко, Т.М.Кравец ; Фед. агентство по образованию, ГОУ ВПО "ВГЛТА". – Воронеж, 2007. – 72 с.
Печатается по решению редакционно-издательского совета ГОУ ВПО "ВГЛТА"
Рецензент канд.физ.-мат.наук, доц.кафедры Теории вероятностей и уравнений в частных производных И.В. Михайлова
Симплексный метод решения канонической задачи линейного программирования
Управление экономикой становится все более трудной задачей из-за чрезвычайно большого числа производственных решений. В связи с этим особое значение приобретают научные методы отыскания оптимальных решений, дающих больший эффект при меньших затратах.
Один из наиболее развитых и широко применяемых методов нахождения оптимальных решений изучается в линейном программировании.
Стандартная задача линейного программирования. Стандартная задача линейного программирования состоит в следующем: найти максимум линейной функции
F (X) = c1x1 + c2x2 + ... + cnxn |
(1) |
для переменных x1, x2, ..., xn, удовлетворяющих системе ограничений - неравенств
anx1 + a12x2 + ... + a1nxn ≤ b1,
a21x1 + a22x2 + ... + a2nxn ≤ b2,
. . . . . . . . . . . . . . .
am1 x1 + am2 x2 + ... + amnxn ≤ bm
иусловиям неотрицательности
x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0.
(2)
(3)
Если стандартная задача ставится на минимум линейной функции (1), то знаки всех ограничений-неравенств берутся противоположными:
a11x1 + a12x2 + ... + a1nxn ≥ b1,
a21x1 + a22x2 + ... + a2nxn ≥ b2, (4)
. . . . . . . . . . . . . . .
am1 x1 + am2 x2 + ... + amnxn ≥ bm
Условия (3) остаются теми же.
Примеры стандартных задач линейного программирования
I. Задача о составлении производственного плана при ограниченных ресурсах
Имеется производство, которое выпускает различные виды продукции A1, ..., An. Для изготовления продукции необходимы ресурсы S1, ..., Sm. Обозначим через aij количество ресурса Si, необходимое для производства единицы продукции вида Aj i 1, ..., m, j 1, ...n. Производство обладает ограниченными ресурсами. Пусть bi− запас ресурса Si. От реализации единицы продукции Aj производство получает прибыль cj. Требуется составить производственный план так, чтобы он давал максимальную прибыль. Данные задачи представлены в таблице 1.
Таблица 1
Виды ресурсов |
Запасы ресурсов |
|
Виды продукции |
||
|
|
|
|
|
|
|
|
A1 |
|
. . . . |
An |
S1 |
b1 |
a11 |
|
. . . . |
a1n |
. . . . |
. . . . |
. . . . |
. . . . |
|
|
Sm |
bm |
am1 |
|
amn |
|
Прибыль |
c1 |
|
. . . . |
cn |
|
Обозначим через xj количество продукции Aj, которое нужно выпустить по плану. От реализации этой продукции получится прибыль cjxj. Реализация всей плановой продукции обеспечит прибыль
F (X) = c1x1 + ... + cnxn.
Конечно, прибыль тем больше, чем больше xj, но беспредельно увеличивать план нам не позволяют ограниченные ресурсы. Действительно, количество ресурса Si, которое потребуется для производства плановой продукции, будет равно ai1x1+...+ainxn и не должно превзойти имеющийся запас bi этого ресурса. Это приводит к ограничениям
a11x1 + a1nxn ≤ b1,
. . . . . . . . . . . . . . .
am1x1 + amnxn ≤ bm.
Кроме того, конечно, x1 ≥ 0, ..., xn ≥ 0.
Таким образом, мы пришли к стандартной задаче линейного программирования типа (1)-(3).
II. Задача о раскрое
На мебельном комбинате из ДСП делают различные заготовки D1, ..., Dm. Имеются различные способы раскроя плит A1, ...An. Через aaij обозначим количество заготовок Di, получаемых из одной плиты при способе раскроя
Aj,
i 1, ..., m, j 1, ....n.
Согласно плановому заданию нужно произвести bi заготовок вида Di. При производстве заготовок остаются отходы: при раскрое плиты по способу Aj получаются отходы площадью cj. Требуется обеспечить выполнение плана с минимальным количеством отходов. Данные задачи представлены в таблице 2.
|
|
|
Таблица 2 |
|
|
Виды заготовок |
План производства |
Способы раскроя |
|||
|
|
|
|
|
|
|
|
A1 |
|
. . . . |
An |
D1 |
b1 |
a11 |
|
. . . . |
a1n |
. . . . |
. . . . |
. . . . |
|
. . . . |
. . . |
Dm |
bm |
am1 |
|
amn |
|
Отходы |
c1 |
|
. . . . |
cn |
|
Обозначим через xj количество плит, которые предполагается раскраивать по способу Aj. Тогда общее количество отходов
F (X) = c1x1 + ... + cnxn.
Количество заготовок вида Di, которое будет произведено, равно ai1x1+
... + ainxn. Оно должно быть не менее планового задания bi. Таким образом получаются ограничения
a11x1 + ... + a1nxn ≥ b1,
. . . . . . . . . . . . . . .
am1x1 + ... + amnxn ≥ bm.
Кроме того,
x1 ≥ 0, ..., xn ≥ 0.
Итак, мы пришли к стандартной задаче линейного программирования типа (1), (3), (4).
Перейдем теперь к изучению симплексного метода, позволяющего решить поставленные задачи. Для этого нам понадобятся дополнительные сведения из линейной алгебры.
III. Метод Гаусса-Жордана. Базисные системы неизвестных
В дальнейшем будем рассматривать системы линейных уравнений
a11x1 + a12x2 + ... + a1nxn = b1,
a21x1 + a22x2 + ... + a2nxn = b2, (5)
. . . . . . . . . . . . . . .
am1x1 + am2x2 + ... + amnxn = bm,
укоторых число неизвестных больше числа уравнений (n > m). Система из m неизвестных xi называется базисной, если определитель
матрицы, составленной из коэффициентов при этих неизвестных, отличен от нуля. Если выбрана базисная система неизвестных, то остальные неизвестные называются свободными. Мы будем предполагать, что для