![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теоретическое введение. Это алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве
Это алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 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)
|