Оптимальное распределение ресурсов

В нашей задаче: отрицательные  вершины контура расположены в клетках а₁₁и а₂₃. В клетке а₁₁ объем перевозок равен 50 т, в а₂₃–20т. Следовательно, меньший объем перевозок в клетках с отрицательными вершинами равен 20. Этот объем вычитаем из клеток а₁₁, a₂₃ и прибавляем к клеткам а₁₃,a₂₁,затем записываем в новую таблицу (Таблица 7):

Сырье	Предприятия				Запасы
	1	2	3	4
1	7 30	8 X12	1 20	2 110	160
2	4 90	5 50	9 X23	8 X24	140
3	9 X31	2 X32	3 170	6 X34	170
Потребность	120	50	190	110	470

Таблица 7

Четвертый   опорный  план.                     

В таблице 7 вновь проверяем  объем ограничений по строкам  и столбцам. Суммарные издержки на перевозку при таком плане  равны:

Z₄=7·30+20+2·110+4·90+5·50+3·170=1570 или на 1650 меньше, чем в первом плане.

Составленный план опять принимаем за исходный, и всю вычислительную процедуру повторяем  снова:

Рассчитываем потенциалы для занятых клеток:

U₁=0;

V₁=C₁₁-U₁=7-0=7;

V₃=C₁₃-U₁=1-0=1;

V₄=C₁₄-U₁=2-0=2;

U₂=C₂₁-V₁=4-7=-3;

V₂=C₂₂-U₂=5+3=8;

V₃=C₂₃-U₂=9+3=12;

U₃=C₃₃-V₃=3-1=2.

 

 

 

 

 

Сырье	Vj    Ui	Предприятия				Запасы
		1	2	3	4
		7	8	1	2
1	0	7 - 30	8   X12	1  + 20	2   110	160
2	-3	4 + 90	5  - 50	9   X23	8   X24	140
3	-9	9   Х31	2 + Х32	3 - 170	6   X34	170
Потребность		120	50	190	110	470

Таблица 8

Затем проверяем план на оптимальность путем определения l_ij для свободных клеток (Таблица 8):

l₁₂=C₁₂-(U₁+V₂ )=8-(0+8)=0;

l₂₄=C₂₄-(U₂+V₄)=9-(-3+1)=11;

l₂₄=C₂₄-(U₂+V₄)=8-(-3+2)=9;

l₃₁=C₃₁-(U₃+V₁)=9-(2+7)=0;

l₃₂=C₃₂-(U₃+V₂)=2-(2+8)=-8;

l₃₄=C₃₄-(U₃+V₄)=6-(2+2)=2.

Так как среди значений l_ij  есть отрицательные, то четвертый опорный план не оптимален.

Для улучшения плана  среди отрицательных значений l_ij берем клетку с наибольшим по абсолютной величине значением и строим из нее замкнутый контур. Возьмем клетку а₃₂, в которой значения l₃₂ = -8. Контур, построенный из клетки а₃₂ (таблиц 8), обозначим пунктиром. В вершине свободной клетки поставим знак “+”, в остальных клетках – знаки “+” и ”- ” чередуются.

В нашей задаче: отрицательные  вершины контура расположены в клетках а₁₁,а₂₂,a₃₃. В клетке а₁₁ объем перевозок равен 30 т, в а₂₂–50т, в a₃₃-170т. Следовательно, меньший объем перевозок в клетках с отрицательными вершинами равен 30. Этот объем вычитаем из клеток а₁₁, a₂₂,a₃₃ и прибавляем к клеткам а₁₃,a₂₁,a₃₂, затем записываем в новую таблицу (Таблица 9):

Сырье	Предприятия				Запасы
	1	2	3	4
1	7 X11	8 X12	1 50	2 110	160
2	4 120	5 20	9 X23	8 X24	140
3	9 X31	2 30	3 140	6 X34	170
Потребность	120	50	190	110	470

Таблица 9

Пятый опорный план.                     

    В таблице 9 вновь проверяем объем ограничений по строкам и столбцам. Суммарные издержки на перевозку при таком плане равны:

Z₅=50+2*110+4*120+5*20+2*30+3*140=1330 или на 1890 меньше, чем в первом плане.

Составленный план опять  принимаем за исходный, и всю вычислительную процедуру повторяем  снова:

Рассчитываем потенциалы для занятых клеток:

U₁=0;

V₃=C₁₃-U₁=1-0=1;

V₄=C₁₄-U₁=2-0=2;

V₃=C₁₃-U₁=1-0=1;

U₃=C₃₃-V₃=3-1=2;

V₂=C₃₂-U₃=2-2=0;

U₂=C₂₂-V₂=5-0=5;

V₁=C₂₁-U₂=4-5=-1;

 

 

 

 

 

Сырье	Vj    Ui	Предприятия				Запасы
		1	2	3	4
		7	8	1	2
