I. Линейное программирование

Производственная задача или задача планирования

Для ознакомления с основными структурными составляющими линейного программирования рассмотрим следующую конкретную задачу.

Задача 1. Для изготовления трех видов продукции А, В, С, используются следующие металлообрабатывающие станки: токарные, фрезерные, шлифовальные и используется сварочное оборудование. Предприятие обычно имеет ограниченные ресурсы по использованию станочного парка. На обработку каждого из типов изделий по каждому виду работ надо затратить определенное количество времени (станкочасов). Обозначим его через а_ij, где i - тип оборудования, j- вид изделия. Готовые изделия реализуются на рынке. При этом стоимость каждого изделия составляет с_j (например, руб/шт).

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

Воспользовавшись числовыми показателями (произвольно), представим условия задачи в табличной форме (таблица 1).

Обозначим количество производимых изделий по видам следующим образом:

А - х₁, В - х₂, С - х₃ .

Составим математическую модель производства:

- при работе фрезерного оборудования общие затраты станкочасов должны

подчиняться следующему неравенству:

Таблица 1

Условия производства

;

- при работе токарных станков общее время их загрузки должно отвечать неравенству:

;

- суммарная загрузка шлифовальных станков должна отвечать неравенству:

;

- сварочное оборудование может быть использовано на программу выпуска в соответствии с неравенством:

.

Приведенные выше неравенства называются ограничениями задачи. Они могут быть неравенствами типа как “ ≤ ”, так и “ ≥ “, возможны ограничения и в виде равенств. По смыслу задачи очевидны такие ограничения:

, , .

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

.

Целью задачи является нахождение такого плана производства, при котором функция F будет максимальной, т.е.:

.

Функция F называется функцией цели или функционалом.

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

Пусть имеется некоторый экономический объект, который может производить продукцию, ассортимент которой составляет п видов изделий. В процессе производства допустимо использование m видов ресурсов. Применяемые технологии характеризуются нормами затрат соответствующего ресурса по каждому виду изделия в количестве а_ij (где i=1…m, j=1…n). Если принять, что предприятие располагает каждым из ресурсов в объеме не более b_i, то при плане производства x_j по каждому типу изделия процесс должен подчиняться ограничениям:

(1)

Система линейных неравенств (1) с позиций векторной алгебры характеризуется следующим. Суммарные технологические нормативы для данного производства описываются матрицей:

Она называется технологической характеристикой предприятия. Сводный план производства (по видам изделий) может быть представлен в виде п – мерного вектора-строки:

.

Тогда общие затраты по i – му ресурсу на производство всех видов изделий можно выразить в виде суммы:

.

Она представляет собой скалярное произведение векторов А и Х. Ограничения на ресурсы, которыми располагает предприятие, описываются m - мерным вектор-столбцом:

,

где b_i - максимальное количество i – го ресурса, которое можно использовать в производственном процессе.

Тогда систему неравенств (1) можно записать в кратком виде, используя правила векторной алгебры, представив левую часть неравенств как произведение матрицы А на вектор Х, а правую – как вектор В:

. (2) К системе также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства: , , … ,… , или, что то же самое

. (3)

Обозначив через с_j цену единицы j – го продукта и записав вектор-строку

,

получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором Х:

или . (4)

Это векторная запись функции цели. Формулы (2,3,4) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого, например, экономического объекта, поведением которого мы хотим управлять. В рамках данной модели, вообще говоря, можно формулировать различные задачи. Но скорее всего самой естественной задачей будет задача поиска такого плана производства, который дает наибольшее (наименьшее) значение целевой функции (4), но одновременно удовлетворяет и ограничениям (2,3). Кратко такую задачу записывают в следующем виде:

, где

. (5)

Это векторная запись задачи линейного программирования (ЗЛП) типа планирования производства.

Несмотря на очевидную простоту задачи (5), ее решение является далеко не тривиальным и во многом стало возможным только после разработки специального математического аппарата. Существенным достоинством методов решения ЗЛП является их универсальность, поскольку к модели (5) могут быть сведены очень многие как экономические, так и неэкономические проблемы.

Поскольку любая научная модель содержит упрощающие предпосылки, для корректного применения получаемых с ее помощью результатов необходимо четкое понимание сути этих упрощений, что в конечном итоге позволяет сделать вывод об их допустимости или недопустимости. Наиболее «сильным» упрощением в рассмотренных моделях является предположение о прямо пропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат а_ij В действительности , что приводит к нелинейности функции цели, а соответственно к принципиальному изменению типа задачи. К другим упрощающим предпосылкам относятся предположения о независимости цен c_j от объемов производства x_j, что может быть справедливо только при незначительных объемах выпуска. Подобные «уязвимые» места модели важно знать, так как они позволяют наметить принципиальные направления совершенствования модели.