Практическая работа 4 Решение задач оптимизации средствами электронных таблиц ms Excel

Цель: овладеть навыками решения задач оптимизации средствами электронных таблиц MS Excel.

Рассмотрим решение задач оптимизации на примере транспортной задачи.

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

Постановка задачи.

Пусть требуется развести груз, хранящийся на m складах А₁ , А₂ , … А_m в количествах а₁ , а₂ , … а_m соответственно по пунктам назначения B₁ , В₂ , … В_n, подавшим заявки на b₁ , b₂ , … b_n единиц груза. Пусть запас груза на всех складах равен суммарной заявке, то есть:

m n

Σ а_i = Σ b_j .

i =1 j =1

Известно, что стоимость перевозки единицы груза от i-го склада к j-му потребителю равна c_ij. Требуется составить такой план перевозок, чтобы все заявки были выполнены, а стоимость всех перевозок была минимальна.

Математическая модель.

Пусть x_ij – количество груза, перевозимое со склада А_i потребителю B_j. Прямоугольную матрицу, составленную из величин x_ij, будем называть планом перевозок.

Суммарное количество груза, перевозимое с каждого склада потребителям, должно быть равно запасу на данном складе. То есть:

x ₁₁ + x₁₂ + … + x_1n = а₁

x₂₁ + x₂₂ + … + x_2n = а₂

……………………….

x_m1 + x_m2 + … + x_mn = а_m

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

x ₁₁ + x₂₁ + … + x_m1 = b₁

x₁₂ + x₂₂ + … + x_m2 = b₂

……………………….

x_1n + x_2n + … + x_mn = b _n

Суммарная стоимость всех перевозок должна быть минимальной

m n

Z =Σ Σ c_{i j} x_{i j} → min

i =1 j =1

Задача 1.

Пусть имеются n=5 поставщиков и m=3 потребителей. Издержки перевозки единицы груза от i-го поставщика в j-й пункт назначения, запасы поставщиков и заказы потребителей приведены в таблице.

Требуется оптимизировать план перевозок.

Таблица 4.1

Запасы и заказы

	Потребитель 1	Потребитель 2	Потребитель 3	Запасы
Поставщик 1	130	70	140	300
Поставщик 2	110	80	120	480
Поставщик 3	60	100	100	200
Поставщик 4	140	80	100	300
Поставщик 4	70	120	90	360
Заказы	580	640	420

Методические рекомендации по выполнению задания.

1. Организуйте данные в MS Excel так, как показано на рис. 4.1.

Рис. 4.1.

2. В ячейках G4 : G8 укажите суммы произведения цены перевозки единицы груза на объем перевозки от i-го поставщика к любому потребителю.

В ячейке G9 – сумму этих сумм, являющуюся целевой функцией, которую нужно минимизировать (=СУММ(G4:G8)).

В ячейки G12 – G16 введите ограничения на количество груза, которое нужно увезти от каждого поставщика (=СУММ(B12:D12)-E12).

В ячейках В18 : D18 = 0 стоят ограничения на количество груза, которое нужно привезти к каждому потребителю (=СУММ(B12:B16)-B17).

3. Вызовите процедуру Поиск решения из меню Сервис и укажите параметры:

• Целевая ячейка: G9 (минимум)

• Изменяя ячейки: В12 : D16

• Ограничения: В12 : D16>=0 (перевозки неотрицательны),

• G12 : G16 =0 (ограничение на количество груза от каждого поставщика),

• В18 : D18 = 0 (ограничение на количество груза для каждого потребителя).

При такой организации данных все перевозки окажутся целыми числами (если целыми являются числа в колонках «Запасы» и в строке «Заказы»).

Проверим, что в полученном решении m+n-1 ненулевых перевозок.

В итоге мы получим минимальную величину издержек, равную 132000 денежным единицам (см. рис. 4.2).

Рис. 4.2

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