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

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

Практическая работа 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

Дата добавления: 2017-02-01