УДК 338

ИСПОЛЬЗОВАНИЕ МАТЕМАТИЧЕСКИХ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ПРОИЗВОДСТВА НА ПРЕДПРИЯТИИ РАДИОЭЛЕКТРОННОЙ ПРОМЫШЛЕННОСТИ

THE USE OF MATHEMATICAL LINEAR PROGRAMMING METHODS TO OPTIMIZE PRODUCTION AT THE PLANT OF ELECTRONIC INDUSTRY

Фёдоров Дмитрий Евгеньевич,

магистрант, Национальный исследовательский ядерный университет «МИФИ», г. Москва

E-mail: mifi93@mail.ru

Fedorov Dmitry,

graduate student, national research nuclear University «MEPhI», Moscow

E-mail: mifi93@mail.ru

Аннотация

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

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

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

Ключевые слова: метод математического линейного программирования, симплекс метод, предприятие, оптимизация производства, максимизация прибыли.

Summary

The main area of work is the use of a mathematical method of linear programming – simplex method. Mathematical programming allows you to find the best plans for the allocation of scarce resources to achieve a specific task. The best result is achieved not at the expense of additional funds and for more effective allocation and use of available resources.

In the course of the work deals with the enterprise of electronic industry. During the current difficult political and economic situation in the country is required to reduce the share of purchased imported components to 0% and calculate the planned output according for 2015. The calculation uses the simplex method, which allows you to find the most profitable production while reducing the cost of production to maximize profit.

The obtained results have practical significance not only for specific enterprises but also for the optimization of any production from textile industry to high-tech industries.

Key words: method of mathematical linear programming, simplex method, enterprise, optimization of production and maximization of profit.

В данной статье анализируется предприятие радиоэлектронной промышленности. Основной проблемой отрасли является высокая зависимость от импортных комплектующих как в гражданском секторе, так и в военном. Была принята государственная программа «Развитие электронной и радиоэлектронной промышленности на 2013-2025 годы». Данная программа предусматривает выделение материальной поддержки на переоснащение производственных фондов, стимулирование темпов производства радиоэлектронных изделий за счет государственных заказов.

Предприятие специализируется на производстве бортовых цифровых вычислительных машин для жестких условий эксплуатации. Имеется 4 готовых продукта: система «Феникс», бцвм А-15АР, бцвм серий ЕА2164, 2165, 2166. В 2015 году себестоимость систем «Феникс» составила 112,07 млн. руб. в количестве 20 штук. БЦВМ А-15АР и серий 2164, 2165, 2166 входят в раздел «Поставка», которая составила 45,99 млн. руб., соответственно было произведено 8,13 и 31 штук.

Таблица 1.Себестоимость за 2015 год

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

Таблица 2. Плановые ключевые показатели

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

Задачей линейного программирования называется задача минимизации (максимизации) значения целевой функции (нескольких переменных), с учетом ограничений на значения этих переменных (выраженных явно, или через уравнения связи), где все зависимости являются линейными. [1]

Для начала требуется определить основные переменные.

х₁, х₂, х₃, х₄ – объемы производства таких продуктов, как система «Феникс», БЦВМ серий А-15АР, ЕА2164, 2165, 2166 соответственно.

F (x) – функция максимизация прибыли.

F (x) = 0,93x₁ + 0,13x₂ + 0,14x₃ + 0,15x₄ → max

Так как за 2015 год было произведено по заказам определённое количество единиц, то вводятся ограничения для каждого из видов. При этом изменилась себестоимость продукции, но средства на их изготовление остались те же самые.

4,67x₁ ≤ 112, 07

0,66x₂ + 0,73x₃ + 0,76x₄ ≤ 45, 99

X₁ ≥ 20

X₂ ≥ 8

X₃ ≥ 13

X₄ ≥ 31

В итоге мы имеем 6 ограничений.

Преобразуем неравенства в равенства добавлением неотрицательных переменных:

0,93x₁ + 0,13x₂+ 0,14x₃ + 0,15x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ → max

0x₂+ 0x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ = 112, 07

0,66x₂+ 0,73x₃ + 0,76x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ = 45, 99

