Исходная задача. 1 страница

Двойственная задача:

Почему двойственная задача столь важна? Дело в том, что оптимальные значения показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. При этом оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). Поэтому их называют «объективно обусловленными оценками» сырья и рабочей силы.

Методы решения сформулированных задач хорошо разработаны и реализованы практически во всех математических пакетах программ, например, в Exel. Наиболее часто используется так называемый симплекс-метод решения задач линейного программирования. Мы не будем останавливаться на изложении этих методов, а сосредоточимся на рассмотрении примеров конкретных постановок для принятия решений.

2.3.2 Математическая модель планирования производства

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

Имеется видов сырья, из которого нужно изготовить видов продукции. Каждый из видов сырья может быть использован различным способом в соответствии с технологическими картами, которые мы будем считать заданными. Обозначим объем -й продукции при обработке сырья j-м способом ( ; ). Здесь общее количество технологических карт. Эти величина образуют матрицу , в которой каждая строка соответствует одному виду продукции, а каждый столбец – технологической карте.

Карты пронумерованы все подряд, но каждая карта пригодна для обработки только определенного вида сырья. Этот факт может быть описан с помощью переменных , которые принимают значение 1, если -я карта может быть использована для обработки сырья -го вида, и значение 0 в противном случае ( ; ). Переменные образуют ‑ матрицу , состоящую из нулей и единиц следующего вида:

. (2.12)

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

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

. (2.13)

Всю спецификацию вырабатываемой продукции можно представить в виде вектора-столбца , который может быть представлен как произведение матрицы на вектор :

. (2.14)

Общий объем (или стоимость) продукции, производимой при плане производства ,определится путем сложения объемов по всем ее видам:

. (2.15)

С учетом (2.13), изменяя порядок суммирования, получим:

. (2.16)

В этой формуле - общий объем (или стоимость) продукции всех видов, получаемой из единицы сырья при использовании в производстве ‑й технологической карты. Эти величины также могут быть объединены в вектор-столбец размерностью M: .

Получим более компактную запись для общего объема продукции:

. (2.17)

Обратимся теперь к сырью. Пусть ( ) - количество сырья ‑го вида, идущего на изготовление продукции. Тогда спецификация имеющегося сырья может быть представлена в виде вектора-столбца

.

По аналогии с формулой (2.14), спецификация сырья, подлежащего обработке при плане производства , определится выражением

. (2.18)

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

Общая стоимость сырья, использованного в соответствии с планом производства с учетом (2.18) равна

. (2.19)

В формуле (2.19) вектор-строка определяет стоимость сырья, обрабатываемого по -й технологической карте.

Часто при планировании производства учитывают отходы сырья. Пусть , ( ) - количество отходов, образующихся при обработке сырья по ‑й технологической карте. Тогда суммарные отходы, получаемые при плане производства , определятся выражением

, (2.20)

где .

2.3.3 Задачи оптимального планирования производства

Приведенные в п. 2.3.2 соотношения позволяют формулировать задачи оптимального планирования производства [10]. Для этого предварительно необходимо проделать следующие операции:

· составить все необходимые технологические карты, на их основе рассчитать матрицы и , а также определить векторы .

· принять решение о критерии оптимизации. В частности, таким критерием может быть:

а) максимум выхода продукции (2.17),

б) минимум расхода сырья (2.19),

в) минимум отходов (2.20).

В практике планирования производства возможны различные постановки задач оптимизации. Ниже рассмотрены три наиболее типичных случая.

Первый случай планирования

Заданы:

· спецификация вырабатываемой продукции ,

· матрицы и ,

· векторы ,

Требуется определить:

· оптимальную по выбранному критерию спецификацию сырья – вектор ;

· план производства , обеспечивающий получение спецификации .

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

. (2.21)

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

. (2.22)

Критерии оптимизации могут быть двух видов:

· минимум расхода сырья

где ; (2.23)

· или минимум отходов

. (2.24)

Использование в качестве критерия максимума выхода продукции (2.17) в рассматриваемой задаче не имеет смысла, т.к. спецификация продукции жестко задана.

Задачи (2.21), (2.22), (2.23) и (2.21), (2.22), (2.24) представляют собой задачи линейного программирования, которые можно решить с помощью стандартных программ, реализующих алгоритм симплекс-метода. Решив эти задачи и получив оптимальный вектор , можно затем определить искомую оптимальную спецификацию сырья (вектор ):

