COMPARISON OF THE METHOD TO STRUCTURAL OPTIMIZATION AND THE SIMPLEX METHOD
Abstract and keywords
Abstract (English):
This article compares the structural optimization method and the simlex method used in solving linear programming problems. The characteristic of each method is given and the analysis of algorithm of the solution of problems by means of these techniques is carried out. The problem showing advantages of one of the methods is solved.

Keywords:
linear programming (LP), simplex method, structural optimization
Text
Publication text (PDF): Read Download

Каждое предприятие ставит своей целью увеличение прибыли и уменьшение затрат (издержек) на производство. Для достижения намеченной цели в экономике часто используется прогнозирование и планирование затрат и оптимальных объёмов производимой на предприятии продукции.
Решение задач линейного программирования делает возможным повышение эффективности предприятия и увеличение его производительности, а именно:  роста доходов и прибыли или снижения затрат необходимых для изготовления продукции и технологических отходов при её производстве.
Для решения задач ЛП используют большое количество разных методов, в их число входят также метод структурной оптимизации и симплекс-метод. Рассмотрим эти два метода подробнее.
Симплекс-метод можно назвать главным или основным методом решения задач линейного программирования [1, стр. 35]. С помощью симплекс-метода за конечное число шагов можно определить существует ли оптимальное решение, или его нет. Родоначальником симплекс-метода является американский математик Роберт Данциг. Суть (содержание) симплекс-метода можно отразить с помощью следующих трёх пунктов [7, стр. 23]:
    Показать способ, с помощью которого можно найти первоначальный опорный план.
    Показать способ, с помощью которого можно перейти от одного опорного плана к другому, в случае если первый опорный план не оказался оптимальным. 
    Задать критерии, с помощью которых можно вовремя завершить процесс проверки решений на оптимальность или сделать вывод о том, что оптимальное решение не существует. 
Так же для решения задач линейного программирования используется метод структурной оптимизации. Структурная оптимизация — это метод, с помощью которого можно построить такую структуру как способа соединения элементов в систему, которая сможет стать максимально эффективной с точки зрения заранее поставленной практической цели и при заданных и всегда ограниченных ресурсах.
Оба метода используются при решении задач ЛП. Но какой из них является более точным и эффективным? Чтобы понять это, нам необходимо рассмотреть решение задач методом структурной оптимизации и симплекс методом. Для предметного представления результатов исследования решим задачу двумя способами.
Условие. Кондитерская фабрика, занимающаяся производством эксклюзивных тортов, имеет на складе какао, сахар и муку и может производить торты двух видов: торт «Вдохновение» и торт «Чёрный принц». Расход продуктов за один день  и общее количество ресурсов для каждого вида тортов представлены в таблице. 
    «Вдохновение»    «Чёрный принц»    Ресурсы
Сахар, кг    4    6    16
Мука, кг    12    4    20
Какао, кг    4    4    12
 За один день кондитерская может изготовить 5 тортов «Вдохновение» и 4 торта «Чёрный принц». Сколько дней должна работать кондитерская, чтобы при имеющихся ресурсах обеспечить максимальный выпуск тортов.
Решение. 1 способ. Симплекс-метод.
Пусть:
х_1 — время изготовления торта «Вдохновение»;
х_2 — время изготовления торта «Чёрный принц»;
Математическая модель задачи примет следующий вид:
                                F(x)=5x_1+4x_2  →max          (1)
