Задачи линейного программирования и методы их решения

Линейное программирование - раздел математического программирования, изучающий задачу отыскания максимума (минимума) линейной функции при линейных ограничениях в виде равенств или неравенств.

Общая задача линейного программирования формулируется следующим образом: требуется определить максимум (или минимум) линейной функции n переменных x ₁, x ₂,..., x_n [19].

(1.18)

при ограничениях:

где - заданные числа.

К задачам линейного программирования сводится большое количество военных, технических и экономических задач управления и планирования. Общая формулировка этих задач будет такой: дана система m независимых алгебраических уравнений с n > m неизвестными переменными (х ₁, х ₂,..., х_n):

(1.19)

..................

и линейная форма

(1.20)

относительно этих неизвестных.

Требуется среди всех неотрицательных решений заданной системы выбрать такое, при котором (1.20) принимает наибольшее (наименьшее) значение. Эта задача носит название основной задачи линейного программирования (ОЗЛП).

Допустимым решением ОЗЛП называют любую совокупность переменных х ₁³0, х ₂ ³0,..., х_n ³0, удовлетворяющую уравнениям (1.19). Оптимальным решением называют то из допустимых решений, при котором форма (1.20) принимает максимальное (минимальное) значение. Если уравнения (1.19) и (1.20) противоречат друг другу, то ОЗЛП не имеет решения.

Основными методами решения задач ОЗЛП являются:

1) геометрический метод;

2) симплексный метод;

3) венгерский метод;

4) метод потенциалов.

Наиболее показательным методом решения ОЗЛП является геометрический метод, но он трудно реализуем на ЭВМ. Его обычно используют, когда n – m =2 [18].

Идея метода потенциалов заключается в том, что для проверки допустимого плана на оптимальность для каждого столбца и строки определяются числа, которые называются потенциалами. C помощью потенциалов легко вычислить индексы свободных клеток опорного плана.

Венгерский метод является наиболее эффективным методом решения транспортной задачи на ЭВМ. Вычислительные эксперименты, поставленные на ЭВМ, показали, что венгерский метод в 2-4 раза эффективнее метода потенциалов. В основу метода положены теоремы, доказанные венгерскими математиками Д. Кенигом и Е. Эгервари.

Наиболее общим (универсальным) методом решения задач линейного программирования (ЛП) является симплексный метод.

Пусть необходимо решить задачу линейного программирования следующего вида:

(1.21)

.................. (1.22)

Введя дополнительные переменные представим систему неравенств в виде системы равенств:

(1.23)

........................

.

Задача (1.21), (1.23) является ОЗЛП. Разрешив систему уравнений (1.23) относительно переменных получим:

(1.24)

........................

Положив свободные переменные получим базисное допустимое решение так как по условиям задачи b_i ³0. Однако данному базисному решению соответствует L ₀=0, так как базисные переменные входят в целевую функцию с нулевыми коэффициентами.

Найдем новое базисное решение, которому соответствует большее значение целевой функции. В выражении (1.21) выберем свободную переменную x_k с Очевидно, что при c_k >0 увеличе­ние x_k приведет к увеличению целевой функции L. Однако x_k ограничено системой уравнений (1.24), так как при неограниченном увеличении x_k некоторые базисные переменные могут стать отрицательными.

Для определения границы возможного увеличения x_k полагаем все свободные переменные в уравнениях (1.23), кроме x_k, равными нулю.

Тогда получим:

(1.25)

............

Если все коэффициенты a_ik - отрицательные числа, то при всех значениях x_k >0 базисные переменные и величины x_k и L неограничены. Рассмотрим случай, когда среди коэффициентов a_ik имеются положительные. Тогда из уравнений (1.25) находим значение при котором все базисные переменные остаются положительными и переменная Подставив значение в уравнение (1.25) и целевую функцию, получим новое базисное решение:

............

............

Таким образом, мы произвели замену свободной переменной x_k на базисную x_n+l. В новом решении переменная x_n+l - свобод­ная, переменная x_k - базисная.

Из уравнения

находим новую базисную переменную

Подставляя значение x_k в уравнение (1.23) и в целевую функцию (1.21), получим новую систему уравнений для базисных переменных и значение целевой функции, выраженные через новые свободные переменные. На последующих итерациях все операции повторяются. Вычислительный процесс заканчивается, если все коэффициенты - при свободных переменных в целевой функции и увеличение целевой функции за счет увеличения одной из свободных переменных невозможно. В этом случае последнее базисное решение является оптимальным.

При решении задач линейного программирования на минимум вычислительный процесс аналогичен. Особенность состоит в том, что для замены базисной переменной выбирается свободная переменная, которая приводит к уменьшению целевой функции. Вычислительный процесс в этом случае заканчивается, если все коэффициенты при свободных переменных в целевой функции положительны и дальнейшее уменьшение величины L за счет увеличения одной из свободных переменных невозможно. Таким образом, в оптимальном решении все свободные переменные равны нулю, базисные переменные определяются системой уравнений аналогично системе (1.24).

Дата добавления: 2015-07-20