Решение задачи линейного программирования

Симплекс-методом

Существо симплекс-метода состоит в следующем. Прежде всего, находится допустимое базис­ное решение. Его можно найти, приняв из числа п переменных какие-либо п—m переменных за свободные, приравняв их нулю и решив получившуюся систему уравнений. Если при этом некоторые из базисных переменных окажутся отрица­тельными, то нужно выбрать другие свободные перемен­ные, т е перейти к новому базису.

Каждое базисное реше­ние, проверяется, на достижение минимума целевой функции.Если минимум не достигут, то ищут новое допустимое базисное решение, но не любое, а такое, которое уменьшает зна­чение целевой функции.Затем процедура повторяется.

Решение линейной задачи симплекс-методом ведется в следующей последовательности.

1. Из вектора переменных размерностью n выбирают переменные, число которых равное числу уравнений ограничений m, их принимают за однозначно определенные (базисные) переменные. Остальные (n-m) переменных принимают за свободные и приравнивают их нулю.

2. Базисные переменные, исходя из уравнений ограничений, выражают через свободные переменные в виде линейной комбинации

.

После преобразования составляется каноническая форма записи модели, из которой определяются хi. Эту запись иногда называют симплекс-планом или опорным планом. Модель записывается в виде следующей системы уравнений:

.

Для того чтобы проверить отвечает ли составленная система поставленной цели (определение оптимальных значений хi), необходимо полученные значения базовых переменных подставить в целевую функцию

,

где - значение целевой функции, определяемое свободными членами , и проанализировать полученную целевую функцию. Если в целевой функции все коэффициенты , то опорный план оптимальный. Следовательно, оптимальное решение запишется в виде:

Если в целевой функции некоторые коэффициенты <0, то план не оптимален. Необходимо строить новый план. Для этого по симплекс-методу одну из свободных переменных (ту, у которой ) необходимо перевести в разряд базовых, а одну из базисных переменных перевести в разряд свободных и составить новый опорный план. Далее процедуру повторяют. Смену переменных выполняют следующим образом. В разряд базисных переводят ту свободную переменную, у которой больше абсолютное значение коэффициента. Затем в выше рассмотренном опорном плане проверяется, какая из базисных переменных при увеличении выбранной свободной переменной быстрее устремляется к нулю. Эту переменную переводят в разряд свободных.

Рассмотрим пример составления и решения линейной задачи симплекс-методом.

Пример 1. Пусть имеется следующая задача.

Цех выпускает валы и втулки. На производство 1 вала рабочий тратит 3 часа, а на производство 1 втулки - 2 часа. От реализации вала предприятие получает прибыль 800 руб., от реализации втулки - 600 руб. Цех должен выпустить не менее 100 валов и не менее 200 втулок. Сколько валов и втулок должен выпустить цех, чтобы получить наибольшую прибыль, если фонд рабочего времени составляет 900 человек - часов?

В качестве переменных (параметров) выбираем: - число валов, - число втулок. Затраты на выпуск 1 вала обозначим =3 час/вал, на выпуск 1 втулки - =2 час/втулка. Прибыль от реализации 1 вала =800 руб./вал, от реализации 1 втулки - =600 руб./втулка. Ресурсы рабочего времени =900 человек - часов. Условия по выпуску валов и втулок: , .

Таким образом, задача запишется в виде:

- множества параметров ;

- ограничения

- целевой функции .

Систему неравенств сведем к системе равенств:

где х3 – недоиспользованный фонд рабочего времени,

х4, х5 – дополнительно выпущенные соответственно, валы и втулки.

Итак, для задачи, рассмотренной выше, запишем:

- целевую функцию (критерий эффективности)

;

- ограничения (область определения)

где - неиспользуемый ресурс времени, - дополнительно выпускаемые валы, - дополнительно выпускаемые втулки.

В рассматриваемом примере число неизвестных n=5, число уравнений m=3.

Решение: 1.Переменные х4, х5 принимаем за свободные. В качестве базовых переменных, выраженных через свободные, возьмем х1, х2, х3. Составим опорный план:

Коэффициенты при х4, х5 отрицательные, следовательно, опорный план не оптимален. Переходим к построению нового опорного плана.

2. Из целевой функции видно, что в разряд базисных целесообразно перевести переменную х4, а х5 оставить свободной. Из числа базисных переменных в разряд свободных целесообразно перевести х3. Тогда новый опорный план будет иметь вид:

Из целевой функции видно, что коэффициент при х5 отрицательный, следовательно, план не оптимален. Переходим к составлению нового опорного плана.

3. Из разряда свободных переменных х5 переводим в базисные, а из базисных переменных х4 переводим в свободные. Составим опорный план вида:

Из целевой функции видно, что опорный план оптимальный. Следовательно, х1=100, х2=300, х3=0, х4=0, х5=100 и в соответствии с поставленной задачей необходимо выпустить 100 шт. валов и 400 шт. втулок. При этом будут использованы все ресурсы, а прибыль составит 260 тысяч рублей.

Пример 2. Решим задачу ранее рассмотренного примера 3 (раскрой материала).

По условию задачи имеем:

- вектор переменных х=(х1, х2, х3, х4);

- ограничение:

3х1+2х2+х3=800,

х1+6х2+9х3+13х4=400;

- целевую функцию

q(x)=12х1+2х2+4х3.

Решение. Так как n=4, m=2, принимаем х3=0, х4=0.

Опорный план запишем в виде:

х1=250+0,87х3+1,62х4 ,

х2=25 - 1,64х3 - 2,43х4 ,

q(x)=3050+7,2х3+14,6х4 .

Решение найдено: число листов, раскроенных 1-м способом х1=250 шт, вторым способом х2=25 шт., третьим и четвёртым способом листы не раскраивались х3=0, х4=0.

При этом минимальные отходы q(х)=3050 м2.