при ограничениях:
                                        {█(〖4x〗_1+ 〖6x〗_(2 )≤16,@12x_1+ 〖4x〗_(2 )≤20,@〖4x〗_1+ 〖4x〗_2≤12,@x_1≥0,x_2≥0.  )┤           (2)
Приведём задачу к каноническому виду:
                                     F(x ̅ )=5x_1+4x_2  →max      (3)
при ограничениях:
                                          {█(4x_1+ 〖6x〗_(2 )+ x_3=16,@      12+ 4x_(2 )+,,,,,,,,x_4=20,@〖            4x〗_1+ 〖4x〗_2+,,,,,,,,,,,x_5=12,@x_J≥0,j= (1,5) ̅.             )┤       (4)
Принимаем x_1, x_2  в качестве свободных переменных,x_3, x_4, x_5 в качестве базисных. Составляем симплекс-таблицу, соответствующую начальному опорному плану.

СП
БП    x_1    x_2    CЧ
x_3    4    6    16
x_4    12    4    20
x_5    4    4    12
F    -5    -4    0

Начальный опорный план имеет вид:
  Х_1=(0,0,16,20,12), F(Х_1)=0.
Рассмотрев последнюю строку таблицы, мы можем заметить, что в ней находятся две отрицательные оценки, это означает, что решение, которое было найдено нами, нельзя назвать оптимальным и его можно улучшить. В качестве ведущего столбца принимаем столбец базисной переменной  x_1 (т.к. именно в этом столбце располагается наибольшее по модулю значение F), а за ведущую строку — строку переменной x_4, где min (16/4,20/12,12/4)=min (4;  5/3; 3) = 5/3.
Ведущим элементом является «12». Вводим в столбец БП переменную x_1, выводим x_4. Составляем симплексную таблицу второго шага:
СП
БП    x_4    x_2    CЧ
x_3    -1/3    14/3    28/3
x_1    1/12    1/3    5/3
x_5    -1/3    8/3    16/3
F    5/12    -7/3    25/3
  Х_2=(  5/3,0,28/3,0,16/3), F(Х_2)=  25/3.
Рассмотрев последнюю строку таблицы, мы вновь можем заметить, что в ней находятся отрицательные оценки, только теперь одна отрицательная оценка, это означает, что решение, которое было найдено нами, вновь нельзя назвать оптимальным и его можно улучшить. Находим ведущий элемент. Ведущим элементом является «14/3».
Составляем симплекс-таблицу третьего шага:

СП
БП    x_4    x_3    CЧ
x_2    -1/14    3/14    2
x_1    3/28    -1/14    1
x_5    -1/7    -4/7    0
F    1/4    1/2    13
  Х_3=(1,2,0,0,0), F(Х_3)=13.
Рассмотрев последнюю строку таблицы, мы  можем заметить, что все оценки свободных переменных являются положительными, следовательно, можно сделать вывод, что найденное опорное решение является оптимальным:
Х_опт=(1,2,0,0,0), F(Х_опт)=13.
Но необходимо не забывать то, что в задачах ЛП, которые предусматривают максимизацию какого-либо критерия, для определения правильной оценки результатов оптимизации их значения каждый раз необходимо сокращать на совокупную стоимость недоиспользованных ресурсов производства, а при минимизации критериев оптимизации их значения каждый раз необходимо увеличить на совокупную стоимость недоиспользованных ресурсов производства.
Единственным критерием оптимизации, который не требует подобной корректировки, в нашем случае может являться именно критерий максимизации использования заданных ограничений.
Математическая модель задачи примет следующий вид:
         F(x)=(4+12+4) x_1+(6+4+4) x_2=20x_1+14x_2  →max     (5)
Значения переменных〖 x〗_1 и x_2 составляют 1 и 2, новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, составило 48. То есть при максимизации недоиспользованных ресурсов мы сможем получить 48 тортов.
Ответ по первому способу. Оптимальные значения переменных составили:  〖 x〗_1=1 день, x_2=2 дня, оптимальный объём продукции составил 13 тортов; новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, равно 48, т.е. максимизации использования недоиспользованных ресурсов выпуск нашей кондитерской фабрики  может быть равен 48 тортам.
2 способ. Метод структурной оптимизации.
Для того, чтобы упростить решение поставленной задачи, мы будем использовать экспресс алгоритма метода структурной оптимизации.
Обозначим:
х_1 — время изготовления торта «Вдохновение»;
х_2 — время изготовления торта «Чёрный принц»;
Математическая модель задачи примет следующий вид:
                                F(x)=5x_1+4x_2  →max          (6)
при ограничениях:
                                                {█(〖4x〗_1+ 〖6x〗_(2 )≤16,@12x_1+ 〖4x〗_(2 )≤20,@4x_1+ 〖4x〗_2≤12,@x_1≥0,x_2≥0.  )┤     (7)
Экспресс алгоритм предполагает следующие действия [4, стр. 7]:
1. Расчёт суммарной интенсивности потребления ограниченных ресурсов 〖 A 〗_j.
〖                                                                A 〗_j=∑_i▒a_ij .    (8)
2. Расчёт предельных значений прототипов ограничений 〖 B 〗_i  для каждого вида ограничений:
〖 B 〗_j=∑_i▒〖a_ij* A_j 〗.     (9)
3. Расчёт значений коэффициентов корректировки γ_i величин 〖 A 〗_j:
γ_i=b_i/B_i .     (10)
4. Выбор предельного значения коэффициента корректировки〖 γ〗^*:
   4.1. Для задач линейного программирования с ограничениями « ≤ »:
〖 γ〗^*=min⁡(γ_i).    (11)
   4.2. Для задач линейного программирования с ограничениями « ≥ »:
〖 γ〗^*=max⁡(γ_i).    (12)
5. Расчёт значений неизвестных задачи линейного программирования:
X_j=A_j*〖 γ〗^*.    (13)
6. Определяем потребности в ресурсах для найденного решения задачи линейного программирования:
∑_(j=1)^n▒〖a_ij*〗 X_j=b_i.     (14)
7. Определение значения функции цели:
    F(x) = ∑_(j=1)^n▒〖C_i*〗 x_j.     (15)
Реализация алгоритма:
    Получаем: А_1=4+12+4=20; А_2=6+4+4=14.
    Получаем: В_1=4*20+6*14=164; В_2=12*20+4*14=296;В_3=4*20+4*14=136.
    Получаем: γ_1=16/164=0,098; γ_2=20/296=0,068; γ_3=12/136=0,088.
    Найдем наименьшее значение γ. 
γ^*=0,068.
    Получаем: Х_1=20*0,068=1,36; Х_2=14*0,068=0,952.
    Получаем:                      4*1,36+6*0,952=11,152
12*1,36+4*0,952=20,128
4*1,36+4*0,952=9,248
    Получаем:  F(x) = 20*1,36 + 14*0,952= 40,528
Ответ по второму способу. Оптимальные значения переменных составили:  〖 x〗_1=1,36 дней, x_2=0,952 дня, новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, равно 40,528 тортов.
Итак, решив задачу двумя способами, мы можем прийти к выводу о том, какой же из способов является более оптимальным. Более оптимальным является метод структурной оптимизации. Обоснуем данный выбор:
    В том случае, если для решения задачи ЛП применяется симлекс метод, то оптимальное решение, полученное с помощью этого метода, не даёт гарантии полного использования одного и более распределяемых видов ресурсов. Вследствие этого, данные, полученные в ходе решения задачи методом структурной оптимизации, являются более точными и конкретными.
    В случае использования для решения зада ЛП симплекс, значения коэффициентов функции цели не во всех случаях определяют направление поиска оптимального решения.
    Оптимальные планы производства, которые будут найдены с помощью решения задачи симплекс-методом, не дают гарантии стабильности, полноты и пропорциональности использования ограниченных ресурсов.
    В том случае, если для решения задачи ЛП применяется симлекс метод, то найденные оптимальные решения делают возможным полный отказ от производства части ранее производимой продукции, что может привести к тому, что спрос на данный вид продукции возрастёт, а вместе с ним возрастёт инфляция в стране. Данная особенность симплекс-метода делает невозможным его использование в задачах оптимизации с обязательной номенклатурой продукции без введения в математических моделях линейного программирования дополнительных ограничений на значения переменных [4, стр. 15].
Итак, существование рассмотренных проблем говорит о том, что переход 
от применения симплекс-метода к применению метода структурной оптимизации при разработке планов производства и программ развития народного хозяйства улучшит использование богатства страны, а также повысит объективность и однозначность принимаемых экономических решений. Так как при решении задач ЛП методом структурной оптимизации мы получаем более точные значения и пускаем в ход все имеющиеся ресурсы

Каждое предприятие ставит своей целью увеличение прибыли и уменьшение затрат (издержек) на производство. Для достижения намеченной цели в экономике часто используется прогнозирование и планирование затрат и оптимальных объёмов производимой на предприятии продукции.
Решение задач линейного программирования делает возможным повышение эффективности предприятия и увеличение его производительности, а именно:  роста доходов и прибыли или снижения затрат необходимых для изготовления продукции и технологических отходов при её производстве.
Для решения задач ЛП используют большое количество разных методов, в их число входят также метод структурной оптимизации и симплекс-метод. Рассмотрим эти два метода подробнее.
Симплекс-метод можно назвать главным или основным методом решения задач линейного программирования [1, стр. 35]. С помощью симплекс-метода за конечное число шагов можно определить существует ли оптимальное решение, или его нет. Родоначальником симплекс-метода является американский математик Роберт Данциг. Суть (содержание) симплекс-метода можно отразить с помощью следующих трёх пунктов [7, стр. 23]:
    Показать способ, с помощью которого можно найти первоначальный опорный план.
    Показать способ, с помощью которого можно перейти от одного опорного плана к другому, в случае если первый опорный план не оказался оптимальным. 
    Задать критерии, с помощью которых можно вовремя завершить процесс проверки решений на оптимальность или сделать вывод о том, что оптимальное решение не существует. 
Так же для решения задач линейного программирования используется метод структурной оптимизации. Структурная оптимизация — это метод, с помощью которого можно построить такую структуру как способа соединения элементов в систему, которая сможет стать максимально эффективной с точки зрения заранее поставленной практической цели и при заданных и всегда ограниченных ресурсах.
Оба метода используются при решении задач ЛП. Но какой из них является более точным и эффективным? Чтобы понять это, нам необходимо рассмотреть решение задач методом структурной оптимизации и симплекс методом. Для предметного представления результатов исследования решим задачу двумя способами.
Условие. Кондитерская фабрика, занимающаяся производством эксклюзивных тортов, имеет на складе какао, сахар и муку и может производить торты двух видов: торт «Вдохновение» и торт «Чёрный принц». Расход продуктов за один день  и общее количество ресурсов для каждого вида тортов представлены в таблице. 
    «Вдохновение»    «Чёрный принц»    Ресурсы
Сахар, кг    4    6    16
Мука, кг    12    4    20
Какао, кг    4    4    12
 За один день кондитерская может изготовить 5 тортов «Вдохновение» и 4 торта «Чёрный принц». Сколько дней должна работать кондитерская, чтобы при имеющихся ресурсах обеспечить максимальный выпуск тортов.
Решение. 1 способ. Симплекс-метод.
Пусть:
х_1 — время изготовления торта «Вдохновение»;
х_2 — время изготовления торта «Чёрный принц»;
Математическая модель задачи примет следующий вид:
                                F(x)=5x_1+4x_2  →max          (1)
при ограничениях:
                                        {█(〖4x〗_1+ 〖6x〗_(2 )≤16,@12x_1+ 〖4x〗_(2 )≤20,@〖4x〗_1+ 〖4x〗_2≤12,@x_1≥0,x_2≥0.  )┤           (2)
Приведём задачу к каноническому виду:
                                     F(x ̅ )=5x_1+4x_2  →max      (3)
при ограничениях:
                                          {█(4x_1+ 〖6x〗_(2 )+ x_3=16,@      12+ 4x_(2 )+,,,,,,,,x_4=20,@〖            4x〗_1+ 〖4x〗_2+,,,,,,,,,,,x_5=12,@x_J≥0,j= (1,5) ̅.             )┤       (4)
Принимаем x_1, x_2  в качестве свободных переменных,x_3, x_4, x_5 в качестве базисных. Составляем симплекс-таблицу, соответствующую начальному опорному плану.

СП
БП    x_1    x_2    CЧ
x_3    4    6    16
x_4    12    4    20
x_5    4    4    12
F    -5    -4    0

Начальный опорный план имеет вид:
  Х_1=(0,0,16,20,12), F(Х_1)=0.
Рассмотрев последнюю строку таблицы, мы можем заметить, что в ней находятся две отрицательные оценки, это означает, что решение, которое было найдено нами, нельзя назвать оптимальным и его можно улучшить. В качестве ведущего столбца принимаем столбец базисной переменной  x_1 (т.к. именно в этом столбце располагается наибольшее по модулю значение F), а за ведущую строку — строку переменной x_4, где min (16/4,20/12,12/4)=min (4;  5/3; 3) = 5/3.
Ведущим элементом является «12». Вводим в столбец БП переменную x_1, выводим x_4. Составляем симплексную таблицу второго шага:
СП
БП    x_4    x_2    CЧ
x_3    -1/3    14/3    28/3
x_1    1/12    1/3    5/3
x_5    -1/3    8/3    16/3
F    5/12    -7/3    25/3
  Х_2=(  5/3,0,28/3,0,16/3), F(Х_2)=  25/3.
Рассмотрев последнюю строку таблицы, мы вновь можем заметить, что в ней находятся отрицательные оценки, только теперь одна отрицательная оценка, это означает, что решение, которое было найдено нами, вновь нельзя назвать оптимальным и его можно улучшить. Находим ведущий элемент. Ведущим элементом является «14/3».
Составляем симплекс-таблицу третьего шага:

СП
БП    x_4    x_3    CЧ
x_2    -1/14    3/14    2
x_1    3/28    -1/14    1
x_5    -1/7    -4/7    0
F    1/4    1/2    13
  Х_3=(1,2,0,0,0), F(Х_3)=13.
Рассмотрев последнюю строку таблицы, мы  можем заметить, что все оценки свободных переменных являются положительными, следовательно, можно сделать вывод, что найденное опорное решение является оптимальным:
Х_опт=(1,2,0,0,0), F(Х_опт)=13.
Но необходимо не забывать то, что в задачах ЛП, которые предусматривают максимизацию какого-либо критерия, для определения правильной оценки результатов оптимизации их значения каждый раз необходимо сокращать на совокупную стоимость недоиспользованных ресурсов производства, а при минимизации критериев оптимизации их значения каждый раз необходимо увеличить на совокупную стоимость недоиспользованных ресурсов производства.
Единственным критерием оптимизации, который не требует подобной корректировки, в нашем случае может являться именно критерий максимизации использования заданных ограничений.
Математическая модель задачи примет следующий вид:
         F(x)=(4+12+4) x_1+(6+4+4) x_2=20x_1+14x_2  →max     (5)
Значения переменных〖 x〗_1 и x_2 составляют 1 и 2, новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, составило 48. То есть при максимизации недоиспользованных ресурсов мы сможем получить 48 тортов.
Ответ по первому способу. Оптимальные значения переменных составили:  〖 x〗_1=1 день, x_2=2 дня, оптимальный объём продукции составил 13 тортов; новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, равно 48, т.е. максимизации использования недоиспользованных ресурсов выпуск нашей кондитерской фабрики  может быть равен 48 тортам.
2 способ. Метод структурной оптимизации.
Для того, чтобы упростить решение поставленной задачи, мы будем использовать экспресс алгоритма метода структурной оптимизации.
Обозначим:
х_1 — время изготовления торта «Вдохновение»;
х_2 — время изготовления торта «Чёрный принц»;
Математическая модель задачи примет следующий вид:
                                F(x)=5x_1+4x_2  →max          (6)
при ограничениях:
                                                {█(〖4x〗_1+ 〖6x〗_(2 )≤16,@12x_1+ 〖4x〗_(2 )≤20,@4x_1+ 〖4x〗_2≤12,@x_1≥0,x_2≥0.  )┤     (7)
Экспресс алгоритм предполагает следующие действия [4, стр. 7]:
1. Расчёт суммарной интенсивности потребления ограниченных ресурсов 〖 A 〗_j.
〖                                                                A 〗_j=∑_i▒a_ij .    (8)
2. Расчёт предельных значений прототипов ограничений 〖 B 〗_i  для каждого вида ограничений:
〖 B 〗_j=∑_i▒〖a_ij* A_j 〗.     (9)
3. Расчёт значений коэффициентов корректировки γ_i величин 〖 A 〗_j:
γ_i=b_i/B_i .     (10)
4. Выбор предельного значения коэффициента корректировки〖 γ〗^*:
   4.1. Для задач линейного программирования с ограничениями « ≤ »:
〖 γ〗^*=min⁡(γ_i).    (11)
   4.2. Для задач линейного программирования с ограничениями « ≥ »:
〖 γ〗^*=max⁡(γ_i).    (12)
5. Расчёт значений неизвестных задачи линейного программирования:
X_j=A_j*〖 γ〗^*.    (13)
6. Определяем потребности в ресурсах для найденного решения задачи линейного программирования:
∑_(j=1)^n▒〖a_ij*〗 X_j=b_i.     (14)
7. Определение значения функции цели:
    F(x) = ∑_(j=1)^n▒〖C_i*〗 x_j.     (15)
Реализация алгоритма:
    Получаем: А_1=4+12+4=20; А_2=6+4+4=14.
    Получаем: В_1=4*20+6*14=164; В_2=12*20+4*14=296;В_3=4*20+4*14=136.
    Получаем: γ_1=16/164=0,098; γ_2=20/296=0,068; γ_3=12/136=0,088.
    Найдем наименьшее значение γ. 
γ^*=0,068.
    Получаем: Х_1=20*0,068=1,36; Х_2=14*0,068=0,952.
    Получаем:                      4*1,36+6*0,952=11,152
12*1,36+4*0,952=20,128
4*1,36+4*0,952=9,248
    Получаем:  F(x) = 20*1,36 + 14*0,952= 40,528
Ответ по второму способу. Оптимальные значения переменных составили:  〖 x〗_1=1,36 дней, x_2=0,952 дня, новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, равно 40,528 тортов.
Итак, решив задачу двумя способами, мы можем прийти к выводу о том, какой же из способов является более оптимальным. Более оптимальным является метод структурной оптимизации. Обоснуем данный выбор:
    В том случае, если для решения задачи ЛП применяется симлекс метод, то оптимальное решение, полученное с помощью этого метода, не даёт гарантии полного использования одного и более распределяемых видов ресурсов. Вследствие этого, данные, полученные в ходе решения задачи методом структурной оптимизации, являются более точными и конкретными.
    В случае использования для решения зада ЛП симплекс, значения коэффициентов функции цели не во всех случаях определяют направление поиска оптимального решения.
    Оптимальные планы производства, которые будут найдены с помощью решения задачи симплекс-методом, не дают гарантии стабильности, полноты и пропорциональности использования ограниченных ресурсов.
    В том случае, если для решения задачи ЛП применяется симлекс метод, то найденные оптимальные решения делают возможным полный отказ от производства части ранее производимой продукции, что может привести к тому, что спрос на данный вид продукции возрастёт, а вместе с ним возрастёт инфляция в стране. Данная особенность симплекс-метода делает невозможным его использование в задачах оптимизации с обязательной номенклатурой продукции без введения в математических моделях линейного программирования дополнительных ограничений на значения переменных [4, стр. 15].
Итак, существование рассмотренных проблем говорит о том, что переход 
от применения симплекс-метода к применению метода структурной оптимизации при разработке планов производства и программ развития народного хозяйства улучшит использование богатства страны, а также повысит объективность и однозначность принимаемых экономических решений. Так как при решении задач ЛП методом структурной оптимизации мы получаем более точные значения и пускаем в ход все имеющиеся ресурсы

Каждое предприятие ставит своей целью увеличение прибыли и уменьшение затрат (издержек) на производство. Для достижения намеченной цели в экономике часто используется прогнозирование и планирование затрат и оптимальных объёмов производимой на предприятии продукции.

Решение задач линейного программирования делает возможным повышение эффективности предприятия и увеличение его производительности, а именно:  роста доходов и прибыли или снижения затрат необходимых для изготовления продукции и технологических отходов при её производстве.

Для решения задач ЛП используют большое количество разных методов, в их число входят также метод структурной оптимизации и симплекс-метод. Рассмотрим эти два метода подробнее.

Симплекс-метод можно назвать главным или основным методом решения задач линейного программирования [1, стр. 35]. С помощью симплекс-метода за конечное число шагов можно определить существует ли оптимальное решение, или его нет. Родоначальником симплекс-метода является американский математик Роберт Данциг. Суть (содержание) симплекс-метода можно отразить с помощью следующих трёх пунктов [7, стр. 23]:

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

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

Оба метода используются при решении задач ЛП. Но какой из них является более точным и эффективным? Чтобы понять это, нам необходимо рассмотреть решение задач методом структурной оптимизации и симплекс‑методом. Для предметного представления результатов исследования решим задачу двумя способами.

Условие. Кондитерская фабрика, занимающаяся производством эксклюзивных тортов, имеет на складе какао, сахар и муку и может производить торты двух видов: торт «Вдохновение» и торт «Чёрный принц». Расход продуктов за один день  и общее количество ресурсов для каждого вида тортов представлены в таблице.

 

«Вдохновение»

«Чёрный принц»

Ресурсы

Сахар, кг

4

6

16

Мука, кг

12

4

20

Какао, кг

4

4

12

 За один день кондитерская может изготовить 5 тортов «Вдохновение» и 4 торта «Чёрный принц». Сколько дней должна работать кондитерская, чтобы при имеющихся ресурсах обеспечить максимальный выпуск тортов.

Решение. 1 способ. Симплекс-метод.

Пусть:

х1 — время изготовления торта «Вдохновение»;

х2 — время изготовления торта «Чёрный принц»;

Математическая модель задачи примет следующий вид:

                                Fx=5x1+4x2max                                        (1)

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

                                        4x1+ 6x2 ≤16,12x1+ 4x2 ≤20,4x1+ 4x2≤12,x1≥0,x2≥0.                                            (2)

Приведём задачу к каноническому виду:

                                     Fx=5x1+4x2max                                   (3)

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

                                          4x1+ 6x2 + x3=16,      12+ 4x2 +,,,,,,,,x4=20,            4x1+ 4x2+,,,,,,,,,,,x5=12,xJ≥0,j= 1,5.                                  (4)

Принимаем x1, x2 в качестве свободных переменных,  x3, x4, x5 в качестве базисных. Составляем симплекс-таблицу, соответствующую начальному опорному плану.

 

СП

БП

x1

x2

CЧ

x3

4

6

16

x4

12

4

20

x5

4

4

12

F

-5

-4

0

 

Начальный опорный план имеет вид:

  Х1=(0,0,16,20,12), F(Х1)=0.

Рассмотрев последнюю строку таблицы, мы можем заметить, что в ней находятся две отрицательные оценки, это означает, что решение, которое было найдено нами, нельзя назвать оптимальным и его можно улучшить. В качестве ведущего столбца принимаем столбец базисной переменной  x1 (т.к. именно в этом столбце располагается наибольшее по модулю значение F), а за ведущую строку — строку переменной x4, где min (164,2012,124)=min (4; 53; 3) = 53.

Ведущим элементом является «12». Вводим в столбец БП переменную x1, выводим x4. Составляем симплексную таблицу второго шага:

СП

БП

x4

x2

CЧ

x3

-1/3

14/3

28/3

x1

1/12

1/3

5/3

x5

-1/3

8/3

16/3

F

5/12

-7/3

25/3

  Х2=( 53, 0, 283,0, 163), F(Х2)= 253.

Рассмотрев последнюю строку таблицы, мы вновь можем заметить, что в ней находятся отрицательные оценки, только теперь одна отрицательная оценка, это означает, что решение, которое было найдено нами, вновь нельзя назвать оптимальным и его можно улучшить. Находим ведущий элемент. Ведущим элементом является «143».

Составляем симплекс-таблицу третьего шага:

 

СП

БП

x4

x3

CЧ

x2

-1/14

3/14

2

x1

3/28

-1/14

1

x5

-1/7

-4/7

0

F

1/4

1/2

13

  Х3=(1,2,0,0,0), F(Х3)=13.

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

Хопт=(1,2,0,0,0), F(Хопт)=13.

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

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

Математическая модель задачи примет следующий вид:

         Fx=4+12+4x1+6+4+4x2=20x1+14x2max   (5)

Значения переменных x1и x2 составляют 1 и 2, новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, составило 48. То есть при максимизации недоиспользованных ресурсов мы сможем получить 48 тортов.

Ответ по первому способу. Оптимальные значения переменных составили:   x1=1 день, x2=2 дня, оптимальный объём продукции составил 13 тортов; новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, равно 48, т.е. максимизации использования недоиспользованных ресурсов выпуск нашей кондитерской фабрики  может быть равен 48 тортам.

2 способ. Метод структурной оптимизации.

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

Обозначим:

х1 — время изготовления торта «Вдохновение»;

х2 — время изготовления торта «Чёрный принц»;

Математическая модель задачи примет следующий вид:

                                Fx=5x1+4x2max                                        (6)

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

                                                4x1+ 6x2 ≤16,12x1+ 4x2 ≤20,4x1+ 4x2≤12,x1≥0,x2≥0.                                    (7)

Экспресс алгоритм предполагает следующие действия [4, стр. 7]:

1. Расчёт суммарной интенсивности потребления ограниченных ресурсов  A j.

                                                                A j=iaij.                                               (8)

2. Расчёт предельных значений прототипов ограничений  B i  для каждого вида ограничений:

 B j=iaij* Aj.                                          (9)

3. Расчёт значений коэффициентов корректировки γi величин  A j:

γi=biBi.                                               (10)

4. Выбор предельного значения коэффициента корректировки γ*:

   4.1. Для задач линейного программирования с ограничениями «  »:

γ*=min⁡(γi).                                      (11)

   4.2. Для задач линейного программирования с ограничениями «  »:

γ*=max⁡(γi).                                      (12)

5. Расчёт значений неизвестных задачи линейного программирования:

Xj=Aj* γ*.                                          (13)

6. Определяем потребности в ресурсах для найденного решения задачи линейного программирования:

j=1naij*Xj=bi.                                                                                     (14)

7. Определение значения функции цели:

                                             F(x) = j=1nCi*xj.                                       (15)

Реализация алгоритма:

  1. Получаем: А1=4+12+4=20; А2=6+4+4=14.
  2. Получаем: В1=4*20+6*14=164; В2=12*20+4*14=296;В3=4*20+4*14=136.
  3. Получаем: γ1=16164=0,098; γ2=20296=0,068; γ3=12136=0,088.
  4. Найдем наименьшее значение γ.

γ*=0,068.

  1. Получаем: Х1=20*0,068=1,36; Х2=14*0,068=0,952.
  2. Получаем:                      4*1,36+6*0,952=11,152

12*1,36+4*0,952=20,128

4*1,36+4*0,952=9,248

  1. Получаем:  F(x) = 20*1,36 + 14*0,952= 40,528

Ответ по второму способу. Оптимальные значения переменных составили:   x1=1,36 дней, x2=0,952 дня, новое, найденное нами, значение функции цели, которое отражает потребление ограниченных ресурсов, равно 40,528 тортов.

Итак, решив задачу двумя способами, мы можем прийти к выводу о том, какой же из способов является более оптимальным. Более оптимальным является метод структурной оптимизации. Обоснуем данный выбор:

  1. В том случае, если для решения задачи ЛП применяется симлекс‑метод, то оптимальное решение, полученное с помощью этого метода, не даёт гарантии полного использования одного и более распределяемых видов ресурсов. Вследствие этого, данные, полученные в ходе решения задачи методом структурной оптимизации, являются более точными и конкретными.
  2. В случае использования для решения зада ЛП симплекс, значения коэффициентов функции цели не во всех случаях определяют направление поиска оптимального решения.
  3. Оптимальные планы производства, которые будут найдены с помощью решения задачи симплекс-методом, не дают гарантии стабильности, полноты и пропорциональности использования ограниченных ресурсов.
  4. В том случае, если для решения задачи ЛП применяется симлекс‑метод, то найденные оптимальные решения делают возможным полный отказ от производства части ранее производимой продукции, что может привести к тому, что спрос на данный вид продукции возрастёт, а вместе с ним возрастёт инфляция в стране. Данная особенность симплекс-метода делает невозможным его использование в задачах оптимизации с обязательной номенклатурой продукции без введения в математических моделях линейного программирования дополнительных ограничений на значения переменных [4, стр. 15].

Итак, существование рассмотренных проблем говорит о том, что переход

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

 

References

1. Akulich I. L. Mathematical programming examples and problems: a tutorial. - St. Petersburg: Publisher "LAN", 2011 - 352 pages.

2. Bundy B. basic linear programming: TRANS. from English. - Moscow: Radio and communication, 1989. - 176 pages.

3. Bolotnikova O. V. Linear programming: simplex method and duality: textbook. - Penza: publishing house of PSU, 2015. - 84 pages.

4. Karganov S. A. solving problems of linear programming by the method of structural optimization. "Management of economic systems" electronic scientific journal. 2012. No. 7.

5. Kuznetsov, A. V. Higher mathematics: mathematical programming: textbook. - Minsk: Higher school, 1994. - 286 pages.

6. Orlova I.V., Tarmash A.N., Fedoseyev V.V. Economic-mathematical methods and application models: manual. - Moscow: Unity Dana, 2015. - 302 pages.

7. Tsvil M. M. Mathematical methods and models in management: textbook. -Rostov-on-don: Russian customs Academy, Rostov branch, 2015. - 222 pages.

Login or Create
* Forgot password?