Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

USING LINEAR PROGRAMMING METHODS FOR SOLVING THE OPTIMIZATION PROBLEM OF PRODUCTION

Lalayan L.R 1 Shamashova A.V. 1
1 Stavropol State Agrarian University
The development of modern society is characterized by an increase in the technical level, the complication of the organizational structure of production, the deepening of the social division of labor, the presentation of high requirements to methods of planning and economic management. In these conditions, only a scientific approach to the management of the economic life of society will ensure high rates of development of the national economy. One of the necessary conditions for the further development of economic science is the application of precise methods of quantitative analysis, the extensive use of mathematics. At present, the latest achievements of mathematics and modern computer technology are increasingly used in economic research and planning. Especially successful are the methods of optimal planning, which constitute the essence of mathematical programming. The solution of the problem of production optimization as one of the problems of the mathematical support of computer-aided design (CAD) systems is proposed.
optimization problem
CAD software
technological efficiency
simplex method

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

В рамках жизненного цикла промышленных изделий система автоматизированного проектирования (САПР) решает задачи автоматизации работ на стадиях проектирования и подготовки производства. Предприятия, ведущие разработки без САПР или лишь с малой степенью их использования, оказываются неконкурентоспособными как из-за больших материальных и временных затрат на проектирование, так и из-за невысокого качества проектов.

Средство обеспечения САПР – это совокупность однотипных компонентов. Выделяют следующие виды обеспечения САПР: техническое, математическое, программное, лингвистическое, информационное и организационное. Эффективность и производительность работы САПР в наибольшей степени зависит от его математического обеспечения. Математическое обеспечение (МО) САПР состоит из математических моделей, методов и алгоритмов, необходимых для решения задач автоматизированного проектирования, которые помогают справиться с поставленной задачей. Выделяют три основные задачи, рассматриваемые в математическом обеспечении САПР: задача анализа, задача оптимизации и задача синтеза [5].

В данной работе подробно рассмотрим задачу оптимизации производственного процесса. Задача оптимизации заключается в повышении эффективности технологических и организационных систем (металлорежущего станка, автоматической линии, производства в целом) при помощи принятия продуманных решений. Главное в постановке задачи оптимизации: максимизация или минимизация целевой функции. Оптимизировать можно разные процессы производства: себестоимость детали (минимизация), быстродействие оборудования, доход от реализации (максимизация) и т.д. [2].

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

В процессе принятия оптимальных решений теоретически наиболее эффективны методы математического программирования: линейное, нелинейное, динамическое программирование и т.д. [4].

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

Допустим, предприятие выпускает два вида изделий: А и В. Для их изготовления используется 3 вида станков (С1, С2, С3). Длительность обработки каждого изделия: на станке типа С1 изделий А – 12; изделий В – 4 единицы; на станке типа С2 изделий А – 4, изделий В – 4 единицы; на станке типа С3 изделий А – 3, изделий В – 12 единиц. Прибыль от реализации одного изделия А составляет 30 единиц, В – 40 единиц. Рабочее время станка С1 – 300 единиц, С2 – 120 единиц, С3 – 252 единиц. Необходимо определить такой план выпуска продукции А и В, чтобы прибыль предприятия была максимальна.

Решение данной задачи осуществляется с помощью симплекс-метода. Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом. [3].

Математическая модель данной задачи имеет вид:

lal1.wmf

где х1 – количество изделий А, х2 – количество изделий В.

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

lal2.wmf

lal3.wmf

lal4.wmf

Построим исходную симплекс-таблицу (табл. 1).

Таблица 1

Исходная симплекс-таблица

Базисные переменные i

x1

x2

x3

x4

x5

Свободный член b

Отношение

lal5.wmf

x3

12

4

1

0

0

300

75

x4

4

4

0

1

0

120

30

x5

13

12

0

0

1

252

21

F

-30

-40

0

0

0

0

-

Допустимый вектор имеет вид: Х(1)=(0,0,300,120,252). План не оптимален, так как в индексной строке есть отрицательные элементы. Ведущий столбец k=2, т.к. в индексной строке наименьший отрицательный элемент стоит во втором столбце. Ведущая строка l=3, так как в третьей строке наименьшее отношение lal6.wmf. Ведущий элемент lal7.wmf.

Построим новую симплекс-таблицу (табл. 2).

lal8.wmf.

Таблица 2

Новая симплекс таблица

Базисные переменные i

x1

x2

x3

x4

x5

Свободный член b

Отношение

lal9.wmf

x3

11

0

1

0

-1/3

216

19,63

x4

3

0

0

1

-1/3

36

12

x5

¼

1

0

0

1/12

21

84

F

-20

-0

0

0

40/12

840

-

Допустимый вектор имеет вид: Х(2)=(0,21,216,36,0). План не оптимален, так как в индексной строке есть отрицательный элемент. Ведущий столбец k=1, так как в индексной строке наименьший отрицательный элемент стоит в первом столбце. Ведущая строка l=2, т.к. во второй строке наименьшее отношение lal10.wmf. Ведущий элемент lal11.wmf.

Построим новую симплекс-таблицу (табл. 3).

lal12.wmf.

Таблица 3

Итоговая симплекс таблица

Базисные переменные i

x1

x2

x3

x4

x5

Свободный член b

Отношение

lal13.wmf

x3

0

0

1

–11/13

8/9

84

x4

1

0

0

1/3

–1/9

12

x5

0

1

0

–1/12

1/9

18

F

0

-0

0

20/3

10/9

1080

Допустимый вектор имеет вид: Х(3)=(12,18,84,0,0). Полученный план оптимален, так как в индексной строке нет отрицательных элементов. Значит, допустимый вектор Х(3) является оптимальным. Целевая функция имеет вид:

F = 1080–20/3 х4 –10/9 х5.

Таким образом, получили оптимальный план производства, где максимальная прибыль составит 1080 единиц (по условию все lal16.wmf). При этом следует выпускать 12 единиц изделий А и 18 единиц изделий В, станок С2 и С3 загружены полностью, а у станка С1 имеется резерв времени 84 единицы.

В ходе решения получили оптимальный план производства, где максимальная прибыль составит 1080 единиц (по условию все lal17.wmf). При этом следует выпускать 12 единиц изделий А и 18 единиц изделий В, станок С2 и С3 загружены полностью, а у станка С1 имеется резерв времени 84 единицы.

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