1	0	7   X11	8   X12	1         50	2   110	160
2	-3	4   120	5   20	9   X23	8   X24	140
3	-9	9   Х31	2   30	3   140	6   X34	170
Потребность		120	50	190	110	470

Таблица 10

Затем проверяем план на оптимальность путем определения l_ij для свободных клеток (Таблица 10):

l₁₁=C₁₁-(U₁+V₁ )=7-(0-1)=8;

l₁₂=C₁₂-(U₁+V₂ )=8-(0+0)=8;

l₂₃=C₂₃-(U₂+V₃)=9-(5+1)=3;

l₂₄=C₂₄-(U₂+V₄)=8-(5+2)=2;

l₃₁=C₃₁-(U₃+V₁)=9-(2-1)=8;

l₃₂=C₃₂-(U₃+V₂)=6-(2+2)=2.

  Все значения l_ij – неотрицательны. Следовательно, план оптимален при следующих значениях переменных: х₁₃=50,   х₁₄=110,   х₂₁=120,   х₂₂=20,   х₃₂=30,   х₃₃=140. При этом Z_max=1330 ден.ед.

 

Задача оптимизации товарных потоков по транспортной сети в MS Excel

Для решения задачи в MS Excel будем придерживаться алгоритма:

1. Создать таблицу с исходными числовыми данными и рабочую таблицу с изменяемыми ячейками, в которые будут записываться полученные результаты.
2. Составить формулу для целевой функции.
3. Указать адреса исходных и изменяемых данных, ограничения на переменные величины.
4. Сохранить полученные результаты и отчеты для анализа решения.

 

1. Составим на рабочем месте Excel две таблицы – они изображены на рис.1. В таблице «Предприятия» записываются исходные числовые данные. В таблице «План перевозок» продублированы столбец «Запасы» и строка «Потребность». Добавлены: столбец «Использовано» и строка «Удовлетворено».

Рис.1

2. Заполним формулами, необходимыми для создания ограничений на запасы, ячейки F10:F12 столбца «Использовано»:

• в ячейку F10 ввести формулу суммы по диапазону В10:E10. Результатом будет функция  = СУММ (В10:E10) в ячейке F10;

• выделить ячейку F10, установить указатель мыши на маркер автозаполнения, провести указателем мыши (при нажатой левой кнопке мыши) по диапазону ячеек F11:F12;

3. Заполним формулами, необходимыми для создания ограничений на потребности, ячейки В13:E13 строки «Удовлетворено»:

• в ячейку В13 ввести сумму по диапазону В10:В12;
• скопировать содержимое ячейки В13 на диапазон С13: E13.

4. Для наглядности запишем общие суммы по столбцам и строкам:

• в ячейку G13 – по столбцу «Запасы»:

= СУММ (G10:G12);

• в ячейку F13 – по столбцу «Использовано»:

= СУММ(F 10: F12);

• в ячейку F14 – по строке «Потребность»:

= СУММ (В14: E14).

5.   Запишем формулу для целевой функции:

• выделим ячейку F15, щелкнув на знаке f_x на панели инструментов, в категории Математические выбрать функцию СУММПРОИЗВ, щелкнуть по кнопке ОК.

• в появившемся диалоговом окне щелкнуть на стрелке – указателе перехода в окне МАССИВ1. Диалоговое окно будет свернуто в строку ввода. Провести указателем мыши (при нажатой левой клавише) по диапазону ячеек В4:E6, щелкнуть на стрелке – указателе перехода для возврата в диалоговое окно.
• аналогично ввести МАССИВ2, выделив диапазон ячеек В10: E12.
• закончить ввод, щелкнув ОК.

Результатом в ячейке F15 будет функция

= СУММПРОИЗВ (В4: E6; В10: E12), значение которой пока равно нулю.

6.    Укажем необходимые  ссылки, на ячейки и ограничения  для целевой функции. 

Выполним команду Сервис, Поиск решения.

В появившемся диалоговом окне  Поиск решения  рис. 2 требуется:

• В поле Установить целевую ячейку  ввести абсолютный адрес, т.е. $F$15;
• Поставить флажок в окошке, соответствующем минимальному значению переключателя Равной;
• В поле, Изменяя ячейки указать диапазон ячеек $B$10:$E$12 либо прямым выделением этого диапазона с помощью мыши, либо с использованием указателя перехода;

Рис. 2

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

Рис.3

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

Список ограничений  для нашей задачи.

Для ускорения ввода  ограничений можно указывать  диапазон ячеек, при этом список ограничений выглядеть так:

 

 

 

 

 

 

Поле Ссылка на ячейку	Тип ограничения	Поле Ограничение	Примечания
$B$10:$E$12	> =	0	Условия не отрицательности  перевозимых грузов
$F$10:$E$12	=	$G$10: $G$12	Условие полного распределения запасов
$В$13:$E$13	=	$В$14:$E$14	Условие полного удовлетворения потребностей
$B$10:$E$12	цел	целое	Условие цело численности  значений по количеству груза