Распределение транспортных единиц по линиям

Имеется n транспортных линий, по j–ой линии необходимо выполнить bj рейсов . В наличии имеются транспортные единицы m типов. Резервы полезного времени транспортной единицы типа i составляют аi . На выполнение транспортной единицей типа i рейса j требуется время tij, а затраты на рейс составляют сij. Требуется найти наиболее экономичную расстановку транспортных единиц по линиям.

Математическая модель

(суммарные транспортные расходы минимальные)

(ограничения по фондам времени каждой транспортной единицы)

(все рейсы должны быть выполнены)

хij ≥ 0, , , хij – целые.

Выбор средств доставки грузов.

Имеется m грузообразующих пунктов с объемами грузов а_i . Имеется n средств доставки грузов (видов транспорта), грузоподъемность j–го средства доставки составляет р_j, а наличный его парк равен N_j, . Грузы подлежат доставке в один центральный пункт (склад), затраты при осуществлении одной единицей средства доставки j–го рейса от пункта i до склада равны с_ij.

Через х_ij обозначим количество средств доставки типа j, отправляющееся из пункта i .

Математическая модель

(суммарные транспортные расходы минимальные)

(ограничения по грузоподъемности каждой транспортной единицы)

(все рейсы должны быть выполнены)

хij ≥ 0, , , хij – целые.

Задача о назначениях

Частным случаем транспортной задачи линейного программирования является задача о назначениях – задача выбора.

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

То есть, ресурсы не делимы между работами, а работы не делимы между ресурсами.

Задача о назначениях имеет место при назначении людей на должности, водителей на машины, транспортных средств на маршруты, при распределении групп по аудиториям, тем по подразделениям.

Исходные параметры модели

Имеется n работ и n кандидатов для их выполнения (механизмов). Производительность каждого механизма различна. Затраты i-го кандидата на выполнение j-ой работы равны c_ij (i, j = ).

Пусть х_ij – переменная, значение которой равно 1, если i-й кандидат назначен выполнять j-ю работу и 0 – в противном случае.

Математическая модель.

Найти минимум целевой функции

(в целевую функцию входят только те значения c_ij (i, j = ), для которых х_ij отличны от нуля, т.е. входят затраты, соответствующие назначенным работам)

при ограничениях

(каждый кандидат выполняет только одну работу);

(каждая работа может выполняться одним кандидатом);

х_ij Є {0; 1}, (i, j = ).

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

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

Экономическая интерпретация задач линейного программирования.

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

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

Возможная формулировка цели – максимизация прибыли, минимизация себестоимости, минимизация времени изготовления.

Параметры задачи:

n - число различных типов изделий (наименований);

m - число различных типов ресурсов (единиц оборудования);

Т_i – фонд времени работы i–ой единицы оборудования, i = 1, . . ., m;

g_k – число различных способов изготовления изделия к-го наименования, характеризующихся различным временем обработки на единице оборудования i–ого типа, к = 1, . . ., n;

tⁱ_kg  -  время обработки изделия к-го наименования, изготавливаемого g–ым способом на оборудовании i –ого типа, i = 1, . . ., m, к = 1, . . ., n, g = 1,…, g_k..

а_к  - спрос на изделие к-го наименования, к = 1, . . ., n.

S – размер склада для хранения изделий, выраженный в количествах изделий;

С_кg – себестоимость изготовления изделия  к-го наименования g–ым способом, к = 1, . . ., n, g = 1,…, g_k;

С_0к – требуемая себестоимость изготовления изделия  к-го наименования, к = 1, . . ., n;

П_к – прибыль от реализации изделия к-го наименования, к = 1, . . ., n.

Управляющие переменные:

х_кg – число изделий  к-го наименования, выпускаемых g–ым способом, к = 1, . . ., n, g = 1,…, g_k.

Ограничения (область допустимых решений):

- по фонду работы оборудования i = 1, . . ., m.

- по размеру склада

- по спросу к = 1, . . ., n.

по себестоимости изготовления , к = 1, . . ., n;

- по условию неотрицательности управляемой переменной (число изделий)

х_кg ≥ 0, к = 1, . . ., n, g = 1,…, g_k.

Формулировка критериев через параметры и управляющие переменные:

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

П =

Если прибыль нелинейно зависит от числа выпускаемых изделий

П = , где f- нелинейная функция;

- минимизация себестоимости (при отсутствии ограничения на себестоимость)

С = ;

- минимизация суммарного времени обработки (в часах) – станки начинают работать одновременно и работают параллельно

Т = .

Решения исходной задачи по любому из предложенных критериев служат переменные х_кg – число изделий  к-го наименования, выпускаемых g–ым способом, к = 1, . . ., n, g = 1,…, g, которые удовлетворяют ограничениям и доставляют экстремум какому либо критерию.

В результате определяют оптимальный план производства - оптимальный состав производственного заказа изделий.

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