Простейшей и наиболее популярной задачей планирования перевозок является транспортная задача, которую мы разобрали в шестой лекции.
Широкий класс
Рассмотрим распределительную задачу. Эта математическая модель широко освещалась в литературе под самыми различными названиями (обобщенная транспортная задача, задача о взвешенном распределении, $$\lambda$$ -задача, задача о расстановке флота и др.). Опишем ее в следующей интерпретации.
Обобщенная транспортная задача, задача о взвешенном распределении, $$\lambda$$ -задача, задача о расстановке флота и др.
Пусть имеется $$n$$ транспортных линий (скажем, пассажирских); по $$j$$ -й линии нужно выполнить $$b_j$$ рейсов $$(j=1,2,...,n)$$. В наличии имеются транспортные единицы m типов. Резервы полезного времени транспортной единицы типа $$i$$ составляют $$a_i (i=1,2,...,m)$$. На выполнение транспортной единицей типа $$i$$ рейса $$j$$ требуется время $$t_{ij}$$, а затраты на рейс составляют $$c_{ij}$$. Требуется указать наиболее экономную расстановку транспортных единиц по линиям.
Обозначая через $$x_{ij}$$ количество рейсов, которое транспортная единица $$i$$ должна выполнить по линии $$j$$, приходим к следующей задаче. Требуется минимизировать
$$\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} c_{ij} x_{ij}$$
при условиях
$$x_{ij}\ge 0, x_{ij}$$ - целые, $$i=1,2,...,m; j=1,2,..n$$,
$$\sum\limits_{j=1}^{n} t_{ij} x_{ij}\le a_i, i=1,2,...,m$$,
$$\sum\limits_{i=1}^{m} x_{ij} =b_j, j=1,2,...n$$.
Здесь условия (7.3.) выражают ограничения по фондам времени каждой транспортной единицы, а условия (7.4.) говорят о том, что все рейсы должны быть выполнены.
К совершенно аналогичной модели приводит близкая к описанной задача о выборе средства доставки груза.
Пусть через $$i=1,2,...,m$$ обозначены грузообразующие пункты с объемами груза в них $$a_i$$. Имеется средств доставки груза (видов транспорта); грузоподъемность $$j$$ - го средства доставки составляет $$p_j$$, а наличный его парк равен $$N_j, j=1,2,...n$$. Грузы подлежат доставке в один центральный пункт (склад); затраты при осуществлении одной единицей средства доставки $$j$$ рейса от пункта $$i$$ до склада равны $$c_{ij}$$. Требуется составить наиболее экономный план доставки.
Через $$x_{ij}$$ обозначим количество средств доставки типа $$j$$, отправляющееся из пункта $$i$$. Тогда задача сведется к минимизации
$$\sum\limits_{j=1}^{n} p_jx_{ij} \ge a_i, i=1,2,...,m$$,
$$\sum\limits_{i=1}^{m} x_{ij}=N_j, j=1,2,...n$$.
Распределительная задача имеет весьма разнообразные приложения. Большое число практических ее интерпретаций можно найти в монографии Д.Б. Юдина и Е.Г. Гольштейна (Юдин Д.Б., Гольштейн Е.Г., Задачи и методы линейного программирования . Изд. 2-е переработанное и дополненное, М., "Советское радио", 1964.)
Пусть требуется распределить изготовление деталей между станками. Индексом $$j=1,2,...,n$$ будем обозначать детали, индексом $$i=1,2,...,m$$ — станки с резервами рабочего времени $$a_i$$. Пусть плановое задание по деталям задается числами $$b_j$$, штучные нормы времени по обработке $$i$$ -м станком $$j$$ -й детали равны $$t_{ij}$$, а себестоимость при этом составляет $$c_{ij}$$. Требуется составить план распределения работ по станкам, обеспечивающий выполнение задания, не выводящий за пределы резервов времени по каждому станку и минимизирующий суммарную себестоимость.
Обозначим через $$x_{ij}$$ количество деталей типа $$j$$, которое следует обработать на станке $$i$$. Тогда описанная задача распределения программы сведется к модели (7.1.)-(7.4.). Заметим, что во многих интерпретациях распределительной задачи требование целочисленности на переменные может и не накладываться.
Пусть в дополнение к перечисленным выше данным выпуск транспортной единицы типа $$i$$ на линию $$j$$ связан с подготовительными работами, требующими времени $$\tau_{ij}$$ (это время не зависит от числа рейсов, которое предстоит выполнить данной транспортной единице). Денежные затраты на проведение этих подготовительных работ составляют $$d_{ij}$$.
Для отыскания наиболее экономной расстановки транспортных единиц по линиям, как и выше, введем целочисленные переменные $$x_{ij}$$. Тогда суммарные затраты составят
$$\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}c_{ij}(x_{ij})$$,
где
$$c_{ij}(x_{ij})= \left\langle \begin{array}{ccc} 0, x_{ij},\\ c_{ij}x_{ij}+d_{ij}, x_{ij} > 0 \end{array} \right$$
Ограничения по фонду времени каждой транспортной единицы будут теперь иметь вид
$$\sum\limits_{i=1}^{n}t_{ij}(x_{ij})\le a_i, i=1,2,...,m$$,
где
$$t_{ij}(x_{ij})= \left\langle \begin{array}{ccc} 0, x_{ij}=0,\\ t_{ij}x_{ij}+\tau_{ij}, x_{ij} > 0 \end{array} \right$$
Ограничения по рейсам (7.4.), равно как и очевидные ограничения (7.2.), при этом сохраняются. Таким образом, задача заключается в минимизации (7.7.) при условиях (7.2.), (7.4.) и (7.9.)
Из (7.7.) и (7.8.) легко усмотреть, что перед нами задача с фиксированными доплатами; ее отличие от рассматривавшихся ранее задач этого рода состоит в том, что здесь фиксированные доплаты входят не только в целевую функцию, но и в ограничения (7.9.). Однако и этот вариант задачи можно свести к
Пусть грузовой флот имеет в своем составе суда $$n$$ типов. Количество судов типа $$j$$ равно $$q_j$$, а затраты при использовании одного судна типа $$j$$ в планируемом периоде составляют $$c_j, j=1,2,...,n$$. Каждое судно обладает грузовыми емкостями $$m$$ типов (трюмы, танки, палубы и тому подобное); грузоподъемность емкости $$i$$ на судне типа $$j$$ равна $$d_{ij}$$. Подлежат перевозке $$p$$ видов грузов. Груз вида $$k$$ имеется в количестве $$a_k, k=1,2,...,p$$. Требуется выбрать наиболее экономичный комплекс средств доставки этих грузов, совместимый с грузовыми возможностями судов.
Учитывая неделимость транспортных единиц, введем целочисленные переменные $$x_j, j=1,2,...,n$$, которые обозначают количество судов типа $$j$$, выделяемое для перевозки. Кроме того, введем переменные $$y_{ik}$$, которые обозначают количество грузов вида $$k$$, подлежащее загрузке в емкость $$i(i=1,2,...,m;k=1,2,...h)$$. Тогда мы придем к задаче минимизации
$$\sum\limits_{j=1}^{n}c_jx_j$$
при условиях
$$0\le x_j\le q_j, x_j$$ - целое; $$y_{ik}\ge 0$$,
$$\sum\limits_{j=1}^{n}d_{ij}x_j-\sum\limits_{k=1}^{p}y_{ik}\ge 0, i=1,2,...,m$$,
$$\sum\limits_{i=1}^{m}y_{ik}=a_k, k=1,2,...,p$$.
Здесь ограничения (7.13.) показывают, что общее количество груза, загружаемое в емкости каждого типа, не должно превышать суммарной грузоподъемности этих емкостей по всем судам, а ограничения (7.14.) говорят о том, что перевозки по всем грузам должны быть полностью осуществлены. Отметим, что на переменные $$y_{ik}$$ требование целочисленности, вообще говоря, не накладывается, так что здесь мы имеем дело с частично
Пусть некоторая центральная база снабжает продукцией (ее можно считать однородной) m складов. Развозка продукции на склады осуществляется одним грузовиком, причем каждый склад получает свой заказ полностью в один прием –грузоподъемность грузовика для этого достаточна. Вообще же грузовик может одновременно взять груз, соответствующий не более чем $$k$$ заказам. Грузовик может объезжать склады по определенным r маршрутам. Разумеется, один и тот же склад может находиться на разных маршрутах.
Пусть для каждого склада известна функция затрат по доставке в зависимости, скажем, от размера заказа. Требуется составить график развозки, обеспечивающий всех клиентов и минимизирующий суммарные затраты. Подчеркнем, что время доставки здесь никак не учитывается; предполагается, что все операции по доставке заведомо могут быть осуществлены в течение некоторого периода времени, устраивающего всех заказчиков.
Под способом развозки будем понимать любую допустимую комбинацию выполнения заказов. Говоря точнее, способ развозки представляет собой $$m$$ -мерный столбец, $$i$$ -я компонента которого равна единицы, если $$i$$ -й заказ в этом способе удовлетворяется, и равна нулю в противном случае. Для любой реальной задачи при небольших значениях $$m,k,r$$ можно фактически выписать все такие способы развозки. Число $$n$$ этих способов будет зависеть не только от этих параметров, но и, например, от числа складов на каждом маршруте, объема заказов и так далее. Кроме того, каждому способу развозки $$j$$ легко сопоставить связанные с ним затраты $$c_j$$ (учитывающие, помимо упомянутых выше затрат по доставке, также стоимость работ по выгрузке и тому подобное).
Итак, пусть при данных конкретных условиях задачи составлена матрица $$A=||a_{ij}||$$ всевозможных способов развозки, состоящая из нулей и единиц. Столбцы этой матрицы представляют собой описанные выше способы развозки, то есть $$a_{ij}=1$$, если в способе $$j$$ заказ $$i$$ удовлетворяется, и $$a_{ij}=0$$ в противном случае. Кроме того, пусть для каждого способа $$j$$ найдены соответствующие ему затраты $$c_{ij}, j=1,2,...,n$$. Теперь задача состоит в выборе наиболее экономичной комбинации этих способов.
Введем переменные
$$x_j \left\langle \begin{array}{ccc} \text{1, если j-й способ развозки реализуется,} \\ \text{0 в противном случае.} \end{array} \right$$
Теперь мы естественным образом получаем задачу минимизации суммарных затратт
$$\sum\limits_{j=1}^{n}c_jx_j$$ (7.16.)
при условиях (7.15.) и
$$\sum\limits_{i=1}^{n}a_{ij}x_j=1, i=1,2,...,m$$.
Условия (7.17.) означают, что все заказы должны быть удовлетворены.
Обращаем внимание на то, что модель (7.15.)-(7.17.) физически совпадает со взвешанной задачей о покрытии.
Ввиду огромного объема капиталовложений, стоящего за любой реальной задачей этого типа, даже небольшие улучшения первоначальных плановых наметок на деле приводят к серьезному положительному экономическому эффекту.
В связи с важной ролью, которую играет в задачах размещения и специализации пространственный фактор, большинство соответствующих моделей представляет собой варианты и обобщения классической транспортной задачи, хотя, разумеется, проблема отнюдь не исчерпывается лишь установлением схемы рациональных грузопотоков.
Пусть имеется n способов реконструкции уже имеющихся предприятий и строительства новых (речь идет об одной отрасли). Предприятия должны производить m продуктов. При каждом способе реконструкции $$j(j=1,2,...,n)$$ выпуск продукта $$i(i=1,2,...,m)$$ за единицу времени (промежуток планирования) составляет $$a_{ij}$$, а приведенные затраты по реализации этого способа равны $$c_j$$.
Вопрос о реконструкции и новом строительстве рассматривается для $$p$$ предприятий; при этом множество номеров способов реконструкции $$N=N\{1,2,...,n\}$$ разбито на непересекающиеся подмножества $$N=N_1\cup N_2\cup ... \cup N_p$$, так, что $$j \in N_k$$ означает, что способ $$j$$ относится к предприятию $$k(k=1,2,...,p)$$. Все эти способы являются в определенном смысле взаимно исключающими: для каждого предприятия может быть реализован один и только один способ реконструкции (строительства). Требуется выбрать способы реконструкции таким образом, чтобы суммарный выпуск каждого продукта $$i$$ всеми предприятиями был не менее заданной величиной $$b_i$$, а суммарные затраты на реконструкцию и строительства были минимальными.
Введем переменные
$$x_j \left\langle \begin{array}{ccc} \text{1, если j-й способ развозки реализуется,} \\ \text{0 в противном случае.} \end{array} \right$$
Тогда наша задача сведется к минимизации
$$\sum\limits_{j=1}^{n}c_jx_j$$
при условиях
$$\sum\limits_{i=1}^{n}a_{ij}x_j\ge b_i, i=1,2,...,m$$
$$\sum\limits_{j\in N_k}x_j=1,k=1,2,...,p$$.
Здесь условия (7.21.) очевидным образом выражают единственность реализации способа реконструкции (строительства) для каждого из предприятий. Действительно, из (7.18.) и (7.21.) сразу следует, что в пределах каждого $$N_k$$ все $$x_j$$ равны нулю, за исключением одного, равного единице.
Связь модели (7.18.)-(7.21.) с задачами размещения является довольно прозрачной. Действительно, можно считать, что некоторые (или все) предприятия являются не действующими, а лишь проектируемыми, причем для каждого из них возможно осуществление не более одного способа строительства (то есть некоторые предприятия могут вообще не строиться). Тогда для индексов $$k$$, отвечающих проектируемым предприятиям, можно заменить условия (7.21.) неравенствами
$$\sum\limits_{j\in N_k}x_j\le 1,k=1,2,...,p$$.
Теперь для некоторых $$N_k$$ в оптимальном плане могут оказаться равными нулю все $$x_j$$, то есть ни один способ строительства соответствующих предприятий не будет реализован. Тем самым мы получим план размещения новых предприятий.
Описанная модель является достаточно общей; однако она не учитывает потребителей продукции и не отражает затрат на транспортировку продукции от поставщиков к потребителям. Этот момент является наиболее существенным.
В самые последние годы для моделей
Пусть имеется неделимых производственных единиц, которые в дальнейшем мы для краткости будем называть центрами; каждую из этих производственных единиц требуется расположить в одном из $$n$$ возможных мест. Затраты, связанные непосредственно с помещением центра $$i$$ на место $$j$$ ("затраты на установку"), равны $$c_{ij}(i=1,2,...,m;j=1,2,...,n)$$. Известны "расстояния" $$d_{ij}$$ от места $$i$$ до места $$j$$ (числа $$d_{ij}$$ вовсе не обязаны равняться соответствующим геометрическим расстояниям; они являются лишь оценкой затрат, связанных с перемещением из $$i$$ в $$j$$ ). Заданы, кроме того, производственные "потоки" $$f_{ij}$$ из центра $$i$$ в центр $$j$$.
Отметим, что, не умаляя общности, можно положить $$m=n$$. Действительно, в случае $$m < n$$ введем дополнительные фиктивные центры $$m+1,m+2,...,n$$, положив для них $$c_{ij}=0$$ при $$i\ge m+1 и f_{ij}=0$$ при $$i\ge m+1$$ или $$j\ge m+1$$.
Нашей целью является назначение (закрепление) центров по местам, минимизирующее суммарные затраты. Каждое такое назначение представляет собой перестановку $$(p_1,p_2,...p_n)$$ чисел $$(1,2,…,n)$$ ; при этом любое из проводимых закреплений центра $$i$$ за местом $$p_i$$ описывается соответствием $$i\to p_i, i=1,2,...,n$$. Для любого назначения мы имеем, во-первых, затраты на взаимосвязь между парами центров; мы будем предполагать, что эти затраты при помещении центра $$i$$ в место $$p_i$$ и центра $$j$$ в место $$p_j$$ равны произведению
$$\sum\limits_{i=1}^{n}c_{ip_i}+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f_{ij}d_{p_ip_j}$$.
Иногда в подобных задачах накладывается следующее дополнительное требование: каждый центр $$i$$ может быть помещен не в любое место, а лишь в одно из мест из данного списка $$S(i)$$, скажем, по соображениям веса, габаритов и тому подобное. Тогда следует присоединить к задаче условие
$$p_i \in S(i), i=1,2,...,n$$.
В случае независимости производственных центров все $$f_{ij}=0$$, и задача минимизации (7.23.) по всем перестановкам превращается в задачу о назначениях. В этом случае $$c_{ip}$$ можно интерпретировать как своеобразную "меру нежелательности" назначения $$i \to p_i$$ или, попросту говоря, как убытки, связанные с таким назначением. Наоборот, в других задачах можно пренебречь затратами на установку $$c_{ip_i}$$ или считать все эти затраты одинаковыми, так что речь идет только о минимизации суммарных "затрат по взаимодействию", то есть второго слагаемого в (7.23.).
Модель (7.23.)-(7.24.) имеет весьма широкие практические приложения, отражая существенные черты многих современных задач проектирования. Так, она может быть использована в вопросах планирования расстановки оборудования в целях машиностроительных или химических предприятий. С другой стороны, она же может найти применение для задач о проектировании расположения деталей в ячейках вычислительных и управляющих устройств (например, при нахождении схем монтажа платы, минимизирующих суммарную длину соединений). Здесь эта модель описана в нарочито общих терминах в надежде, что различные более конкретные интерпретации читатель этой лекции найдет сам.
Общая задача теории расписаний. В отечественной литературе эту задачу обычно называют задачей календарного планирования. Общую ее схему можно описать следующим образом. Имеется m станков и n деталей, каждая из которых должна пройти обработку на всех станках в определенном порядке. Этот порядок может быть одинаковым для всех деталей либо различным для разных их групп. При этом производственные операции считаются неделимыми (начав обработку детали $$j$$ на станке $$i$$, мы должны довести эту обработку до конца, не имея права прервать ее).
Задана матрица $$A=||a_{ij}||$$, где $$a_{ij}\ge 0$$ — время, необходимое для обработки $$j$$ -й детали на $$i$$ -м станке $$(a_{ij}=0$$ для тех деталей $$j$$, которые не требуют обработки на станке $$i$$ ). Требуется указать такой порядок запуска деталей в обработку, который минимизировал бы общее время выполнения всех работ (длину производственного цикла).
Непосредственному решению (путем перебора всех вариантов) эта задача не поддается, так как при этом уже в простейшем случае одинакового порядка прохождения деталей пришлось бы выбирать наименьшую из $$n$$! величин. При больших $$n$$ это практически неосуществимо даже с использованием быстродействующих электронных машин. Несмотря на огромное прикладное значение этой задачи (описанная модель или ее варианты являются схемами основной массы задач по организации производства), пока удалось получить ее решение только для случая двух машин (алгоритм Джонсона, лекция №17) $$m=2$$. Вместе с тем случай $$m > 2$$ до сих пор доставлял весьма серьезные теоретические и вычислительные затруднения. Постановка задач этого класса в виде целочисленных задач линейного программирования является одним из перспективных путей продвижения в этом направлении.
Известно несколько формулировок задачи теории расписаний в виде целочисленных задач линейного программирования. Опишем одну из возможных постановок для которой является идея А. С. Мэн ( Мэн А.С. Задача календарного планирования для предприятий единичного и мелкосерийного производства. Сб. "Календарное планирование", М. , "Прогресс", 1966, гл.12.).
Не умаляя общности, можно считать $$a_{ij}$$ целыми числами. Составление графика обработки деталей будем связывать с "календарем", "дни" которого занумерованы целыми числами $$0,1,...,T$$, где $$T$$ настолько велико, чтобы заведомо обеспечить возможность обработки всей партии.
Введем неотрицательные целочисленные переменные , принимающие значения $$0,1,...,T$$. Здесь $$x_{ij}$$ указывает "дату" начала обработки $$i$$ -м станком $$j$$ -й детали. Рассмотрим условия, которым должны удовлетворять $$x_{ij}$$.
Прежде всего нужно наложить ограничение, не допускающее одновременной обработки на одном станке двух деталей. Для этого моменты начала обработки любых двух деталей $$j,k$$ должны отстоять по "календарю" не менее чем на длительность обработки той из них, которая запускается первой, то есть
$$x_{ij}-x_{ik} \ge a_{ik}\ или\ x_{ik}-x_{ij}\ge a_{ij}$$
В обычную задачу линейного программирования альтернативное условие типа (7.25.) ввести нельзя. Определим целочисленные переменные $$y_{ijk}$$, принимающие значения 0 или 1. Тогда (7.25.) можно переписать в виде
$$(T+a_{ik})y_{ijk} + (x_{ij} - x_{ik}) \ge a_{ik}$$,
$$(T+a_{ij})(1-y_{ijk}) + (x_{ik} - x_{ij}) \ge a_{ij}$$
Отметим очевидное неравенство $$|x_{ij}-x_{ik}|\le T$$, вытекающее из определения $$T$$. Ясно, что случай $$x_{ij} - x_{ik}=0$$ невозможен, то есть обработка двух разных деталей не может начаться на одном станке одновременно, ибо в этом случае неравенства (7.26.) удовлетворялись бы только при $$y_{ij}=1$$, а неравенства (7.27.) – только при $$y_{ijk}=0$$. Если $$x_{ij}-x_{ik} > 0$$, то $$y_{ijk}$$ в (7.26.) может быть равен нулю или единице, а в (7.27 ) – только нулю, так что единственным возможным значением здесь будет $$y_{ijk}=0$$. Если же $$x_{ij}-x_{ik} > 0$$, то $$y_{ijk}$$ в (7.26.) может быть равен только единице, а в (7.27.) и нулю и единице, так что в этом случае возможно лишь $$y_{ijk}=1$$.
Отсюда ясно, что $$y_{ijk}=0$$, если на $$i$$ -м станке обработка $$k$$ -й детали предшествует обработке $$j$$ -й детали, и $$y_{ijk}=1$$ в противном случае.
Теперь следует отразить условия на заданный технологический порядок прохождения деталями обработки на станках. В данной формулировке в принципе безразлично, является ли этот порядок одинаковым для всех деталей или нет. Именно, если деталь должна быть обработана сначала на станке $$i$$, затем на станке $$l$$, то мы должны иметь
$$x_{lj}-x_{ij}\ge a_{ij}$$.
Отсюда ясно, что случай $$x_{lj}-x_{ij}=0$$, то есть одновременное начало обработки одной детали на двух станках, возможен лишь при $$a_{ij}=0$$, то есть тогда, когда данная деталь на одном из этих станков вообще не должна обрабатываться.
Для некоторых деталей условие упорядочения может налагаться лишь в следующей ослабленной форме: деталь $$j$$ должна пройти обработку на станках $$i_1$$ и $$i_2$$, в любом порядке, затем на станке $$l$$. Тогда условие (7.29.) заменится следующими двумя условиями:
$$x_{lj}-x_{i_1j} \ge a_{i_1 j}, x_{lj}-x_{i_2j}\ge a_{i_2j}$$
Можно дать еще вариант условий этого типа, считая что деталь $$j$$ между обработкой на станках $$i$$ и $$l$$ должна пролежать время $$\tau_{il}^{t}$$ (целое число) . В этом случае
$$x_{lj}-x_{ij}=a_{ij}+\tau_{il}^{j}$$.
Могут быть наложены дополнительные условия "на отправку" (то есть на сроки окончания отдельных работ). Так, если обработка детали $$j$$ на станке $$i$$ должна быть закончена к сроку $$d_{ij}$$, то
$$x_{ij}+a_{ij}\le d_{ij}$$.
В качестве критерия оптимальности принимается минимизация общего времени обработки партии. Пусть $$t(\le T)$$ — дата полного завершения работ. Нужно минимизировать $$t$$ при условиях
$$x_{ij}+a_{ij}\le t, i=1,2,...,m;j=1,2,...,n$$
и при условиях (7.26.), (7.27.), (7.28.) или его вариантах и, возможно, еще при условиях (7.31.).
Всего в этой модели приходится вводить $$p=mn+mC_n^2=mn(1+\frac{n-1}{2})$$ переменных (не считая $$t$$ и свободных переменных). Эти переменные, кроме того, должны быть целочисленными. Для реальных задач даже самых скромных размеров это приводит к весьма громоздким моделям (так, при $$m=5$$
и $$n=10$$ мы получаем $$p=275$$ ).
Однако описанная модель, по-видимому, является одной из наиболее экономных в смысле размеров получающейся
Рассмотрим следующую упрощенную задачу о наилучшем распределении памяти вычислительной машины. Пусть $$П_{ij}$$ — $$j$$ -я стандартная подпрограмма для вычисления функции $$i$$ в библиотеке подпрограмм $$(i=1,2,...,m;j=1,2,...,n)$$. Подпрограмма $$П_{ij}$$ занимает $$p_{ij}$$ ячеек памяти и требует для счета $$t_{ij}$$ секунд. Требуется составить "программу" $$П$$, которая определяется заданием некоторого набора $$I$$ индексов $$i$$, то есть функций, подлежащих вычислению (наличием иных команд пренебрегаем). При этом следует для составления программы $$П$$ указать такой набор подпрограмм $$П_{ij}$$, чтобы длина всей программы не превосходила M ячеек, а время счета по ней было минимальным.
Как обычно в подобных случая, вводим переменные
$$x_{ij}= \left\langle \begin{array}{ccc} \text{1, если }П_{ij}\text{ включается в П}\\ \text{0 в противном случае.} \end{array} \right$$
Тогда наша задача сведется к минимизации
$$\sum\limits_{i=I}\sum\limits_{j=1}^{n} t_{ij}x_{ij}$$
при условиях
$$\sum\limits_{i=1}^{n}x_{ij},i \in I; \sum\limits_{i \in I}\sum\limits_{j=1}^{n} p_{ij}x_{ij} \le M$$.
Рассмотрим финансирование исследовательских проектов. Пусть на протяжении $$T$$ лет возможно осуществление исследовательских проектов. Ожидаемый эффект проекта $$j$$, выраженный в "сегодняшних" единицах полезности, составляет $$c_j,j=1,2,...n$$. Затраты в год $$i$$ на осуществление проекта $$j$$ составляют $$a_{ij}$$, а общий лимит капиталовложений на исследования в году $$i$$ равен $$b_i, i=1,2,...,T$$. Требуется указать максимально эффективный набор проектов, не выводящий за пределы отпускаемых вложений.
Формализация этой задачи очевидна: если обычным образом ввест переменные
$$x_j \left\langle \begin{array}{ccc} \text{1, если проект j осуществляется,}\\ \text{0 в противном случае,} \end{array} \right$$
то мы придем к задаче максимизации
$$\sum\limits_{j=1}^{n} c_jx_j$$
при условиях
$$i=1\sum\limits^{n} a_{ij}x_j\le b_i, i=1,2,...,T$$.
Рассмотрим следующую упрощенную статическую модель распределения тракторных работ (Корбут А.А. Целочисленные задачи линейного программирования. В сб. "Эконом.-матем. методы", вып. 2, М., "Наука", 1965, 141-186.).
Имеется n типов сельскохозяйственных машин и m видов работ, подлежащих выполнению в объемах $$b_i$$, $$i=1,2,...,m$$ (будем считать, что все эти объемы выражены в гектарах). Заданы производительность $$j$$ -й машины на $$i$$ -й работе $$a_{ij}$$, а также себестоимость $$d_{ij}$$ обработки одного гектара работы $$i$$ машиной $$j$$. Себестоимость самих машин (скажем, стоимость их покупки или аренды, взятая с некоторым коэффициентом приведения) составляет $$c_j? j =1,2,...,n$$. Следует найти оптимальный машинный парк для данного комплекса работ и указать его распределение по работам. Чтобы выполнить задание и добиться минимальной суммарной себестоимости, обозначим через $$x_{ij}$$ количество машин каждого типа, а через $$y_{ij}$$ — количество машин типа $$j$$, которое будет выделено на работу $$i$$. Тогда наша задача сведется к минимизации
$$\sum c_{jxj} + \sum\limits_{i=1}^{m}b_i\sum\limits_{j=1}^{n}d_{ij}y_{ij}$$
при условиях
$$x_j\ge 0, x_j\text{ — целые; }y_{ij}\ge 0,y_{ij}\text{ — целые,}$$
$$x_j - \sum\limits_{i=1}^{m} y_{ij} \ge 0, j=1,2,...,n;\\ \sum\limits_{i=1}^{n} a_{ij}y_{ij}=b_i,i=1,2,...,m $$
Отметим, что накладывать условие целочисленности на $$y_{ij}$$ не обязательно, так как нецелые $$y_{ij}$$ здесь вполне поддаются разумной интерпретации.
Таким образом, перед нами еще один пример задачи с неделимостями. Модель эта существенно усложнится, если дополнительно потребовать выполнения каждой работы в отведенные для нее агротехнические сроки; здесь мы не будем на этом останавливаться.
Простейшей и наиболее популярной задачей планирования перевозок является транспортная задача, которую мы разобрали в шестой лекции.
Широкий класс
Рассмотрим распределительную задачу. Эта математическая модель широко освещалась в литературе под самыми различными названиями (обобщенная транспортная задача, задача о взвешенном распределении, $$\lambda$$ -задача, задача о расстановке флота и др.). Опишем ее в следующей интерпретации.
Обобщенная транспортная задача, задача о взвешенном распределении, $$\lambda$$ -задача, задача о расстановке флота и др.
Пусть имеется $$n$$ транспортных линий (скажем, пассажирских); по $$j$$ -й линии нужно выполнить $$b_j$$ рейсов $$(j=1,2,...,n)$$. В наличии имеются транспортные единицы m типов. Резервы полезного времени транспортной единицы типа $$i$$ составляют $$a_i (i=1,2,...,m)$$. На выполнение транспортной единицей типа $$i$$ рейса $$j$$ требуется время $$t_{ij}$$, а затраты на рейс составляют $$c_{ij}$$. Требуется указать наиболее экономную расстановку транспортных единиц по линиям.
Обозначая через $$x_{ij}$$ количество рейсов, которое транспортная единица $$i$$ должна выполнить по линии $$j$$, приходим к следующей задаче. Требуется минимизировать
$$\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} c_{ij} x_{ij}$$
при условиях
$$x_{ij}\ge 0, x_{ij}$$ - целые, $$i=1,2,...,m; j=1,2,..n$$,
$$\sum\limits_{j=1}^{n} t_{ij} x_{ij}\le a_i, i=1,2,...,m$$,
$$\sum\limits_{i=1}^{m} x_{ij} =b_j, j=1,2,...n$$.
Здесь условия (7.3.) выражают ограничения по фондам времени каждой транспортной единицы, а условия (7.4.) говорят о том, что все рейсы должны быть выполнены.
К совершенно аналогичной модели приводит близкая к описанной задача о выборе средства доставки груза.
Пусть через $$i=1,2,...,m$$ обозначены грузообразующие пункты с объемами груза в них $$a_i$$. Имеется средств доставки груза (видов транспорта); грузоподъемность $$j$$ - го средства доставки составляет $$p_j$$, а наличный его парк равен $$N_j, j=1,2,...n$$. Грузы подлежат доставке в один центральный пункт (склад); затраты при осуществлении одной единицей средства доставки $$j$$ рейса от пункта $$i$$ до склада равны $$c_{ij}$$. Требуется составить наиболее экономный план доставки.
Через $$x_{ij}$$ обозначим количество средств доставки типа $$j$$, отправляющееся из пункта $$i$$. Тогда задача сведется к минимизации
$$\sum\limits_{j=1}^{n} p_jx_{ij} \ge a_i, i=1,2,...,m$$,
$$\sum\limits_{i=1}^{m} x_{ij}=N_j, j=1,2,...n$$.
Распределительная задача имеет весьма разнообразные приложения. Большое число практических ее интерпретаций можно найти в монографии Д.Б. Юдина и Е.Г. Гольштейна (Юдин Д.Б., Гольштейн Е.Г., Задачи и методы линейного программирования . Изд. 2-е переработанное и дополненное, М., "Советское радио", 1964.)
Пусть требуется распределить изготовление деталей между станками. Индексом $$j=1,2,...,n$$ будем обозначать детали, индексом $$i=1,2,...,m$$ — станки с резервами рабочего времени $$a_i$$. Пусть плановое задание по деталям задается числами $$b_j$$, штучные нормы времени по обработке $$i$$ -м станком $$j$$ -й детали равны $$t_{ij}$$, а себестоимость при этом составляет $$c_{ij}$$. Требуется составить план распределения работ по станкам, обеспечивающий выполнение задания, не выводящий за пределы резервов времени по каждому станку и минимизирующий суммарную себестоимость.
Обозначим через $$x_{ij}$$ количество деталей типа $$j$$, которое следует обработать на станке $$i$$. Тогда описанная задача распределения программы сведется к модели (7.1.)-(7.4.). Заметим, что во многих интерпретациях распределительной задачи требование целочисленности на переменные может и не накладываться.
Пусть в дополнение к перечисленным выше данным выпуск транспортной единицы типа $$i$$ на линию $$j$$ связан с подготовительными работами, требующими времени $$\tau_{ij}$$ (это время не зависит от числа рейсов, которое предстоит выполнить данной транспортной единице). Денежные затраты на проведение этих подготовительных работ составляют $$d_{ij}$$.
Для отыскания наиболее экономной расстановки транспортных единиц по линиям, как и выше, введем целочисленные переменные $$x_{ij}$$. Тогда суммарные затраты составят
$$\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}c_{ij}(x_{ij})$$,
где
$$c_{ij}(x_{ij})= \left\langle \begin{array}{ccc} 0, x_{ij},\\ c_{ij}x_{ij}+d_{ij}, x_{ij} > 0 \end{array} \right$$
Ограничения по фонду времени каждой транспортной единицы будут теперь иметь вид
$$\sum\limits_{i=1}^{n}t_{ij}(x_{ij})\le a_i, i=1,2,...,m$$,
где
$$t_{ij}(x_{ij})= \left\langle \begin{array}{ccc} 0, x_{ij}=0,\\ t_{ij}x_{ij}+\tau_{ij}, x_{ij} > 0 \end{array} \right$$
Ограничения по рейсам (7.4.), равно как и очевидные ограничения (7.2.), при этом сохраняются. Таким образом, задача заключается в минимизации (7.7.) при условиях (7.2.), (7.4.) и (7.9.)
Из (7.7.) и (7.8.) легко усмотреть, что перед нами задача с фиксированными доплатами; ее отличие от рассматривавшихся ранее задач этого рода состоит в том, что здесь фиксированные доплаты входят не только в целевую функцию, но и в ограничения (7.9.). Однако и этот вариант задачи можно свести к
Пусть грузовой флот имеет в своем составе суда $$n$$ типов. Количество судов типа $$j$$ равно $$q_j$$, а затраты при использовании одного судна типа $$j$$ в планируемом периоде составляют $$c_j, j=1,2,...,n$$. Каждое судно обладает грузовыми емкостями $$m$$ типов (трюмы, танки, палубы и тому подобное); грузоподъемность емкости $$i$$ на судне типа $$j$$ равна $$d_{ij}$$. Подлежат перевозке $$p$$ видов грузов. Груз вида $$k$$ имеется в количестве $$a_k, k=1,2,...,p$$. Требуется выбрать наиболее экономичный комплекс средств доставки этих грузов, совместимый с грузовыми возможностями судов.
Учитывая неделимость транспортных единиц, введем целочисленные переменные $$x_j, j=1,2,...,n$$, которые обозначают количество судов типа $$j$$, выделяемое для перевозки. Кроме того, введем переменные $$y_{ik}$$, которые обозначают количество грузов вида $$k$$, подлежащее загрузке в емкость $$i(i=1,2,...,m;k=1,2,...h)$$. Тогда мы придем к задаче минимизации
$$\sum\limits_{j=1}^{n}c_jx_j$$
при условиях
$$0\le x_j\le q_j, x_j$$ - целое; $$y_{ik}\ge 0$$,
$$\sum\limits_{j=1}^{n}d_{ij}x_j-\sum\limits_{k=1}^{p}y_{ik}\ge 0, i=1,2,...,m$$,
$$\sum\limits_{i=1}^{m}y_{ik}=a_k, k=1,2,...,p$$.
Здесь ограничения (7.13.) показывают, что общее количество груза, загружаемое в емкости каждого типа, не должно превышать суммарной грузоподъемности этих емкостей по всем судам, а ограничения (7.14.) говорят о том, что перевозки по всем грузам должны быть полностью осуществлены. Отметим, что на переменные $$y_{ik}$$ требование целочисленности, вообще говоря, не накладывается, так что здесь мы имеем дело с частично
Пусть некоторая центральная база снабжает продукцией (ее можно считать однородной) m складов. Развозка продукции на склады осуществляется одним грузовиком, причем каждый склад получает свой заказ полностью в один прием –грузоподъемность грузовика для этого достаточна. Вообще же грузовик может одновременно взять груз, соответствующий не более чем $$k$$ заказам. Грузовик может объезжать склады по определенным r маршрутам. Разумеется, один и тот же склад может находиться на разных маршрутах.
Пусть для каждого склада известна функция затрат по доставке в зависимости, скажем, от размера заказа. Требуется составить график развозки, обеспечивающий всех клиентов и минимизирующий суммарные затраты. Подчеркнем, что время доставки здесь никак не учитывается; предполагается, что все операции по доставке заведомо могут быть осуществлены в течение некоторого периода времени, устраивающего всех заказчиков.
Под способом развозки будем понимать любую допустимую комбинацию выполнения заказов. Говоря точнее, способ развозки представляет собой $$m$$ -мерный столбец, $$i$$ -я компонента которого равна единицы, если $$i$$ -й заказ в этом способе удовлетворяется, и равна нулю в противном случае. Для любой реальной задачи при небольших значениях $$m,k,r$$ можно фактически выписать все такие способы развозки. Число $$n$$ этих способов будет зависеть не только от этих параметров, но и, например, от числа складов на каждом маршруте, объема заказов и так далее. Кроме того, каждому способу развозки $$j$$ легко сопоставить связанные с ним затраты $$c_j$$ (учитывающие, помимо упомянутых выше затрат по доставке, также стоимость работ по выгрузке и тому подобное).
Итак, пусть при данных конкретных условиях задачи составлена матрица $$A=||a_{ij}||$$ всевозможных способов развозки, состоящая из нулей и единиц. Столбцы этой матрицы представляют собой описанные выше способы развозки, то есть $$a_{ij}=1$$, если в способе $$j$$ заказ $$i$$ удовлетворяется, и $$a_{ij}=0$$ в противном случае. Кроме того, пусть для каждого способа $$j$$ найдены соответствующие ему затраты $$c_{ij}, j=1,2,...,n$$. Теперь задача состоит в выборе наиболее экономичной комбинации этих способов.
Введем переменные
$$x_j \left\langle \begin{array}{ccc} \text{1, если j-й способ развозки реализуется,} \\ \text{0 в противном случае.} \end{array} \right$$
Теперь мы естественным образом получаем задачу минимизации суммарных затратт
$$\sum\limits_{j=1}^{n}c_jx_j$$ (7.16.)
при условиях (7.15.) и
$$\sum\limits_{i=1}^{n}a_{ij}x_j=1, i=1,2,...,m$$.
Условия (7.17.) означают, что все заказы должны быть удовлетворены.
Обращаем внимание на то, что модель (7.15.)-(7.17.) физически совпадает со взвешанной задачей о покрытии.
Ввиду огромного объема капиталовложений, стоящего за любой реальной задачей этого типа, даже небольшие улучшения первоначальных плановых наметок на деле приводят к серьезному положительному экономическому эффекту.
В связи с важной ролью, которую играет в задачах размещения и специализации пространственный фактор, большинство соответствующих моделей представляет собой варианты и обобщения классической транспортной задачи, хотя, разумеется, проблема отнюдь не исчерпывается лишь установлением схемы рациональных грузопотоков.
Пусть имеется n способов реконструкции уже имеющихся предприятий и строительства новых (речь идет об одной отрасли). Предприятия должны производить m продуктов. При каждом способе реконструкции $$j(j=1,2,...,n)$$ выпуск продукта $$i(i=1,2,...,m)$$ за единицу времени (промежуток планирования) составляет $$a_{ij}$$, а приведенные затраты по реализации этого способа равны $$c_j$$.
Вопрос о реконструкции и новом строительстве рассматривается для $$p$$ предприятий; при этом множество номеров способов реконструкции $$N=N\{1,2,...,n\}$$ разбито на непересекающиеся подмножества $$N=N_1\cup N_2\cup ... \cup N_p$$, так, что $$j \in N_k$$ означает, что способ $$j$$ относится к предприятию $$k(k=1,2,...,p)$$. Все эти способы являются в определенном смысле взаимно исключающими: для каждого предприятия может быть реализован один и только один способ реконструкции (строительства). Требуется выбрать способы реконструкции таким образом, чтобы суммарный выпуск каждого продукта $$i$$ всеми предприятиями был не менее заданной величиной $$b_i$$, а суммарные затраты на реконструкцию и строительства были минимальными.
Введем переменные
$$x_j \left\langle \begin{array}{ccc} \text{1, если j-й способ развозки реализуется,} \\ \text{0 в противном случае.} \end{array} \right$$
Тогда наша задача сведется к минимизации
$$\sum\limits_{j=1}^{n}c_jx_j$$
при условиях
$$\sum\limits_{i=1}^{n}a_{ij}x_j\ge b_i, i=1,2,...,m$$
$$\sum\limits_{j\in N_k}x_j=1,k=1,2,...,p$$.
Здесь условия (7.21.) очевидным образом выражают единственность реализации способа реконструкции (строительства) для каждого из предприятий. Действительно, из (7.18.) и (7.21.) сразу следует, что в пределах каждого $$N_k$$ все $$x_j$$ равны нулю, за исключением одного, равного единице.
Связь модели (7.18.)-(7.21.) с задачами размещения является довольно прозрачной. Действительно, можно считать, что некоторые (или все) предприятия являются не действующими, а лишь проектируемыми, причем для каждого из них возможно осуществление не более одного способа строительства (то есть некоторые предприятия могут вообще не строиться). Тогда для индексов $$k$$, отвечающих проектируемым предприятиям, можно заменить условия (7.21.) неравенствами
$$\sum\limits_{j\in N_k}x_j\le 1,k=1,2,...,p$$.
Теперь для некоторых $$N_k$$ в оптимальном плане могут оказаться равными нулю все $$x_j$$, то есть ни один способ строительства соответствующих предприятий не будет реализован. Тем самым мы получим план размещения новых предприятий.
Описанная модель является достаточно общей; однако она не учитывает потребителей продукции и не отражает затрат на транспортировку продукции от поставщиков к потребителям. Этот момент является наиболее существенным.
В самые последние годы для моделей
Пусть имеется неделимых производственных единиц, которые в дальнейшем мы для краткости будем называть центрами; каждую из этих производственных единиц требуется расположить в одном из $$n$$ возможных мест. Затраты, связанные непосредственно с помещением центра $$i$$ на место $$j$$ ("затраты на установку"), равны $$c_{ij}(i=1,2,...,m;j=1,2,...,n)$$. Известны "расстояния" $$d_{ij}$$ от места $$i$$ до места $$j$$ (числа $$d_{ij}$$ вовсе не обязаны равняться соответствующим геометрическим расстояниям; они являются лишь оценкой затрат, связанных с перемещением из $$i$$ в $$j$$ ). Заданы, кроме того, производственные "потоки" $$f_{ij}$$ из центра $$i$$ в центр $$j$$.
Отметим, что, не умаляя общности, можно положить $$m=n$$. Действительно, в случае $$m < n$$ введем дополнительные фиктивные центры $$m+1,m+2,...,n$$, положив для них $$c_{ij}=0$$ при $$i\ge m+1 и f_{ij}=0$$ при $$i\ge m+1$$ или $$j\ge m+1$$.
Нашей целью является назначение (закрепление) центров по местам, минимизирующее суммарные затраты. Каждое такое назначение представляет собой перестановку $$(p_1,p_2,...p_n)$$ чисел $$(1,2,…,n)$$ ; при этом любое из проводимых закреплений центра $$i$$ за местом $$p_i$$ описывается соответствием $$i\to p_i, i=1,2,...,n$$. Для любого назначения мы имеем, во-первых, затраты на взаимосвязь между парами центров; мы будем предполагать, что эти затраты при помещении центра $$i$$ в место $$p_i$$ и центра $$j$$ в место $$p_j$$ равны произведению
$$\sum\limits_{i=1}^{n}c_{ip_i}+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f_{ij}d_{p_ip_j}$$.
Иногда в подобных задачах накладывается следующее дополнительное требование: каждый центр $$i$$ может быть помещен не в любое место, а лишь в одно из мест из данного списка $$S(i)$$, скажем, по соображениям веса, габаритов и тому подобное. Тогда следует присоединить к задаче условие
$$p_i \in S(i), i=1,2,...,n$$.
В случае независимости производственных центров все $$f_{ij}=0$$, и задача минимизации (7.23.) по всем перестановкам превращается в задачу о назначениях. В этом случае $$c_{ip}$$ можно интерпретировать как своеобразную "меру нежелательности" назначения $$i \to p_i$$ или, попросту говоря, как убытки, связанные с таким назначением. Наоборот, в других задачах можно пренебречь затратами на установку $$c_{ip_i}$$ или считать все эти затраты одинаковыми, так что речь идет только о минимизации суммарных "затрат по взаимодействию", то есть второго слагаемого в (7.23.).
Модель (7.23.)-(7.24.) имеет весьма широкие практические приложения, отражая существенные черты многих современных задач проектирования. Так, она может быть использована в вопросах планирования расстановки оборудования в целях машиностроительных или химических предприятий. С другой стороны, она же может найти применение для задач о проектировании расположения деталей в ячейках вычислительных и управляющих устройств (например, при нахождении схем монтажа платы, минимизирующих суммарную длину соединений). Здесь эта модель описана в нарочито общих терминах в надежде, что различные более конкретные интерпретации читатель этой лекции найдет сам.
Общая задача теории расписаний. В отечественной литературе эту задачу обычно называют задачей календарного планирования. Общую ее схему можно описать следующим образом. Имеется m станков и n деталей, каждая из которых должна пройти обработку на всех станках в определенном порядке. Этот порядок может быть одинаковым для всех деталей либо различным для разных их групп. При этом производственные операции считаются неделимыми (начав обработку детали $$j$$ на станке $$i$$, мы должны довести эту обработку до конца, не имея права прервать ее).
Задана матрица $$A=||a_{ij}||$$, где $$a_{ij}\ge 0$$ — время, необходимое для обработки $$j$$ -й детали на $$i$$ -м станке $$(a_{ij}=0$$ для тех деталей $$j$$, которые не требуют обработки на станке $$i$$ ). Требуется указать такой порядок запуска деталей в обработку, который минимизировал бы общее время выполнения всех работ (длину производственного цикла).
Непосредственному решению (путем перебора всех вариантов) эта задача не поддается, так как при этом уже в простейшем случае одинакового порядка прохождения деталей пришлось бы выбирать наименьшую из $$n$$! величин. При больших $$n$$ это практически неосуществимо даже с использованием быстродействующих электронных машин. Несмотря на огромное прикладное значение этой задачи (описанная модель или ее варианты являются схемами основной массы задач по организации производства), пока удалось получить ее решение только для случая двух машин (алгоритм Джонсона, лекция №17) $$m=2$$. Вместе с тем случай $$m > 2$$ до сих пор доставлял весьма серьезные теоретические и вычислительные затруднения. Постановка задач этого класса в виде целочисленных задач линейного программирования является одним из перспективных путей продвижения в этом направлении.
Известно несколько формулировок задачи теории расписаний в виде целочисленных задач линейного программирования. Опишем одну из возможных постановок для которой является идея А. С. Мэн ( Мэн А.С. Задача календарного планирования для предприятий единичного и мелкосерийного производства. Сб. "Календарное планирование", М. , "Прогресс", 1966, гл.12.).
Не умаляя общности, можно считать $$a_{ij}$$ целыми числами. Составление графика обработки деталей будем связывать с "календарем", "дни" которого занумерованы целыми числами $$0,1,...,T$$, где $$T$$ настолько велико, чтобы заведомо обеспечить возможность обработки всей партии.
Введем неотрицательные целочисленные переменные , принимающие значения $$0,1,...,T$$. Здесь $$x_{ij}$$ указывает "дату" начала обработки $$i$$ -м станком $$j$$ -й детали. Рассмотрим условия, которым должны удовлетворять $$x_{ij}$$.
Прежде всего нужно наложить ограничение, не допускающее одновременной обработки на одном станке двух деталей. Для этого моменты начала обработки любых двух деталей $$j,k$$ должны отстоять по "календарю" не менее чем на длительность обработки той из них, которая запускается первой, то есть
$$x_{ij}-x_{ik} \ge a_{ik}\ или\ x_{ik}-x_{ij}\ge a_{ij}$$
В обычную задачу линейного программирования альтернативное условие типа (7.25.) ввести нельзя. Определим целочисленные переменные $$y_{ijk}$$, принимающие значения 0 или 1. Тогда (7.25.) можно переписать в виде
$$(T+a_{ik})y_{ijk} + (x_{ij} - x_{ik}) \ge a_{ik}$$,
$$(T+a_{ij})(1-y_{ijk}) + (x_{ik} - x_{ij}) \ge a_{ij}$$
Отметим очевидное неравенство $$|x_{ij}-x_{ik}|\le T$$, вытекающее из определения $$T$$. Ясно, что случай $$x_{ij} - x_{ik}=0$$ невозможен, то есть обработка двух разных деталей не может начаться на одном станке одновременно, ибо в этом случае неравенства (7.26.) удовлетворялись бы только при $$y_{ij}=1$$, а неравенства (7.27.) – только при $$y_{ijk}=0$$. Если $$x_{ij}-x_{ik} > 0$$, то $$y_{ijk}$$ в (7.26.) может быть равен нулю или единице, а в (7.27 ) – только нулю, так что единственным возможным значением здесь будет $$y_{ijk}=0$$. Если же $$x_{ij}-x_{ik} > 0$$, то $$y_{ijk}$$ в (7.26.) может быть равен только единице, а в (7.27.) и нулю и единице, так что в этом случае возможно лишь $$y_{ijk}=1$$.
Отсюда ясно, что $$y_{ijk}=0$$, если на $$i$$ -м станке обработка $$k$$ -й детали предшествует обработке $$j$$ -й детали, и $$y_{ijk}=1$$ в противном случае.
Теперь следует отразить условия на заданный технологический порядок прохождения деталями обработки на станках. В данной формулировке в принципе безразлично, является ли этот порядок одинаковым для всех деталей или нет. Именно, если деталь должна быть обработана сначала на станке $$i$$, затем на станке $$l$$, то мы должны иметь
$$x_{lj}-x_{ij}\ge a_{ij}$$.
Отсюда ясно, что случай $$x_{lj}-x_{ij}=0$$, то есть одновременное начало обработки одной детали на двух станках, возможен лишь при $$a_{ij}=0$$, то есть тогда, когда данная деталь на одном из этих станков вообще не должна обрабатываться.
Для некоторых деталей условие упорядочения может налагаться лишь в следующей ослабленной форме: деталь $$j$$ должна пройти обработку на станках $$i_1$$ и $$i_2$$, в любом порядке, затем на станке $$l$$. Тогда условие (7.29.) заменится следующими двумя условиями:
$$x_{lj}-x_{i_1j} \ge a_{i_1 j}, x_{lj}-x_{i_2j}\ge a_{i_2j}$$
Можно дать еще вариант условий этого типа, считая что деталь $$j$$ между обработкой на станках $$i$$ и $$l$$ должна пролежать время $$\tau_{il}^{t}$$ (целое число) . В этом случае
$$x_{lj}-x_{ij}=a_{ij}+\tau_{il}^{j}$$.
Могут быть наложены дополнительные условия "на отправку" (то есть на сроки окончания отдельных работ). Так, если обработка детали $$j$$ на станке $$i$$ должна быть закончена к сроку $$d_{ij}$$, то
$$x_{ij}+a_{ij}\le d_{ij}$$.
В качестве критерия оптимальности принимается минимизация общего времени обработки партии. Пусть $$t(\le T)$$ — дата полного завершения работ. Нужно минимизировать $$t$$ при условиях
$$x_{ij}+a_{ij}\le t, i=1,2,...,m;j=1,2,...,n$$
и при условиях (7.26.), (7.27.), (7.28.) или его вариантах и, возможно, еще при условиях (7.31.).
Всего в этой модели приходится вводить $$p=mn+mC_n^2=mn(1+\frac{n-1}{2})$$ переменных (не считая $$t$$ и свободных переменных). Эти переменные, кроме того, должны быть целочисленными. Для реальных задач даже самых скромных размеров это приводит к весьма громоздким моделям (так, при $$m=5$$
и $$n=10$$ мы получаем $$p=275$$ ).
Однако описанная модель, по-видимому, является одной из наиболее экономных в смысле размеров получающейся
Рассмотрим следующую упрощенную задачу о наилучшем распределении памяти вычислительной машины. Пусть $$П_{ij}$$ — $$j$$ -я стандартная подпрограмма для вычисления функции $$i$$ в библиотеке подпрограмм $$(i=1,2,...,m;j=1,2,...,n)$$. Подпрограмма $$П_{ij}$$ занимает $$p_{ij}$$ ячеек памяти и требует для счета $$t_{ij}$$ секунд. Требуется составить "программу" $$П$$, которая определяется заданием некоторого набора $$I$$ индексов $$i$$, то есть функций, подлежащих вычислению (наличием иных команд пренебрегаем). При этом следует для составления программы $$П$$ указать такой набор подпрограмм $$П_{ij}$$, чтобы длина всей программы не превосходила M ячеек, а время счета по ней было минимальным.
Как обычно в подобных случая, вводим переменные
$$x_{ij}= \left\langle \begin{array}{ccc} \text{1, если }П_{ij}\text{ включается в П}\\ \text{0 в противном случае.} \end{array} \right$$
Тогда наша задача сведется к минимизации
$$\sum\limits_{i=I}\sum\limits_{j=1}^{n} t_{ij}x_{ij}$$
при условиях
$$\sum\limits_{i=1}^{n}x_{ij},i \in I; \sum\limits_{i \in I}\sum\limits_{j=1}^{n} p_{ij}x_{ij} \le M$$.
Рассмотрим финансирование исследовательских проектов. Пусть на протяжении $$T$$ лет возможно осуществление исследовательских проектов. Ожидаемый эффект проекта $$j$$, выраженный в "сегодняшних" единицах полезности, составляет $$c_j,j=1,2,...n$$. Затраты в год $$i$$ на осуществление проекта $$j$$ составляют $$a_{ij}$$, а общий лимит капиталовложений на исследования в году $$i$$ равен $$b_i, i=1,2,...,T$$. Требуется указать максимально эффективный набор проектов, не выводящий за пределы отпускаемых вложений.
Формализация этой задачи очевидна: если обычным образом ввест переменные
$$x_j \left\langle \begin{array}{ccc} \text{1, если проект j осуществляется,}\\ \text{0 в противном случае,} \end{array} \right$$
то мы придем к задаче максимизации
$$\sum\limits_{j=1}^{n} c_jx_j$$
при условиях
$$i=1\sum\limits^{n} a_{ij}x_j\le b_i, i=1,2,...,T$$.
Рассмотрим следующую упрощенную статическую модель распределения тракторных работ (Корбут А.А. Целочисленные задачи линейного программирования. В сб. "Эконом.-матем. методы", вып. 2, М., "Наука", 1965, 141-186.).
Имеется n типов сельскохозяйственных машин и m видов работ, подлежащих выполнению в объемах $$b_i$$, $$i=1,2,...,m$$ (будем считать, что все эти объемы выражены в гектарах). Заданы производительность $$j$$ -й машины на $$i$$ -й работе $$a_{ij}$$, а также себестоимость $$d_{ij}$$ обработки одного гектара работы $$i$$ машиной $$j$$. Себестоимость самих машин (скажем, стоимость их покупки или аренды, взятая с некоторым коэффициентом приведения) составляет $$c_j? j =1,2,...,n$$. Следует найти оптимальный машинный парк для данного комплекса работ и указать его распределение по работам. Чтобы выполнить задание и добиться минимальной суммарной себестоимости, обозначим через $$x_{ij}$$ количество машин каждого типа, а через $$y_{ij}$$ — количество машин типа $$j$$, которое будет выделено на работу $$i$$. Тогда наша задача сведется к минимизации
$$\sum c_{jxj} + \sum\limits_{i=1}^{m}b_i\sum\limits_{j=1}^{n}d_{ij}y_{ij}$$
при условиях
$$x_j\ge 0, x_j\text{ — целые; }y_{ij}\ge 0,y_{ij}\text{ — целые,}$$
$$x_j - \sum\limits_{i=1}^{m} y_{ij} \ge 0, j=1,2,...,n;\\ \sum\limits_{i=1}^{n} a_{ij}y_{ij}=b_i,i=1,2,...,m $$
Отметим, что накладывать условие целочисленности на $$y_{ij}$$ не обязательно, так как нецелые $$y_{ij}$$ здесь вполне поддаются разумной интерпретации.
Таким образом, перед нами еще один пример задачи с неделимостями. Модель эта существенно усложнится, если дополнительно потребовать выполнения каждой работы в отведенные для нее агротехнические сроки; здесь мы не будем на этом останавливаться.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.