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

                                        ∆₁₁ = –4 + 3 = –1,

                                        ∆₂₂ = –5 – 3 + 3 = –5,

                                        ∆₂₃ = –3 – 3 + 7 =  1,

                                        ∆₃₂ = –5 – 2 + 3 = –4,

                                        ∆₄₂ = –5 – 4 + 5 = –4,

                                        ∆₄₃ = –3 – 4 + 5 = –2.

Анализ значений ∆_ij показывает, что условие оптимальности для плана Х₀ не выполнено, т.к. имеется значение ∆₂₃ = +1. Необходима корректировка плана.

Составляем цикл, включающий клетки: (2, 3), (3, 3), (3, 1), (2, 1). Среди значений, стоящих в минусовых клетках, выбирается минимальное. Это и будет корректирующая величина θ = 32. Свободная клетка (2, 3) заполняется значением 32, а клетка (3, 3) освобождается. В соответствии со знаком клетки меняются значения в клетках цикла: в клетку (3,1) заносится число 45 (13 + θ = 13 + 32 = 45), а в клетку (2,1) — число 21 (53 – θ = 53 – 32 = 21).

Таким образом, начальный план скорректирован и получен новый опорный план Х₁ со значением целевой функции Р₁ = Р₀ – ∆₂₃ θ = –1145 – 1 × 32 = –1177. Этот план представлен в таблице 2.1.

           

                 –   61 13

 Х₁  =     21  –  32     ,   Р₁ = –1177.

              45  –   –

              24  –   –

Шаг 2. Опорный план X₁ проверяется на оптимальность. Рассчитаем для него значения потенциалов строк U_i и столбцов V_j. Определим значение ∆_ij для всех свободных клеток:

∆₁₁ = –3 + 3 = 0,

∆₂₂ = –5 – 4 + 3 = –6,

∆₃₂ = –5 – 3 + 3 = –5,

∆₃₃ = –3 – 3 + 5 = –1,

∆₄₂ = –5 – 5 + 5 = –5,

∆₄₃ = –3 – 5 + 5 = –3.

Таблица 2.1

bj ai	90	61	45	Ui
74	-3	-5       61	-3     13	0
53	-7      21	-3	-7    32	4
45	-6     45	-3	-5	3
24	-8     24	-5	-5	5
Vj	-3	-5	-3	P1 = -1177

План, представленный в таблице 2.1, оптимален, т.к. выполнено условие (2) оптимальности плана транспортной задачи: все ∆_ij ≤ 0; значит, получено окончательное решение задачи. Умножив значение P₁ на –1, получим максимальное значение целевой функции.

Наличие ∆₁₁ = 0 говорит о том, что при заданных исходных данных в этой задаче существует ещё одно оптимальное распределение механизмов по участкам работ с тем же значением целевой функции.

Ответ:

                                                            –  61  13

                                      Х ^* =     21  –   32    ,    Р^*  = 1177.

                                                  45  –    –

                                                  24  –    –

Экономическая интерпретация оптимального решения задачи распределения механизмов между участками работ

Для получения максимальной производительности всех механизмов на всех участках работ в размере 1177 (единиц работы/единицу времени) необходимо распределить их следующим образом:

·  механизм 1 — на участок В (61 единицы) и участок С (13 единиц);

·  механизм 2 — на участок А (21 единицы) и участок С (32 единицы);

·  механизм 3 — на участок А (45 единиц);

·  механизм 4 — на участок А (24 единиц).

3. Задача о назначении напарников

Для рациональной организации в районе патрульно-постовой службы опытным сотрудникам Иванову, Петрову, Сидорову и Егорову необходимо назначить напарников из числа вновь поступивших молодых сотрудников: Костина, Мишина, Васина и Юрина. В ходе прохождения испытательного срока все возможные пары сотрудников оценивались по количеству неустраненных ими правонарушений за время дежурства на вверенном им участке. В результате были получены усредненные показатели по количеству неустраненных патрулями правонарушений за время одного дежурства, приведенные в следующей таблице.

	Костин	Мишин	Васин	Юрин
Иванов	2	10	9	7
Петров	15	4	14	8
Сидоров	13	14	16	11
Егоров	4	15	13	19

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

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

Решение

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

Так как число опытных сотрудников (m = 4) равно числу молодых сотрудников (n = 4), должны выполняться следующие условия:

1.  К каждому опытному сотруднику прикрепляется только один молодой сотрудник.

2.  К каждому молодому сотруднику прикрепляется только один опытный сотрудник.

Введем переменные x_ij (i, j = ), которые характеризуют назначение i-го опытного сотрудника в пару с j-м молодым сотрудником. Они могут принимать лишь одно из двух значений 0 или 1:

                   1, если в пару к опытному сотруднику i назначен молодой сотрудник j; 

       x_ij =    

                    0, если не назначен.

Например, x₃₂ = 1. Это означает, что опытный сотрудник Сидоров (i = 3) назначен в пару с молодым сотрудником Мишином (j = 2).

Так как любой опытный сотрудник i должен быть назначен только в одну из четырёх возможных пар, то только одна из величин x_i1, x_i2, x_i3, x_i4  будет равна 1, а остальные будут равны 0. Таким образом, условие 1 имеет вид:

x_i1 + x_i2 + x_i3  + x_i4  = 1, i = .

С другой стороны, каждый молодой сотрудник j назначается только в одну из четырёх возможных пар. Поэтому только одна из величин x_1j , x_2j , x_3j , x_4j  равна 1, а остальные равны 0. Таким образом, условие 2 имеет вид:

x_1j + x_2j + x_3j  + x_4j  = 1, j = .