. (2.25)

Второй случай планирования

Заданы:

· спецификация сырья ,

· матрицы и ,

· векторы .

Требуется определить:

· оптимальную по выбранному критерию спецификацию вырабатываемой продукции ,

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

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

, (2.26)

(2.27)

и обеспечивает экстремум одного из критериев:

· максимум выпуска продукции , (2.28)

· минимум отходов . (2.29)

Использование в качестве критерия оптимизации минимума расхода сырья в данной постановке невозможно, т.к. объемы сырья заданы. Как и в предыдущем случае, решив с помощью стандартной программы задачи (2.26), (2.27), (2.28) или (2.26), (2.27), (2.29), получим оптимальный план производства , а затем искомую оптимальную спецификацию продукции

. (2.30)

Третий случай планирования

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

Заданы:

· спецификация сырья ,

· плановая спецификация вырабатываемой продукции ,

· матрицы и ,

· векторы .

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

В данном случае ограничения имеют вид

· , (2.31)

· , (2.32)

а критерий оптимальности задается одним из выражений:

· максимум выпуска продукции

, (2.33)

· минимум отходов

, (2.34)

· минимум расхода сырья

. (2.35)

Найдя план производства как решение неравенств (2.31), (2.32) с условиями (2.33), (2.34) или (2.35), необходимо затем вычислить фактические спецификации вырабатываемой продукции и используемого сырья .

Пример. Рассмотрим пример принятия решения о производстве пиломатериалов из круглых бревен [10].

Требуется составить план раскроя бревен четырех размерных групп со средними диаметрами вершинной части 38. 42, 46 и 50 сантиметров на пиломатериалы 12 сечений с использованием 12 технологических карт (поставов). При этом нужно выполнить заданную спецификацию пиломатериалов и обеспечить минимум расхода сырья.

Характеристики сырья приведены в таблице 2.5, а характеристики карт раскроя – в таблице 2.4.

.

Таблица 2.5.

Характеристики сырья

Плановая спецификация вырабатываемых пиломатериалов определена таблицей 2.6.

Таблица 2.5

План выработки пиломатериалов

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

Выпишем все исходные данные задачи. Матрица определится таблицей 2.4.

Матрица применимости карт раскроя к видам сырья также определяется таблицей 2.4 и имеет вид

. (2.36)

Векторы спецификаций сырья и пиломатериалов определяются соответственно таблицами 2.5 и 2.6 и имеют следующий вид.

(2.37)

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

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

(2.38)

который бы удовлетворял системе ограничений

(2.39)

и доставлял минимум критерию

(2.40)

Сформулированная задача решалась с использованием стандартной программы, реализующей симплекс-метод. В результате расчета были выбраны карты раскроя с номерами 3,6,7,9 и 10, а остальные карты не использовались. Полученный вектор оптимального выпуска продукции после округления значений до ближайшего целого числа имеет вид

(2.41)

При этом фактически будет выработана следующая спецификация продукции (в куб.м):

Мы видим, что план по выпуску продукции выполнен, а по ряду позиций – и перевыполнен.

Фактически израсходовано следующее количество сырья (штук бревен):

. (2.42)

Сравнивая полученные цифры с заданной спецификацией (2.37), мы видим, что получилась значительная экономия сырья.

Значение критерия оптимизации (общий объем израсходованного сырья) составил

(куб.м). (2.43)

2.3.4 Транспортная задача

В качестве следующего примера задачи оптимизации при принятии решений рассмотрим так называемую транспортную задачу, которая также часто встречается на практике [26].

Задача формулируется следующим образом. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать «прикрепление» потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.

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

. (2.44)

Стоимость доставки единицы товара со склада номер потребителю номер составляет рублей.

Обозначим количество товаров, поставляемых со склада номер потребителю номер , , .

Должны выполниться следующие условия.

· Все товары со складов должны быть вывезены:

, . (2.45)

· Все потребители должны быть удовлетворены:

, . (2.46)

· Все должны быть неотрицательными: .

Принятие решение заключается в составлении плана перевозок, т.е. выборе объемов поставок товара со склада потребителю . При этом суммарные затраты на перевозку должны быть минимальными:

. (2.47)

Пример. Рассмотрим решение транспортной задачи, исходные данные к которой представлены в таблице 2.7.

Таблица 2.7

Исходные данные к транспортной задаче