Практична робота №3« Розв’язок транспортної задачі за допомогою вікна Пошук рішення в табличному редакторі Microsoft Excel»

Практична робота № 3 « Розв’язок транспортної задачі за допомогою вікна "Пошук рішення" в табличному редакторі Microsoft Excel»

Ціль роботи: вивчити методи рішення планировании наиболее рациональных перевозок грузов та обґрунтування рішення.

Постановка задачі:

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

Пусть в n пунктах отправления находятся соответственно а₁,а₂,…а_n единиц однородного груза, который должен быть доставлен m потребителям в количестве b₁,b₂,…b_m единиц. Даны стоимости c_i,j перевозок единицы груза из i-ого пункта отправления j-ому пункту потребления. Пусть x_i,j³0 – количество единиц груза отправляемого из i -ого в j-ый пункт.

Система ограничений

,

Целевая функция – суммарные затраты на перевозки: (3). Требуется найти значения x_i,j, удовлетворяющие ограничениям (1),(2) и минимизирующие целевую функцию (3). (a_i, b_j, c_i,j– заданы).

Занесём исходные данные в таблицу. Определим значения x_i,j.

bj ai

b1

b2

…

bj

…

bm

a1

c11

c12

…

c1j

…

c1m

x11

x12

x1j

x1m

…

…

…

…

…

…

…

ai

ci1

ci2

…

cij

…

cij

xi1

xi2

xij

xim

…

…

…

…

…

…

…

an

cn1

cn2

…

cnj

…

cnm

xn1

xn2

xnj

xnm

Пример1: В 2-х пунктах отправления А и В имеются 150т и 90т горючего. В пункты 1,2,3 требуется доставить 60,70,110 тонн соответственно. Стоимости тонны горючего при перевозке из пункта А в пункты 1,2,3 составляют соответственно 6,10,4 д. ед., а из пункта В – 12,2,8 д. ед. соответственно. Составить оптимальный план перевозок, чтобы сумма транспортных расходов была минимальна.

Решение

Занесём исходные данные в таблицу

	bj ai
А
В

Суммарные запасы поставщиков равны суммарным потребностям, т.е.

=240 д. ед. Модель является закрытой.

Обозначим x_i,j³0 – количество единиц груза отправляемого из i -ого пункта отправления в j-ый пункт потребления.

Целевая функция

Система ограничений

Занесём данные о стоимости перевозок, о запасах поставщиков и потребностях потребителей в таблицу Excel.

	Поставщики	Запасы	Потребители
	А
	В
	Потребности

Составим таблицу, включающую план перевозок и ограничения.

	Поставщики	Потребители	Ограничения	Запасы
	А				=СУММ(B11:D11)	=
	В				=СУММ(B12:D12)	=
	Ограничения	=СУММ(B11:B12)	=СУММ(C11:C12)	=СУММ(D11:D12)
		=	=	=
	Потребности						=СУММПРОИЗВ(C3:E4;B11:D12)

Используя окно «Поиск решения» найдем оптимальное решение. Система ограничений задается следующим образом:

$B$11:$D$12>=0 (Перевозимое количество тонн горючего)

$B$11:$D$12=целое

$E$11:$E$12=$G$11:$G$12 (Ограничения на запасы)

$B$13:$D$13=$B$15:$D$15 (Ограничения на потребности)

Изменяемые ячейки: $B$11:$D$12

Целевая ячейка: $G$15

Оптимальное решение:

	Поставщики	Потребители	Ограничения	Запасы
	А					=
	В					=
	Ограничения
		=	=	=
	Потребности

Ответ:

Найден оптимальный план перевозок X= . Минимальная стоимость транспортных расходов L=1020 д. ед.

Завдання для виконання практичної роботи№3

……………………………………………………………………………………………………

2. Открытая модель транспортной задачи.

Ранее рассматривались задачи, для которых суммарные запасы поставщиков были равны суммарным потребностям, т.е.

. Такая модель называется закрытой. В противном случае - открытой.

Возможны две ситуации:

1) Суммарные запасы превышают суммарные потребности, т.е. . Приводим к закрытой модели, вводя фиктивного потребителя, потребности которого .

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

Найти оптимальный план транспортной задачи. Все данные записаны в таблицу.

bj ai

Т.к. Sa_i ¹ Sb_j, то открытая модель транспортной задачи Sb_j > Sa_i, поэтому вводим фиктивного поставщика с запасом а₅=50. Получаем закрытую модель.

Все оценки положительны, следовательно, найденный план оптимален: Минимальная стоимость расходов 430 гр.

Задание №2

Вариант 1

bj ai

Дата добавления: 2015-09-29