0x₂+ 0x₃ + 0x₄ + 0x₅ + 1x₆ — 1x₇ + 0x₈ + 0x₉ + 0x₁₀ = 20

1x₂+ 0x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ — 1x₈ + 0x₉ + 0x₁₀ = 8

0x₂+ 1x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ — 1x₈ — 1x₉ + 0x₁₀ = 13

0x₂+ 0x₃ + 1x₄ + 0x₅ + 1x₆ + 0x₇ — 1x₈ — 1x₉ — 1x₁₀ = 31

X₄, x₅, x₆, x₇, x₈, x₉, x₁₀ ≥ 0

Так как количество базисных векторов должен быть 6, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на − M, где M, очень большое число:

0,93x₁ + 0,13x₂+ 0,14x₃ + 0,15x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ – Mx₁₁ – Mx₁₂ – Mx₁₃ – Mx₁₄ → max

4,67x₁ + 0x₂+ 0x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 112, 07

0x₁ + 0,66x₂+ 0,73x₃ + 0,76x₄ + 0x₅ + 1x₆+ 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 45, 99

1x₁ + 0x₂+ 0x₃ + 0x₄ + 0x₅ + 0x₆ — 1x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 20

0x₁ + 1x₂+ 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ — 1x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 8

0x₁ + 0x₂+ 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ — 1x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 13

0x₁ + 0x₂+ 0x₃ + 1x₄ + 0x₅ + 0x₆ — 1x₇ + 0x₈ + 0x₉ — 1x₁₀ + 0x₁₁ + 0x₁₂ + 0x₁₃ + 0x₁₄ = 31

x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂, x₁₃, x₁₄ ≥ 0

Матрица коэффициентов A=│a_ij│ системы уравнений имеет вид:

Таблица 3. Матрица коэффициентов

Правая часть ограничений системы уравнений имеет вид:

Таблица 4. Правая часть ограничений системы

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с искусственными переменными:

Таблица 5. Ввод новых переменных

Базисные векторы x₅, x₆, x₁₁, x₁₂, x₁₃, x₁₄, следовательно, все элементы в столбцах x₅, x₆, x₁₁, x₁₂, x₁₃, x₁₄, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₁₁, кроме ведущего элемента. Для этого сложим строку 8 со строкой 3, умноженной на -1. Обнулим все элементы столбца x₁₂, кроме ведущего элемента. Для этого сложим строку 8 со строкой 4, умноженной на -1. Обнулим все элементы столбца x₁₃, кроме ведущего элемента. Для этого сложим строку 8 со строкой 5, умноженной на -1. Обнулим все элементы столбца x₁₄, кроме ведущего элемента. Для этого сложим строку 8 со строкой 6, умноженной на -1.

Таблица 6. Шаг 0

Шаг 1: запишем текущий опорный план:

X = │0  0  0  0  112.07  45.99  0  0  0  0  20  8  13  31│

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-1.), следовательно, в базис входит вектор x₁. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (a_i,0 /a_i,1), при a_i,1>0, i=1,…6. min(112.07:4.67, 20.:1.)=20. соответствует строке 3. Из базиса выходит вектор x₁₁. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 1, 7, 8 со строкой 3, умноженной на -4.67, 0.93, 1, соответственно.

Симплекс таблица примет следующий вид:

Таблица 7. Шаг 1

Шаг 2:

Запишем текущий опорный план:

X = │20  0  0  0  18.67  45.99  0  0  0  0  0  8  13  31│

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-1.), следовательно, в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (a_i,0 /a_i,2), при a_i,2>0,i=1,…6. min(45.99:0.66, 8.:1.)=8. соответствует строке 4. Из базиса выходит вектор x₁₂. Сделаем исключение Гаусса для столбца x₂, учитывая, что ведущий элемент соответствует строке 4. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 2, 7, 8 со строкой 4, умноженной на -0.66, 0.13, 1, соответственно.

Симплекс таблица примет следующий вид:

Таблица 8. Шаг 2

Шаг 3:

Запишем текущий опорный план:

