Теоретическое введение. Это алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве

Это алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.

То есть Симплекс – это понятие геометрическое, означающее совокупность вершин многомерного тела.

Идея симплекс-метода заключается в последовательном переборе решений – в последовательном переходе от одной вершины к другой. Однако этот перебор не хаотичный, а таков, что на каждом шаге решение улучшается.

Задача: Определить максимальную прибыль предприятия, выпускающего продукцию в виде изделий трех видов (i = 1, 2, 3). Для изготовления каждого i-го изделия требуются три вида ресурсов: энергетические, финансовые и сырьевые (j = 1, 2, 3).

Исходные данные:

ü наличие на предприятии каждого j-го ресурса bj;

ü норма расхода j-го ресурса на одно изделие i-го вида aji;

ü прибыль zi от реализации одного i-го изделия;

ü минимальное количество b4 всех видов изделий, которое предприятие должно выпустить.

Решение: Обозначим искомые количества 1-го, 2-го и 3-го видов изделий через х1, х2 и х3.

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

Z = z1x1+ z2x2+ z3x3 → max. (1.1)

Перейдем к составлению ограничений. Поскольку на одно изделие 1-го вида требуется а11 единиц энергии, на искомое количество х1 потребуется а11х1 единиц энергии. Для искомых количеств изделий 2-го и 3-го видов потребуется соответственно а12х2 и а13х3 единиц энергии. Суммарный расход энергии на выпуск трех видов изделий составит а11х1 + а12х2 + а13х3 единиц энергии. Эта величина ограничена наличием на предприятии энергетических ресурсов в количестве b1. Таким образом, ограничение по энергетическим ресурсам будет иметь вид

а11х1+ а12х2 + а13х3 < b1.

Аналогично составляются ограничения по финансовым и сырьевым ресурсам.

Ограничение минимального суммарного количества выпускаемых изделий запишется как

х1+ х2+ х3 > b4.

В итоге, вся система ограничений будет иметь вид

а11х1+ а12х2 + а13х3 < b1,

а21х1+ а22х2 + а23х3 < b2, (1.2)

а31х1+ а32х2 + а33х3 < b3,

х1+ х2+ х3 > b4.

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

xi > 0, i = 1, 2, 3. (1.3)

Выражения (1.1), (1.2) и (1.3) представляют собой математическую модель поставленной оптимизационной задачи.

Выражения (1.2) и (1.3) являются линейно зависимыми от искомых переменных хi, следовательно, рассматриваемая оптимизационная задача относится к классу линейных задач, решаемых методами линейного программирования.

Решаем задачу симплекс-методом при следующих исходных данных:

прибыль от реализации одного изделия 1, 2 и 3 видов:

z1 = 8; z2 = 11; z3 = 12 у.е./изд.;

нормы расхода энергии на одно изделие:

а11 = 2; а12 = 2; а13 = 3 е.э./изд. (единиц энергии/изделие)

нормы расхода финансовых средств на одно изделие:

а21 = 6; а22 = 5, 5; а23 = 4 у.е./изд.

нормы расхода сырья на одно изделие:

а31 = 4; а32 = 6; а33 = 8 е.с./изд. (единиц сырья/изделие)

наличие на предприятии энергетических, финансовых и сырьевых ресурсов:

b1 = 50 е.э.; b2 = 100 у.е.; b3 = 150 е.с.

минимальное количество всех видов изделий, которое предприятие должно выпустить b4= 15 изд.

Решение. В соответствии с выражением (1.5) и исходными данными целевая функция запишется в виде:

Z=8х1+11х2+12х3 → max. (1.4)

С исходными данными система ограничений запишется в виде:

2х1+ 2х2 + 3х3 < 50,

6х1+ 5, 5х2 + 4х3 < 100, (1.5)

4х1+ 6х2 + 8х3 < 150,

x1+ x2+ x3 > 15.

После введения дополнительных переменных х4, х5, х6 и х7 перейдем от ограничений-неравенств к равенствам

2х1+ 2х2 + 3х3 + х4 = 50,

6х1+ 5, 5х2 +4х3 + х5 = 100, (1.6)

4х1+ 6х2 + 8х3 + х6 = 150,

- x1- x2 - x3 + x7 = -15.

Граничные условия неотрицательности переменных имеют вид

x1 > 0, x2 > 0, x3 > 0,

x4 > 0, x5 > 0, x6 > 0, x7 > 0. (1.7)