Транспортная задача - Задание 1

Порядок выполнения работы:

Фирма, обслуживающая туристов, прибывающих на отдых, должна разместить их в четырех отелях: «Морской», «Солнечный», «Слава», «Уютный», в которых забронировано соответственно 3, 10, 18 и 14 мест. Туристы прибывают поездом, самолетом и теплоходом в количестве 15, 25 и 5 человек соответственно. Транспортные расходы фирмы по перевозке занесены в таблицу.

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

Решение. В этом варианте ТЗ речь идет о рациональной перевозке туристов («однородный продукт») от пункта прибытия («от поставщика») к отелям («к потребителям» этого продукта).

1. Составим математическую модель задачи и проверим задачу на замкнутость.

Введем обозначения: x_ij - количество туристов, перевозимых из i-го пункта прибытия в j-й отель (i =1: m, j =1: n, в нашей задаче m=3, n=4);

a_i - количество туристов, прибывших на ж/д вокзал, в аэропорт и на морской вокзал (a₁=15, a₂=25, a₃=5);

bj - количество мест, забронированных в отелях (b₁=3, b₂=10, b₃=18, *4=14);

c_ij - стоимости перевозок из пункта i прибытия в пункт j размещения.

Транспортные расходы на перевозки из пункта i прибытия в пункт j размещения.

Целевая функция . В нашей задаче

Ограничения общего вида заданы двумя условиями:

1) все туристы должны быть доставлены из пунктов прибытия в отели;

2) на всех забронированных в отелях местах должны быть размещены туристы.

и

и

и ,

Ограничения на неотрицательность переменных: x_ij ≥ 0.

Проверим ТЗ на замкнутость:

т.е. задача замкнутого типа.

Другие ограничения – количество туристов x_ij – целые числа.

Неизвестными переменными в нашей задаче будут количество туристов x_ij, заселившихся в разные отели.

Теперь введем условие задачи – оптимизируемую модель в Excel в виде, наиболее удобном для дальнейших вычислений, как показано ниже:

Рис.1 – Внешний вид оптимизируемой модели в Excel

Здесь, в ячейках C11: F13 размещены начальные значения неизвестных (x ₁₁, х₁₂, х₁₃, х₁₄, …, x_ij) =0. В ячейках В4: В6 записаны граничные значения количества прибывших туристов в пункты прибытия. В ячейках С7: F7 записаны граничные значения количества забронированных мест в отелях. В ячейках В11: В13 записаны формулы для ограничений количества заселившихся туристов: = x ₁₁+х₁₂+х₁₃+х₁₄, = x ₂₁+х₂₂+х₂₃+х₂₄, = x ₃₁+х₃₂+х₃₃+х₃₄. В ячейках C14: F14 записаны формулы для ограничений количества туристов по отелям: = x ₁₁+х₂₁+х₃₁, = x ₁₂+х₂₂+х₃₂, = x ₁₃+х₂₃+х₃₃, = x ₁₄+х₂₄+х₃₄. Целевая функция в общем виде записывается в ячейке В19: = с₁₁ ∙ x ₁₁+ с₂₁ ∙ х₂₁+ с₃₁ ∙ х₃₁+ с₁₂ ∙ x ₁₂+ с₂₂ ∙ х₂₂+ с₃₂ ∙ х₃₂+ с₁₃ ∙ x ₁₃+ с₂₃ ∙ х₂₃+ с₃₃ ∙ х₃₃+ с₁₄ ∙ x ₁₄+ с₂₄ ∙ х₂₄+ с₃₄х₃₄. Или же в ячейке В19: = 10 ∙ x ₁₁+12 ∙ х₂₁+0 ∙ х₃₁+ 5 ∙ x ₁₂+7 ∙ х₂₂+14 ∙ х₃₂+20 ∙ x ₁₃+9 ∙ х₂₃+16 ∙ х₃₃+11 ∙ x ₁₄+20 ∙ х₂₄+18 ∙ х₃₄.

Нам осталось запустить поиск решения Данные► Поиск р ешения… и ввести адреса ячеек и ограничения, как на рисунке 2:

Рис.2 – Внешний вид диалогового окна «Поиск решения»

Результат поиска решения выглядит так:

Рис 3 – Результаты поиска

Здесь в ячейках C11: F13 подобрано оптимальное количество туристов, дающее минимальные транспортные расходы, равные 394$. Проанализируйте полученное решение.

Поэкспериментируйте: попробуйте вручную изменить подобранные значения, оцените значения целевой функции. Повторно вызовите инструмент Поиск решения, удалив условие x_ij – целые числа или добавив новое условие, и выполните подбор.

Задание 2 - Оптимизация использования ресурсов

Предприятие изготавливает и продает краску двух видов: для внутренних и наружных работ. Для ее производства используется два исходных продукта: A и B. Расходы продуктов A и B на 1т соответствующих красок и запасы этих продуктов на складе приведены в таблице.

Отпускная цена за 1 тонну краски для внутренних работ составляет 2 000 рублей, краска для наружных работ продается по 1 000 рублей за 1 тонну.

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

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

1. Переменные задачи. Обозначим: х₁ - количество производимой краски для внутренних работ; х₂ - для наружных работ.

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

х ₁, х ₂ > 0;

по расходу продукта A: 1, 3 х ₁ + 2, 1 х ₂ < 4, 8;

по расходу продукта B: 2, 6 х ₁ +1, 6 х ₂ < 8, 5.

В левых частях последних двух неравенств определены расходы продуктов A и B, в правых указаны их запасы.

3. Целевая функция задачи. Обозначим Z доход от продажи краски (тыс. руб.), тогда целевая функция задачи записывается так:

Z = 2х₁ + х₂,

таким образом, задача состоит в том, чтобы найти

max Z=2x₁+x₂,

при ограничениях:

1, 3 х ₁ + 2, 1 х ₂ < 4, 8

2, 6 х ₁ +1, 6 х ₂ < 8, 5

х1, х2 > 0.

Из решения видно, что для получения максимальной прибыли предприятию нужно израсходовать: продукта А - 4, 25 т и продукта В - 8, 5 т. Полученная Вами прибыль составит 6 538, 46 руб. Полученный результат поиска оптимального решения приведен на рис.4.

Рис.4

Поэкспериментируйте: попробуйте изменить исходные значения, например:

Повторно вызовите инструмент Поиск решения и получите новое решения и проанализируйте его.