X = │20  8  0  0  18.67  45.71  0  0  0  0  0  0  13  31│

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-1.), следовательно, в базис входит вектор x₄. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (a_i,0 /a_i,4), при a_i,4>0,i=1,…6. min(31.22:0.76, 31.:1.)=31. соответствует строке 6. Из базиса выходит вектор x₁₄. Сделаем исключение Гаусса для столбца x₄, учитывая, что ведущий элемент соответствует строке 6. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 2, 7, 8 со строкой 6, умноженной на -0.76, 0.15, 1, соответственно.

Симплекс таблица примет следующий вид:

Таблица 9. Шаг 3

Шаг 4:

Запишем текущий опорный план:

X = │20  8  13  0  18.67  31.22  0  0  0  0  0  0  0  31│

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-1.), следовательно, в базис входит вектор x₄. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (a_i,0 /a_i,4), при a_i,4>0, i=1…6. min (31.22: 0.76, 31:1) = 31. соответствует строке 6. Из базиса выходит вектор x₁₄. Сделаем исключение Гаусса для столбца x₄, учитывая, что ведущий элемент соответствует строке 6. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 2, 7, 8 со строкой 6, умноженной на -0.76, 0.15, 1, соответственно.

Симплекс таблица примет следующий вид:

Таблица 10. Шаг 4

Шаг 5:

Запишем текущий опорный план:

X = │20  8  13  31  18.67  7.66  0  0  0  0  0  0  0  31│

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-0.93), следовательно, в базис входит вектор x₇. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (a_i,0 /a_i,7), при a_i,7>0, i=1…6. min (18.67: 4.67) =3.99 соответствует строке 1. Из базиса выходит вектор x₅. Сделаем исключение Гаусса для столбца x₇, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 3, 7 со строкой 1, умноженной на 0.21, 0.2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Таблица 11. Шаг 5

Шаг 6:

Запишем текущий опорный план:

X = │23.99  8  13  31  0  7.66  3.99  0  0  0  0  0  0  0│

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-0.15), следовательно, в базис входит вектор x₁₀. Определяем, какой вектор выходит из базиса. Для этого вычисляем min (a_i,0 /a_i,10), при a_i,10>0, i=1…6. min (7.66: 0.76) =10.07 соответствует строке 2. Из базиса выходит вектор x₆. Сделаем исключение Гаусса для столбца x₁₀, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 6, 7 со строкой 2, умноженной на 1.31, 0.2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Таблица 12. Шаг 6

Шаг 7:

Запишем текущий опорный план:

X = │23.99  8  13  41.07  0  0  3.99  0  0  10.07  0  0  0  0│

Текущий опорный план является оптимальным, так как в строках 7−8 под переменными X₁, x₂, x₃, X₄, x₅, x₆, x₇, x₈, x₉, x₁₀ нет отрицательных элементов.

Записываем конечное решение:

X₁ = 23, 99, x₂ = 8, x₃ = 13, x₄ = 41, 07

Значение целевой функции в данной точке:

F(x) = 0,934*23, 99+0,132*8+0,146*13+0,152*41, 07 = 31, 61

В итоге следует произвести 23шт. – систем «Феникс», 8 шт. – БЦВМ А-15Р, 13 шт. – БЦВМ серий ЕА 2164, 2165, 41шт. – БЦВМ серии ЕА2166. В совокупности предприятию это принесет максимальную чистую прибыль в размере 31,61 млн. руб. Все изделия будут выполнены только на основе отечественной элементной базе, что сэкономит деньги государству. Если данные мероприятия реализуется, не исключено, что производить продукцию будут в более масштабных объемах, что принесет дополнительную прибыль.

 

Список литературы

1. Коротков М., Основы линейного программирования 2003г.
2. Э.В. Киселева, Математическое программирование, 2002 г.
3. Киселева Е.В., Построение математических моделей целочисленного линейного программирования. Примеры и задачи, 2012 г.
4. Гераськин М.И., Линейное программирование, 2014 г.
5. Правительство России – Об утверждении государственной программы Российской Федерации [Электронный ресурс]. – Режим доступа: http://government.ru/docs/3345/
6. Хохлов С.В., Радиоэлектронная промышленность в 2014-2015 годах: итоги, задачи и направления развития.