Глава 3. Исследование и решение распределительных задач

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

• по виду целевой функции – на линейные и нелинейные. Если затраты (доход), определяемые объемом x_ij ресурса i, выделенного на выполнение работы j, равны x_ijc_ij, то задача линейна, а в противном случае нелинейна;

• по имеющимся в наличии необходимым ресурсам – на сбалансированные (закрытые) и несбалансированные (открытые). Если общий объем наличных ресурсов равен общей потребности в них, то имеет место сбалансированная (закрытая) распределительная задача, в противном случае она не сбалансирована (открыта);

• по характеру изменения переменных – подразделяются на три класса:

– если все переменные при решении могут принимать любое значение из области допустимых, имеющих непрерывный характер, то такие задачи мы будем относить к классу задач с непрерывным изменением переменных;

– если на все переменные или на их часть наложено дополнительное требование целочисленности, то мы имеем дело с целочисленными распределительными задачами;

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

• по количеству экстремумов у целевой функции – на одноэкстремальные и многоэкстремальные. Класс распределительных задач, для которых любой локальный оптимум целевой функции на множестве допустимых планов является одновременно и глобальным оптимумом, называется одно-экстремальным. При наличии в задаче многих локальных экстремумов она называется многоэкстремальной;

• по характеру распределения ресурсов во времени – на статические и динамические. Если распределительная задача не связана со временем или каждое последующее распределение не зависит от всех остальных, то задача называется статической, в противном случае – динамической.

Рассмотрим решение в системе Mathcad некоторых распределительных задач.

Общая задача линейного программирования (ОЗЛП)

Постановка задачи

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

Выявление основных особенностей и закономерностей.

Количество изделий j-го наименования, которое может производить предприятие, обозначим за x_j. Зная требуемое количество каждого вида i-го ресурса для изготовления каждого j-го типа изделия – норму расхода c_ij и количество каждого i-го ресурса a_i , имеющегося в наличии на предприятии, – можно записать в общем виде следующую систему неравенств:

с₁₁· х₁ + с₁₂ · х₂ +…+с_1j · x_j +…+c_1n · x_n ≤ a₁

…………………………………………..

с_i1· х₁ + с_i2 · х₂ +…+с_ij · x_j +…+c_in · x_n ≤ a_i

…………………………………………..

с_m1· х₁ + с_m2 · х₂ +…+с_mj · x_j +…+c_mn · x_n ≤ a_m

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

f(x)=P₁·x₁ + P₂ · x₂ +…+ P_j · x_j +…+P_n · x_n

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

3х₁ +5х₂ + 2х₃ + 7х₄ ≤ 15

4х₁ +3х₂ + 3х₃ + 5х₄ ≤ 9

5х₁ +6х₂ + 4х₃ + 8х₄ ≤ 30

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

f(x)= 40х₁ +50х₂ + 30х₃ + 20х₄