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

где J₀ множество потребителей, I₀ - множество поставщиков. Минимум должен быть обеспечен при соблюдении следующих условий.

1. По использованию возможностей каждого из поставщиков:

где А_i - запасы поставщика i. Соотношение обозначает, что объем грузов, полученных потребителями от данного поставщика, будет равен запасам их у поставщика. И таких ограничений будет столько, сколько поставщиков (i 0 1₀). Например, применительно к первому поставщику (i = l) ограничение будет иметь вид:

X₁₁ + X₁₂+X₁₃+X₁₄ = 330 и т. д.

2. По удовлетворению запросов каждого из потребителей

где B_j - запасы потребителя j.

Соотношение обозначает, что объем грузов, полученных от разных поставщиков, будет равен заказу каждого из потребителей. И таких ограничений будет столько, сколько потребителей (j 0 J₀). Например, применительно к первому потребителю (j = l) ограничение будет иметь вид:

X₁₁+X₂₁+X₃₁+X₄₁+X₅₁=542.

3. По равенству наличия ресурсов (возможность поставщиков) и потребностей в них (заказов потребителей):

Данное ограничение нами, выполнено посредством введения фиктивного поставщика. В результате мы имеем четыре потребителя и пять поставщиков (i = 1 ... 5).

4. Неотрицательность переменных: x_ij ³ 0. В обратном случае решение не имеет экономического смысла.

Решение задачи методом потенциалов предусматривает постепенное улучшение плана от исходного (допустимого или опорного) до оптимального. Опорное решение можно получить двумя способами: способом северо-западного угла и способом предпочтительных оценок.

Первоначально информацию задачи сведем в табл. 28. Чтобы не произошло смешение информации, коэффициенты с_ij запишите в верхнем правом углу.

Таблица 28.

Исходная информация задачи

Поставщики	Потребители				Наличие ресурсов
Поставщики	I	II	III	IV	Наличие ресурсов
А	3,10	3,37	2,43	2,87	330
В	2,75	2,54	2,96	3,97	592
С	4,3	3,06	3,21	3,51	710
Д	2,42	4,05	3,21	2,69	1140
Е_ф	0	0	0	0	72
Потребность в ресурсах	542	810	792	800	2944

Рассмотрим способы получения опорного решения.

1. Способ северо-западного угла. Сущность его в следующем. Задание по перевозкам (х_ij) начинаем распределять с верхней клетки слева, т. е. северо-западной х₁₁. В нее записываем план, равный меньшему из значений, стоящему в строке для этой клетки (330) или в столбце (542), т.е. записываем 330. Значит, ресурсы первого поставщика исчерпаны, однако заказ первого заказчика не выполнен на (542-330) = 212 т. Чтобы их удовлетворить, рассматриваем возможности второго поставщика В (В = 592). Тогда в клетку х₂₁ запишем меньшее из значений для этой, клетки (212 и 592), т. е. 212. Теперь имеем, что заказ первого потребителя в количестве 542 т выполнен, однако возможности поставщика В недоиспользованы на 380 единиц (592-212). Их распределяем второму потребителю, начиная с клетки х₂₂. Для нее характерны значения в строке - оставшийся ресурс поставщика В второго) - 380 и заказ 810 т. По тому же принципу план распределяем и дальше. Получаем опорный план (табл. 29).

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

а) распределение плана осуществляем исходя из значений c_ij. При этом, решая задачу на минимум, лучшей будет клетка с меньшим значением c_ij (

), а при решении на максимум - с большим (

);

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

в) если имеется нуль-клетка или нуль-столбец, то при решении на минимум план записываем в ту нуль-клетку, для которой характерна большая по абсолютной величине разность между нулем и лучшим с точки зрения цели значением целевой функции (0-с_ij), стоящем в строке или столбце для этого нуля, а при решении на максимум за основу принимаем нуль с соответствующей меньшей разностью. В нашем случае c₅₁ = 0 в строке для этого нуля стоят нулевые оценки. Значит, рассматриваем коэффициенты столбца (0; 2,42), так как 2,42 лучшее из значений с₁₁, затем - (0; 2,54), (0; 2,43), (0; 2,26). Большая разность характерна для k₅₂ (0; 2,54). В нуль-клетку k₅₂ записываем возможный план х₅₂ = 72. Отсюда возможности поставщика Е_ф исчерпаны. В другом случае рассматривали бы k₅₃ (0; 2,43) и т. д.;

г) после распределения плана в строках (столбцах) с запрещенными клетками и в нуль-строке (столбце) распределение плана выполняем по оставшимся клеткам, начиная с лучшей с точки зрения цели. В нашем примере такой будет при c₄₁ = 2,42. В нее записываем 542 и, таким образом, заказ первого потребителя будет выполнен. Затем находим лучшую из оставшихся и так до полного распределения плана. Следующей лучшей, будет клетка k₁₃ при с₁₃=2,43. В нее заносим план размером 330 и т. д. В результате получим опорный план (табл. 29).

Таблица 29.

Опорный план задачи (определен способом предпочтительных оценок)

Поставщики	Потребители				Ресурсы
Поставщики	I	II	III	IV	Ресурсы
А	^3,1	^3,37	^2,43 330	^2,87	330
В	^2,75	^2,54 592	^2,96	^3,97	592
С	^4,3	^3,06 146	^3,21 462	^3,51 102	710
Д	^2,42 542	^4,05	^3,21	^2,6⁹ 698	1240
Е_ф	⁰	⁰ 72	⁰	⁰	72
Потребность в ресурсах	542	810	792	800	2944

Затраты материально-денежных средств на выполнение опорного плана составят:

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

Использование способа северо-западного угла обеспечило нахождение опорного плана, т. е. решение, при котором ресурсы распределены, а заказы выполнены (табл. 30).

Таблица 30.

Опорный план задачи (определен способом северо-западного угла)

Поставщики	Потребители				Ресурсы
Поставщики	I	II	Ш	IV	Ресурсы
А	^3,1 330	^3,37	^2,43	^2,87	330
В	^2,7⁶ 212	^2,54 380	^2,96	^3,97	592
С	^4,3	^3,06 430	^3,21 280	^3,51	710
Д	^2,42	^4,05	^3,21 512	^2,6⁹ 728	1240
Е_ф	⁰	⁰	⁰	⁰ 72	72
Потребность в ресурсах	542	810	792	800	2944

Затраты материально-денежных средств на выполнение плана составят: