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

F₁= 330x2,43+592x2,54+146x3,06+462x3,51+542x2,42+648x2,69+72x0 = 7782,6.

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

При выполнении контрольной работы вы можете использовать любой из двух способов для получения опорного решения. При построении опорного или исходного плана важно обеспечить соблюдение следующего правила: число заполненных клеток должно составить сумму строк (m) и столбцов (n) без единицы (m+n-1). В нашем случае число строк - 5, столбцов - 4. Значит, заполненных клеток должно быть 8. В обоих случаях их количество равно восьми. В том случае, если число заполненных клеток меньше m+n-1, можно сделать следующее: а) переставить местами несколько строк или столбцов, б) поставить нуль в лучшую (с точки зрения цели) из оставшихся пустых клеток. Следует помнить, что число заполненных клеток будет меньше m+n-1, если какое-либо значение в строке «потребность в ресурсах» равно сумме или разности значений столбца «наличие ресурсов» или наоборот. Построенный опорный план проверяем на оптимальность. Проверка включает два этапа:

1. Нахождение потенциалов (оценочных коэффициентов) для заполненных клеток, т. е. клеток, в которых записан план.

2. Проверка на потенциальность незаполненных клеток. Сущность проверки состоит в том, чтобы выяснить, имеются ли свободные клетки, перераспределение плана в которые приводит к улучшению плана, т. е. уменьшению значения F (функции) при решении задачи на минимум или увеличению ее при решении на максимум. Рассмотрим содержание этапов.

Этап 1. Потенциалы для заполненных клеток определяем по формуле

(1)

откуда

(2)

(3)

где v_j - потенциал столбца j, j = 1...4, u_i - потенциал строки i (или поставщика i и потребителя j). Поскольку в уравнении (1) два неизвестных, вводим исходное значение u₁ = 0. При этом за основу дальнейших расчетов возьмем опорный план, полученный способом предпочтительных оценок. В табл. 30 введем дополнения. Введем строку для обозначения потенциалов столбцов (v_j) и столбец для обозначения потенциалов строк (u_j) (табл. 31).

Таблица 31.

Рабочая таблица оптимизации распределения ресурсов между потребителями

Поставщики	Потребители				Ресурсы	Потенциалы строк, u_i
Поставщики	I	II	Ш	IV	Ресурсы	Потенциалы строк, u_i
А	^3,1	^3,37	^2,43 330	^2,87	330	0
В	^2,75	^2,54 592	^2,96	^3,97	592	-0,26
С	^4,3	^3,06 146	^3,21 462	^3,57 102	710	-0,78
Д	^2,42 542	^4,05	^3,21	^2,69 698	1240	0,04
Е	⁰	⁰ 72	⁰	⁰	72	2,28
Потребность в ресурсах	542	810	792	800	2944	-
Потенциалы столбцов, v_j	²^,⁴⁶	^2,28	_2,43	_2,73	-	-

Поскольку u₁ = 0, т. е. потенциал первой строки, то по коэффициенту 2,43 (с₁₃) заполненной клетки k₁₃ определим v₃=c₁₃+u₁= 2,43+0 = 2,43. Поскольку в строке u₁ больше нет заполненных клеток, то берем вновь определенный потенциал v₃ и на его основе и с учетом с_ij заполненных клеток столбца v₃ найдем новые потенциалы. В столбце v₃ заполненной является клетка k₃₃, для которой следует определить потенциал строки u₃. Согласно формуле (3) u₃ = v₃-с₃₃ = 2,43-3,21 = -0,78. Поскольку в столбце v_з больше заполненных клеток не имеется, берем за основу найденное значение u₃ = -0,78 и на его основе рассчитываем по данным заполненных клеток k₃₄ и k₃₂ потенциалы v₄ и v₂. Они соответственно равны: v₄ = с₃₄ + u₃ = 3,51 + (-0,78) =2,73; v₂ = u₃ + с₃₂ = 3,06 + (-0,78) = 2,28. И так продолжаем до определения потенциалов для всех строк и столбцов. После этого проверяем возможность улучшения плана за счет незаполненных клеток, т. е. проверяем план на потенциальность. Решение будет оптимальным, если для незаполненных клеток выполняется условие:

