Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Методическая разработка урока "ТРАНСПОРТНАЯ ЗАДАЧА"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Методическая разработка урока "ТРАНСПОРТНАЯ ЗАДАЧА"

библиотека
материалов

Транспортная задача

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

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

Составленный план должен обеспечивать выполнение таких условий, как:

  • Полное удовлетворение спроса потребителей;

  • Вывоз всей продукции от поставщика;

  • Минимизация транспортных затрат.

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

Рассмотрим простейший вариант транспортной задачи. В т пунктах отправления (складах) А1, А2, …, Ат находится однородный груз в количестве а1, а2, …, ат единиц соответственно. Потребность в этом грузе в п пунктах назначения (магазинах) В1, В2, …, Вп составляет b1, b2, …, bn соответственно. Будем считать, что сумма запасов на складах равна суммарным потребностям в магазинах, т.е. = . Такая модель называется замкнутой.

Обозначим через Сij удельные затраты, т.е. затраты на перевозку единицы груза из i-го пункта в j-й пункт назначения, а через Xij – неизвестный объем груза, который надор перевезти из j- го пункта отправления в j-й пункт назначения.

Перевозку груза надо организовать таким образом, чтобы суммарные затраты на перевозки были минимальными. Суммарные затраты на перевозки Z определяются следующим образом: необходимо просуммировать все объемы перевозок груза, умноженные на соответствующие удельные затраты, т.е. Z=. Суммарные затраты являются целевой функцией.

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

Рассмотрим транспортную задачу на примере четырех складов и четырех магазинов.

Задача. Известно, что на складах имеется запас муки в количестве 45, 100, 20, 75 мешков. А магазины имеют потребность в этом товаре в количестве 30, 80, 95, 35 мешков.


Ячейки, выделенные фоном, содержат удельные стоимости перевозок Cij. Например, стоимость перевозки единицы груза (мешка) со склада № 3 в магазин № 4 составляет 11 денежных единиц. Проверим замкнутость модели. Для этого просуммируем все запасы муки на складах: 45 + 100 + 20 + 75 = 240. Найдем суммарные потребности магазинов в муке: 30 + 80 + 95 + 35 = 240. Таким образом, модель является замкнутой, т. е. потребность магазинов в муке равна запасу на складах.

Весь груз со складов должен быть вывезен. Этот факт для i-го склада можно отразить следующим образом: Xi1 + Xi2 + Xi3 + Xi4 = ai. Весь груз в магазины должен быть ввезен. Для j-го магазина будет справедливо следующее: X1j + X2j + X3j + X4j = bj.

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


Вывоз всего груза со складов достигается при выполнении системы уравнений:


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

Z = C11 X11 + … + C14X14 + C21 · X 21 + … + С24 · X24 + C31 · X31 +…+ C34 · X34 +C41 · X41 +…+ C44 · X44.

Решение с помощью электронных таблиц

Рассмотрим решение задачи на примере табличного процессора Microsoft Excel.

Представим данные в виде, показанном в таблице 1.

=СУММПРОИЗВЕД(С3:F16;C13:F16)



Исходными данными являются удельные затраты на перевозки (диапазон ячеек C13:F16), запасы муки на складах (диапазон ячеек A13:A16), потребности магазинов в муке

( диапазон ячеек С11:F11).

Диапазон ячеек C3:F6 предназначен для получения искомого решения-объемов перевозок груза. Суммируя объемы перевозок в каждой строке, задаем левые части уравнений-ограничений, обеспечивающий вывоз всего груза с каждого склада. Суммированием объемов перевозок по столбцам задаются левые части уравнений-ограничений, удовлетворяющих спрос каждого магазина в муке. Формула =СУММПРОИЗВ (С3:F6; C13:F16), вычисляющая целевую функцию(суммарные затраты) Z, размещена в ячейке С19. Встроенная функция СУММПРОИЗВ суммирует произведения, полученные построчным перемножением содержимого ячеек из диапазонов С3:F6; C13:F16.

Например, СУММПРОИЗВ (А1:В2;А3:B4) =A1*A3+B1*B3+A2*A4+B2*B4.

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

В результате будет найдено решение, представленное в таблице 2.

1455




Искомые объемы перевозок представлены в ячейках C3:F6. Со склада №1 мука будет отправлена в магазины №2 и 3 в объемах 10 и 35 мешков соответственно, со склада №2 – в магазины №1 и 2 в объемах 30 и 70 мешков, со склада №3 - в магазин №3 в объеме 20 мешков, со склада №4 в магазины №3 и 4 в объемах 40 и 35 мешков. Минимальные затраты на перевозки составляют 1455 денежных единиц.

Литература:

Информатика и ИКТ. Профильный уровень: учебник для 11 класса. / И.Г. Семакин,Е.,К.Хеннер, Л.В.Шестакова.— М.: БИНОМ, Лаборатория знаний, 2012. — 330 с.




Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 27.11.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров54
Номер материала ДБ-393776
Получить свидетельство о публикации
Похожие материалы

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