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

1.  n – количество ресурсов, m – количество работ.

2.  a_i = 1 – единичное количество ресурса A_i (i =1,n), например: один работник; одно транспортное средство; одна научная тема и т.д.

3.  b_j = 1 – единичное количество работы B_j (j =1,m), например: одна должность; один маршрут; одна лаборатория.

4.  c_ij – характеристика качества выполнения работы B_j с помощью ресурса А_i. Например, компетентность i-го работника при работе на j-й должности; время, за котороеi-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры

1.  x_ij – факт назначения или неназначения ресурса А_i на работу B_j:

2. L(X) – общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 3.1

Общий вид транспортной матрицы задачи о назначениях
Ресурсы, Ai	Работы, B1				Количество ресурсов
	B1	B2	…	Bm
A1	c11	c12	…	c1m	1
A2	c21	c22	…	c2m	1
…	…	…	…	…	…
An	cn1	cn2	…	cnm	1
Количество работ	1	1	…	1

Модель задачи о назначениях

(3.1)

В некоторых случаях, например, когда c_ij – это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ, в отличие от (3.1). В этом случае ЦФ L(X) заменяют на L₁(X) = – L(X) и решают задачу с ЦФ L₁(X) → min, что равносильно решению задачи с ЦФ L(X) → max.

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

Алгоритм венгерского метода.

1. В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки.

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

3. Если после выполнения первого и второго пункта не получено допустимое решение (в том смысле, что каждому работнику назначена в точности одна работа) выполняем следующие действия:

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

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

   • Если новое распределение нулевых элементов не позволяет построить допустимое решение повторите пункт 3. В противном случае перейдите к пункту 4.

4. Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем этапе.

Замечание. Случай максимизации целевой функции сводится к задаче минимизации для матрицы, полученной из исходной матрицы умножением каждого элемента на –1.

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

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

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

х_ij = 0 или 1,

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

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

Основным методом решения задачи коммивояжера является метод ветвей и границ.

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

База	Потребитель	Потребитель	Потребитель	Потребитель
	1	2	3	4
A	68	72	75	83
B	56	60	58	63
C	38	40	35	45
D	47	42	40	45

Вычтем минимальные элементы по строкам (выделены полужирным), получим новую таблицу:

	1	2	3	4
A	0	4	7	15
B	0	4	2	7
C	3	5	0	10
D	7	2	0	5

Повторим ту же процедуру для столбцов:

	1	2	3	4
A	0	2	7	10
B	0	2	2	2
C	3	3	0	5
D	7	0	0	0

На рисунке ниже приведено окончательное решение задачи. В результате в начальной таблице суммируются клетки, соответствующие выбранным элементам итоговой таблицы (по диагонали - 68+60+35+45=208), это и будет минимальное решение данной задачи. Для решения такой же задачи на максимум необходимо первоначальные значения умножить на (-1), после чего производить решение по приведенному выше алгоритму.

Билет 24.Общая распределительная задача и её частные случаи. Сведение к транспортной задаче.

Общая распределительная задача ЛП – это РЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов.

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

1)     n – количество исполнителей;

2)     m – количество видов выполняемых работ;

3)       – запас рабочего ресурса исполнителя   ( )  [ед.ресурса];

4)       – план по выполнению работы   ( )  [ед. работ];

5)       – стоимость выполнения работы   исполнителем    [руб./ед. работ];

6)       – интенсивность выполнения работы   исполнителем   [ед. работ/ед.ресурса].

Искомые параметры модели РЗ

1)       – планируемая загрузка исполнителя   при выполнении работ    [ед. ресурса];

2)       – количество работ  , которые должен будет произвести исполнитель    [ед. работ];

3)       – общие расходы на выполнение всего запланированного объема работ  [руб.].

Этапы построения модели

I. Определение переменных.

II. Построение распределительной матрицы (см. табл.6.1).

III.Задание ЦФ.

IV.Задание ограничений.

Таблица 6.1 Общий вид распределительной матрицы

Исполнители,	Работы,				Запас ресурса, ед.ресурса
			…
			…
			…
…	…	…	…	…	…
			…
План, ед.работы			…

Модель РЗ

;

(6.1)

где   – это количество работ j-го вида, выполненных i-м исполнителем.

Этапы решения РЗ

I. Преобразование РЗ в ТЗ:

1) выбор базового ресурса и расчет нормированных производительностей ресурсов  :

(6.2)

2) пересчет запаса рабочего ресурса исполнителей  :

[ед. ресурса];

(6.3)

3) пересчет планового задания  :

;

(6.4)

4) пересчет себестоимостей работ:

.

(6.5)

II. Проверка баланса пересчитанных параметров   и построение транспортной матрицы.

III. Поиск оптимального решения ТЗ .

IV. Преобразование оптимального решения ТЗ   в оптимальное решение РЗ  , причем переход   выполняется по формуле (6.6)

[ед. ресурса],

(6.6)

где   и   – соответственно элементы решения РЗ и ТЗ.

V. Определение количества работ  , соответствующее оптимальному решению РЗ  :

.

(6.7)

VI. Определение ЦФ распределительной задачи   согласно (6.1).

Задача №6.01

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

        производительности станков по каждому виду ткани, м/ч

;

        себестоимость тканей, руб./м

;

        фонды рабочего времени станков ( ): 90, 220, 180 ч;

        планируемый объем выпуска тканей ( ): 1200, 900, 1800, 840 м.

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

Решение

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

Таблица 6.2

Распределительная матрица задачи №6.01

Станки	Ткани				Фонд времени  , ч
	В1	В2	В3	В4
А1	2 ( ) ( ) 24	1 30	3 18	1 42	90
А2	3 12	2 15	4 9	1 21	220
А3	6 8	3 10	5 6	2 14	180
Объем выпуска , м	1200	900	1800	840

ЦФ имеет смысл себестоимости выпуска запланированного количества ткани всех видов

Ограничения имеют вид

Преобразуем РЗ в ТЗ, т.е. представим исходную задачу в виде, когда ткани производит только один станок – базовый и все параметры задачи согласуем с его характеристиками. В качестве базового можно выбирать любой из станков. Мы выберем станок с максимальной производительностью, т.е.  . По формуле (6.2) определим производительности станков  , нормированные относительно производительности базового станка:

;

;

.

Таким образом, базовый станок работает в два раза быстрей второго станка и в три раза быстрей третьего.

Пересчитаем фонды времени станков по формуле (6.3):

 [ч];    [ч];    [ч].

Из этих величин следует, что тот объем работ, который второй станок выполняет за свой фонд времени 220 ч базовый станок сможет выполнить за 110 ч. Аналогично объем работ, который третий станок выполняет за 180 ч базовый выполнит за 60 ч.

Пересчитаем плановое задание по формуле (6.4):

 [ч];   [ч];   [ч];   [ч].

Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит за 50 ч, второго вида – за 30 ч и т.д.

Пересчет себестоимостей производим по формуле (6.5), например:

 [руб./ч];   [руб./ч];   [руб./ч].

В полученной ТЗ условие баланса (4.2) не выполняется, т.к. суммарный фонд времени станков больше, чем это необходимо для выполнения плана по выпуску всех тканей (260 ч > 200 ч). Введем фиктивный столбец   и запишем все пересчитанные параметры РЗ в транспортную матрицу (см. табл.6.3). Фиктивные тарифы для упрощения приравняем к нулю.

Таблица 6.3

Транспортная матрица задачи №6.01

Станки	Ткани					Фонд времени , ч
	В1	В2	В3	В4	ВФ
А1	48	30	54	42	0	90
А2	72	60	72	42	0	110
А3	144	90	90	84	0	60
Объем выпуска  , ч	50	30	100	20	60

Для упрощения вместо оптимального решения рассмотрим опорный план  , найденный методом северо-западного угла.

 [ч].

Преобразуем опорный план ТЗ   в опорный план РЗ   согласно (6.6)

 ч].

Таким образом, первый станок должен 50 ч производить ткань первого вида, 30 ч – ткань второго вида и 10 ч – ткань третьего вида. Второй станок должен 180 ч производить ткань третьего вида и 40 ч – ткань четвертого вида. А третий станок будет простаивать, не выпуская ткань вообще, т.к. согласно решению, его загрузка находится в фиктивном столбце ( ).

Определим, сколько метров ткани каждого вида должны произвести станки по формуле (6.7)

 [м].

Определим общую себестоимость производства по формуле (6.1), используя вычисленные значения элементов матрицы 

 (руб.).

Если общий объем наличных ресурсов ?b_i (i = 1…m) равен общей потребности в них ?a_j (j = 1…n), то имеет место сбалансированная (закрытая) распределительная задача. Если же ?a_j ? ?b_i, то задача называется несбалансированной (открытой).

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

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

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

Билет 25. Особенности решения транспортной задачи с помощью электронных таблиц

Решение транспортной задачи в Excel — условное название для методов нахождения решения транспортной задачи с применением электронных таблиц Microsoft Excel. Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи. В MS Excel также можно организовать поиск начального допустимого плана и пошаговое решение транспортной задачи симплеккс-методом.