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

Фирма осуществляет поставку бутылок на четыре завода, занимающихся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 - 3000 бутылок и на складе 3 - 4000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу 5000 бутылок, третьему заводу - 1000 бутылок, четвертому заводу - 3000 бутылок. Матрицей C = (c_ij) задана стоимость перевозки (ден. ед.) одной бутылки от каждого склада к каждому заводу:

Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной?

Решение. Запишем исходные данные в распределительную таблицу, найдем исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, n + m – 1 = 6 (n = 4, m = 3), следовательно, задача является вырожденной.

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

bj ai					ui
						-1
						-1
	vj

Оценки свободных клеток будут равны:

Δ₁₁ = -3, Δ₁₃ = -6, Δ₂₁ = -3, Δ₂₄ = -1, Δ₃₃ = -4, Δ₃₄ = -1 ( Δ_ij = u_i + v_j – c_ij)

Все оценки отрицательные, получили оптимальное решение.

Ответ:

Х _опт =

Стоимость транспортных расходов составит: L = 52000 ден. ед.

Транспортная задача и ЕХСЕL.

Пример 7. Задача организации оптимального снабжения.

Три фермерских хозяйства А₁, А₂, А₃ ежедневно могут доставлять в город соответственно 60, 60 и 50 ц молока для обеспечения пяти торговых точек: В₁, В₂, В₃, В₄, В₅. Стоимость перевозки 1 ц молока и потребности торговых точек в молоке указаны в таблице.

Фермерское хозяйство	Затраты на перевозку 1 ц к торговым точкам	Запас молока (ц)
В1	В2	В3	В4	В5
А1
А2
А3
Потребности в молоке (ц)

Определить оптимальный план поставки молока в каждую точку для удовлетворения потребностей, чтобы суммарные транспортные издержки были минимальными.

Решение. Данная задача является ТЗ открытого типа, так как запасы молока у поставщиков (фермерских хозяйств) больше потребностей в молоке у торговых точек. Для открытой модели по сравнению с закрытой моделью изменяется только вид системы ограничений.

Переменные х_ij ; ) ¾ количество молока, поставляемое i- м фермерским хозяйством в j -ю торговую точку.

Целевая функция - суммарные транспортные издержки, которые необходимо минимизировать:

f(X) = 7 х₁₁ + 6х₁₂ + 8х₁₃ +10х₁₄ +12х₁₅ + 9х₂₁ + 5х₂₂ + 7х₂₃ +4х₂₄ + 6х₂₅ +6х₃₁ + 8х₃₂ + 4х₃₃ + 9х₃₄ + 7х₃₅

Ограничения связанные с поставщиками и потребителями (функциональные):

· по поставщикам

· по потребителям

Ограничения следующие из экономического смысла задачи (прямые): х_ij

Указать адреса ячеек, в которые будет помещен результат решения. Изменяемые ячейки – В11:F13. В эти ячейки в результате решения задачи будет записаны оптимальные значения х_ij.

1. Ввести исходные данные.

2. Ввести зависимости для ограничений, т. е. внести функции ограничений. Сначала ввести условия реализации мощностей поставщиков:

где a_i - мощность поставщика i; - объем поставки груза от поставщика i к потребителю j; n –количество потребителей.

· Поместить курсор в ячейку G11.

· Выбрать функцию СУММ.

· Выделить необходимые для суммирования ячейки В11:F11.

· Нажать кнопку ОК для подтверждения ввода формулы для суммирования. Аналогичные действия выполняются для ячеек G12, G13.

Затем ввести условие удовлетворения запросов потребителей:

где b_j - мощность потребителя j; m –количество потребителей.

· Поместить курсор в ячейку В14.

· Выбрать функцию СУММ.

· Выделить необходимые для суммирования ячейки В11:В13.

· Нажать кнопку ОК для подтверждения ввода формулы для суммирования.

Эту же последовательность действий выполнить для ячеек с14 и F14.

3. Ввести зависимость для целевой функции. Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, зарезервируем ячейку и введем формулу для ее вычисления:

где - стоимость доставки 1 ц молока от поставщика i к потребителю j.

· Поместить курсор в ячейку G14 (после решения задачи в данной ячейке будет находиться значение целевой функции).

· Запустить Мастер функций (значок f_x).

· В окне Категория выбрать Математические.

· В окне Функция выбрать СУММПРОИЗВ.

· Нажать кнопку ОК.

· В окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией.

В нашей задаче целевая функция представляет собой произведение затрат на доставку молока (ячейки В3:F5) и объемов поставок для каждого потребителя (содержимое ячеекВ11:F13).

· И поле Массив 1 указать адреса В3:F5.

· И поле Массив 2 указать адреса В11:F13.

· Нажать кнопку ОК -подтверждение окончания ввода адресов массивов.

В поле ячейки G14 появится некоторое числовое значение, равное произведению поставок на коэффициенты затрат по доставке грузов (в данной задаче - это 0).

В следующей таблице отражены введенные формулы.

Фермер-cкие хозяй-cтва	Количество перевезенного молока от фермерских хозяйств Аi к торговым точкам Вj
	B1	B2	B3	B4	B5
A1						=СУММ(В11:F11)
A2						=СУММ(В12:F12)
A3						=СУММ(В13:F13)
	=СУММ (В11:B13)	=СУММ (C11:C13)	=СУММ (D11:D13)	=СУММ (E11:E13)	=СУММ (F11:F13)	=СУММПРОИЗВ (В3:F5,В11:F13)

4. Запустить команду Поиск решений.

5. Назначить ячейку для целевой функции.

· В окне Оптимизировать целевую ячейку указана $G$14.

· Ввести тип целевой функции – Минимальное значение.

· В окне Изменяя ячейки указать В11:F13

6. Ввести ограничения.

Поместить указатель мыши на кнопку Добавить. Появится диалоговое окно Добавление ограничения. В окне Ссылка на ячейку указываем В14:F14. Правее в выпадающем списке с условными операторами выбираем =. В окне Ограничение: вводим В6:F6 (это ограничение по уровню спроса). Аналогично вводится ограничение по уровню запасов G11:G13 = G3:G5.

После ввода всех ограничений нажмем кнопку ОК.

7. Ввести параметры для решения задачи ЛП.

Во вкладке Выберите метод решения выбираем Поиск решения линейных задач симплексным методом.

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

Нажать кнопку ОК. Опять появится диалоговое окно Поиск решения. Решение задачи выполняется сразу же после ввода данных, когда на экране находится диалоговое окно Поиск решения.

Нажать кнопку Поиск решения. В результате на экране появится диалоговое окно Результаты поиска решения.

Решение найдено и отражено в таблице.

Фермерские хозяйства	Количество перевезенного молока от фермерских хозяйств Аi к торговым точкам Вj
	B1	B2	B3	B4	B5
A1	30	10	0	0	0	40
A2	0	10	5	20	25	60
A3	0	0	50	0	0	50
	30	20	55	20	25	785

Ответ: Общие затраты на перевозку продукции составят 785 денежных единиц. Спрос торговых точек удовлетворен полностью - они получат 150 ц молока. У первого фермерского хозяйства останется нереализованным 20 ц молока.