v_j - u_i ≤ с_ij, (4)

при решении задачи на минимум

v_j - u_i ≥ с_ij, (5)

при решении задачи на максимум.

В нашем случае проверяем незаполненные клетки по формуле (4). Нарушения будут иметь место, если для незаполненной клетки характерно v_j-u_i > c_ij , и тогда величина нарушения (k_jj) составит k_ij =v_j-u_i-с_ij > 0.

Из табл. 31следует, что нарушение характерно для клетки k₅₄. Величина нарушения потенциальности (k_ij), т. е. k₅₄ = 2,73-2,28-0=0,45. С экономической точки зрения величина непотенциальности обозначает, насколько единиц улучшится план (при решении на минимум F уменьшается, на максимум - F возрастает), если в непотенциальную клетку, вследствие перераспределения плана, введем задание (х_ij) в размере 1. Клетка с нарушением становится основой для улучшения плана. Если же в результате проверки определено несколько нарушений, то при решении на минимум и максимум в качестве исходной для улучшения плана берем клетку с наибольшим нарушением. Улучшение плана выполняем на основе цикла, который дает ответ на вопрос, как улучшить план. Правила построения цикла следующие:

l. Цикл начинаем строить с непотенциальной клетки с наибольшим нарушением и завершаем в ней (в случае, если за основу цикла взята клетка не с максимальным нарушением, для получения оптимального плана потребуется построить больше циклов);

2. Вершины цикла проходят только по заполненным клеткам. При этом поворот линии цикла осуществляем под углом 90° и только в занятых клетках. Число вершин цикла в строке или столбце четное (в случае, если число заполненных клеток меньше, чем m+n-1, в цикле могут получиться две и более незаполненные клетки). Решение в подобной ситуации возможно, если номер другой незаполненной клетки, кроме той, что послужила началом цикла (т. е. не потенциальной и с наибольшим нарушением), будет нечетным по отношению к начальной клетке цикла;

3. В не потенциальную клетку цикла ставим плюс, в следующую - минус и так поочередно (если число заполненных клеток цикла меньше m+n-1), то в другие, кроме начальной клетки цикла, ставим нуль. Необходимо, чтобы знак для них был положительным. А это достигается, если номер этих клеток нечетный, считая, что клетка начала цикла имеет номер 1.

В нашем случае не потенциальная клетка k₅₄. Она начало цикла, который пройдет по клеткам k₅₄-k₅₂-k₃₂-k₃₄ Приставляем знаки в вершинах цикла: k₅₄ (+), k₅₂ (-), k₃₂ (+), k₃₄ (-). По цепи цикла перемещаем меньшее число клетки со знаком минус, т. е. 72. В результате получим новый план (табл. 32).

Таблица 32.

Улучшенный план распределения ресурсов

Поставщики	Потребители				Ресурсы	Потенциалы строк u_i
Поставщики	I	II	Ш	IV	Ресурсы	Потенциалы строк u_i
А	^3,1	^3,37	^2,43 330	^2,87	330	0
В	^2,75	^2,54 592	^2,96	^3,97	592	-0,26
С	^4,3	^3,06 218	^3,21 462	^3,51 30	710	-0,78
Д	^2,42 542	^4,05	^3,21	^2,69 698	1240	0,04
Е_ф	⁰	⁰	⁰	⁰ 72	72	2,73
Потребность в ресурсах	542	810	792	800	2944	-
Потенциалы столбцов, v_j	²^,⁴⁶	²^,²⁸	₂_,₄₃	₂_,₇₃	-	-

Материально-денежные затраты на выполнение плана составят: