Алгоритм решения задачи 1 ЛП (линейного программирования симплекс-методом)

Задача №1

Предприятие выпускает продукцию трех видов. На изготовление каждого i-ого вида продукции затрачивается три различных видов ресурсов (j): энергетические, финансовые и сырьевые.Причем на каждый вид продукции затрачивается разное количество каждого ресурса (a_ji). Прибыль от реализации каждого i-ого изделия различна (z_i). Определить максимальную прибыль предприятия исходя из условий ограниченности каждого вида ресурса (b_j) и принимая во внимание тот факт, что предприятие должно выпустить минимальное количество всех видов изделий (b₄).

Алгоритм составления математической модели оптимизационной задачи

1) Составление целевой функции.

Так как по условию задачи необходимо найти максимальную прибыль предприятия, то этот экономический критерий необходимо выразить целевой функцией. Так как на предприятии, исходя из условия задачи, выпускается три вида продукции и известна стоимость каждого вида продукции, то обозначив количество выпускаемой продукции каждого вида через x₁, x₂, x₃ и умножив это количество на стоимость каждого вида продукции z₁, z₂, z₃получим прибыль от реализации каждого изделия. При этом сумма прибыли от реализации каждого изделия должна стремиться к максимальному значению. Поэтому целевая функция будет иметь следующий вид:

2) Составление ограничений.

По условию задачи известно, что на каждый вид продукции затрачивается три вида ресурсов. На примере первого ресурса, энергетического, на каждый вид продукции затрачивается a₁₁, a₁₂, a₁₃. Суммарное количество затрат энергетического ресурса на каждый вид продукции составит: единиц энергии. При этом данный вид ресурса ограничен на предприятии количеством b₁. Таким образом, моет быть введено ограничение по энергетическому ресурсу которое выглядит следующим образом:

Аналогично ограничения должны быть составлены для каждогоиз ресурсов.

Исходя из условия об ограничении минимального количества выпускаемой продукции (b₄) должно быть введено дополнительное ограничение имеющее вид:

При составлении ограничений должен быть учтен тот факт, что количество выпускаемой продукции каждого вида не может быть отрицательным.

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

Алгоритм решения задачи 1 ЛП (линейного программирования симплекс-методом)

1. Необходимо выполнить разделение переменных на свободные и базисные. Для этого преобразовать составленную систему ограничений по количеству ресурсов к виду:

2. Записать полученную систему ограничений и целевую функцию в виде таблицы:

3. Записать исходное решение, в котором свободные переменные равны нулю, базисные переменные равны свободным членам ограничений, значение целевой функции равно нулю.

4. Просмотреть столбец b (свободных членов). Если выполняется условие , то решение является допустимым, тогда переходимк п.7 алгоритма. Если есть свободные члены удовлетворяющие условию , то выбирается член с максимальным значением и строка содержащая этот член становится разрешающей.

5. Просмотреть коэффициенты a_jiразрешающей строки. Если все коэффициенты данной строки положительные, то задача не имеет решения. Если среди коэффициентов a_jiразрешающей строки есть отрицательные, то выбирается наибольший из этих коэффициентов и столбец содержащий выбранный коэффициент становится разрешающим.

6. Выполнить пересчет всех коэффициентов таблицы, включая значение целевой функции, которое имеет противоположный знак. Перейти к п.4.

7. Просмотреть коэффициенты z_iстроки целевой функции. Если все коэффициенты удовлетворяют условию ,то текущее решение будет оптимальным. Вычисления заканчиваются.

8. Если в строке целевой функцииесть коэффициенты удовлетворяющие условию , то необходимо выбрать наибольший из них и столбец содержащий этот коэффициент становится разрешающим. Выполняется вычисление отношений свободных членов b_jк положительным коэффициентам a_jiразрешающего столбца. Строка, отвечающая минимальному изэтих отношений будет разрешающей.

9. Выполнить пересчет всех коэффициентов таблицы и перейти к п.7.