Лабораторная работа № 4.

ТРАНСПОРТНАЯ ЗАДАЧА. ПОСТРОЕНИЕ ПЕРВОГО ОПОРНОГО ПЛАНА.

1. Цель работы. Построение и исследование математической модели системы распределения работ в виде транспортной задачи линейного программирования. Построение первого опорного плана.

2. Краткие теоретические сведения.

Проблема выбора (задача о назначениях) является дискретным аналогом транспортной задач линейного программирования.

(max)

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

Обычно данные транспортной задачи записывают в виде таблицы планирования:

Пункты	Пункты назначения
отправл.	B1	B2	...	Bj	...	Bn	Запасы
A1	c11 x11	c12 x12	... ...	C1j x1j	... ...	c1n x1n	a1
A2	c21 x21	c22 x22	... ...	C2j x2j	... ...	c2n x2n	a2
...	...	...	...	...	...	...	...
Ai	ci1 xi1	ci2 xi2	... ...	cij xij	... ...	cin xin	ai
...	...	...	...	...	...	...	...
Am	cm1 xm1	cm2 xm2	... ...	cmj xmj	... ...	cmn xmn	am
Потреб- ности	b1	b2	...	bj	...	bn

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

3. Содержание работы

Для выполнения работ B₁, B₂, B₃, B₄ требуется соответственно b₁, b₂, b₃, b₄ работников. Имеющиеся работники по своей квалификации могут быть разбиты на группы А₁, А₂, А₃, причем количество работников каждой из квалификаций составляет соответственно а₁, а₂, а₃ чел. Необходимо составить распределение работ между работниками с учетом возможных дополнительных условий:

• Несовпадение количества имеющихся и количества требуемых работников и при этом требование непременного выполнения определенных работ (приоритетные работы) или полной загрузки работников некоторой квалификации (приоритетные работники);

• Запрет на выполнение некоторых работ работниками определенных квалификаций;

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

Эффективность выполнения работником каждой из работ зависит от уровня его квалификации. Экспертами составлена таблица, в которой величина с_ij представляет собой выраженная в баллах эффективность выполнения работником, имеющим квалификацию А_i, работы типа B_j. Критерием качества распределения работ является выраженная в баллах суммарная эффективность выполнения работ всеми работниками в соответствии с данным распределением.

Варианты заданий:

Вариант 1.

	B1	B2	B3	B4	ai
А1	2	2,5	3	5	5
А2	1	2	1	1	5
А3	1,5	1	3	2	5
bj	3	5	5	2

Дополнительные условия: а) для выполнения работы B₃ должно быть направлено не более 3 работников квалификацииА₁; для выполнения работы B₁ не могут быть привлечены работники квалификацииА₃

Вариант 2.

	B1	B2	B3	B4	ai
А1	3	1,5	3	4	5
А2	1	1,5	3	1	4
А3	1	1	3	2	3
bj	2	7	2	2

Дополнительные условия: а) для выполнения работы B₂ должно быть направлено не менее 4 работников квалификацииА₁; б) работа B₁ должна быть полностью обеспечена работниками.

Вариант 3.

	B1	B2	B3	B4	ai
А1	2	2,5	3	5	4
А2	1	2	1	1	4
А3	1,5	1	3	2	6
bj	3	5	5	2

Дополнительные условия: а) для выполнения работы B₃ не могут быть привлечены работники квалификации А₃; б) работа B₁ должна быть полностью обеспечена работниками.

Вариант 4.

	B1	B2	B3	B4	ai
А1	2	3	5	1	5
А2	4	2	2	1	4
А3	1,5	1,5	3	2	10
bj	2	8	3	1

Дополнительные условия: а) все работники квалификации А₃ должны быть привлечены к работе; б) для выполнения работы B₂ должно быть направлено не менее 3 работников квалификацииА₃.

Вариант 5.

	B1	B2	B3	B4	ai
А1	2	2,5	3	5	3
А2	1	2	1	1	1
А3	5	1	3	2	4
bj	3	2	4	2

Дополнительные условия: а) работы B₁ и B₄ должны быть полностью обеспечены работниками; б) для выполнения работы B₂ должно быть направлено не более 1 работника квалификации А₁

Вариант 6.

	B1	B2	B3	B4	ai
А1	4	5	1	2	7
А2	2,5	1	2	2	5
А3	3,5	3	2	4	14
bj	8	6	3	4

Дополнительные условия: а) все работники квалификации А₂ и А₃ должны быть привлечены к работе; б) для выполнения работы B₂ должно быть направлено не менее 3 работников квалификацииА₂.

Вариант 7.

	B1	B2	B3	B4	ai
А1	1	1,5	3,5	2	10
А2	2	2	4	4	12
А3	3	4	5	2	3
bj	6	9	6	5

Дополнительные условия: а) для выполнения работы B₄ не могут быть привлечены работники квалификации А₃; б) для выполнения работы B₂ должно быть направлено не менее 8 работников квалификацииА₁.

Вариант 8.

	B1	B2	B3	B4	ai
А1	2	2	5	3	13
А2	1	2,5	1,5	4,5	11
А3	2,5	1,5	5	4	14
bj	10	8	11	12

Дополнительные условия: а) работы B₁ и B₄ должны быть полностью обеспечены работниками; б) для выполнения работы B₁ и B₃ не могут быть привлечены работники квалификации А₃.

Вариант 9.

	B1	B2	B3	B4	ai
А1	4	5	3,5	2,5	30
А2	1,5	2	1	5	15
А3	5	1,5	3,5	5	40
bj	13	22	14	12

Дополнительные условия: а) все работники квалификации А₁ и А₂ должны быть привлечены к работе; б) для выполнения работы B₁ не могут быть привлечены работники квалификации А₂;

Вариант 10.

	B1	B2	B3	B4	ai
А1	2	5	3	3	12
А2	1,5	2	5	5	10
А3	2	4	3,5	2,5	14
bj	10	8	14	8

Дополнительные условия: а) работа B₁ должна быть полностью обеспечена работниками; б) для выполнения работы B₃ должно быть направлено не более 10 работников квалификацииА₁.