Referat.me

Название: Эффективное распределение ресурсов, транспортная задача

Вид работы: доклад

Рубрика: Информатика

Размер файла: 116.25 Kb

Скачать файл: referat.me-129878.docx

Краткое описание работы: Доклад на тему «Эффективное распределение ресурсов. Транспортная задача.» В настоящее время большое прикладное значение имеет задача распределения ресурсов по работам. Значение этой проблемы определяется, во-первых, ограниченностью ресурсов и, во-вторых, тем, что эффективность ресурсов в разных направлениях может быть различна.

Эффективное распределение ресурсов, транспортная задача

Доклад на тему

«Эффективное распределение ресурсов. Транспортная задача.»

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

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

Оптимальное распределение ресурсов - такое распределение ресурсов, которое обеспечивает наилучшее, наиболее эффективное их использование в соответствии с заданным критерием оптимальности.

Критерий оптимальности - признак, по которому вариант функционирования системы признается наилучшим из возможных.

Проблема оптимального распределения ресурсов решается с помощью методов линейного.

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций, задаваемых системами линейных уравнений и неравенств.

Математическая формулировка задачи линейного программирования ставится следующим образом:

нужно определить максимум линейной целевой функции (линейной формы)

(1)

при условиях

при . (2)

Примером задачи линейного программирования можно назвать задачу об оптимальном рационе, когда необходимо минимизировать стоимость продуктов (f(x)), но при этом получить минимум необходимых веществ (белков, жиров. углеводов).

Основными алгоритмами решения общей задачи линейного программирования являются:

· графический метод

· симплекс-метод

Графический метод является наиболее простым в случае наличия в системе 2-х переменных, которые мы оптимизируем. Тогда мы получаем решение на плоскости. При наличии 3-х переменных мы получаем задачу в пространстве Для его осуществления необходимо построить полуплоскости для каждого ограничения (2). После чего выделить область их пересечения (это будет область допустимых значений, если пересечений нет – то значит нет решения), а затем построить градиент целевой функции.

Далее строим перпендикуляр к градиенту (лучше всего в точке (0,0)) и перемещаем его в сторону границ выделенной области.

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

Наиболее популярная задача эффективного распределения ресурсов - транспортная задача.

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

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

Имеется ряд пунктов производства A 1 , A 2 , ..., Am с объемами производства в единицу времени (месяц, квартал), равными соответственно a 1 , a 2 , ..., am ,, и пункты потребления B 1 , B 2 , ..., Bn , потребляющие за тот же промежуток времени, соответственно b 1 , b 2 , ..., bn продукции.

Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю — эти величины обозначим cij . В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые xij .

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет то, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта

и каждый поставщик отгружает весь произведенный им продукт

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

Последовательность действий:

1. Нахождение опорного плана

2. Оптимизация с помощью метода потенциалов

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

Из трех холодильников Ai , i =1,3, вмещающих мороженную рыбу в количествах a i , необходимо последнюю доставить в пять магазинов B j , j =1-5 в количествах b т. Стоимости перевозки 1т рыбы из холодильника i A в магазин j B заданы в виде матрицы

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

1 a =320, 2 b =140, 20 23 20 15 24

2 a =280, 3 b =110, С = 29 15 16 19 29

3 a =250, 4 b =230, 6 11 10 9 8

1 b =150, 5 b =220

Составим опорный план по правилу минимального элемента.

Введем некоторые обозначения: Ai* - излишек нераспределенного груза от

поставщика Ai, Bj* - недостача в поставке груза потребителю Bj.

Находим незанятую клетку с минимальным тарифом: (3,1). Помещаем туда меньшее из чисел A3*=250 и B1*=150.

Находим незанятую клетку с минимальным тарифом: (3,5). Помещаем туда меньшее из чисел A3*=100 и B5*=220.

Находим незанятую клетку с минимальным тарифом: (1,4). Помещаем туда меньшее из чисел A1*=320 и B4*=230.

Находим незанятую клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2*=280 и B2*=140.

Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=140 и B3*=110. Находим незанятую клетку с минимальным тарифом: (1,5).

Помещаем туда меньшее из чисел A1*=90 и B5*=120.

Находим незанятую клетку с минимальным тарифом: (2,5). Помещаем туда меньшее из чисел A2*=30 и B5*=30.

Пришли к таблице:

Транспортные расходы составят z = 12040 .

Решим задачу методом потенциалов.

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j,

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

U1=0

V4=C1,4-U1= 15

V5=C1,5-U1= 24

U2=C2,5-V5=5

U3=C3,5-V5=-16

V2=C2,2-U2= 10

V3=C2,3-U2= 11

V1=C3,1-U3= 22

Для свободных клеток определим значения оценок (разностей между прямыми и косвенными тарифами).

S1,1 = С1,1 - (U1 + V1) = -2 .

S1,2 = С1,2 - (U1 + V2) = 13.

S1,3 = С1,3 - (U1 + V3) = 9.

S2,1 = С2,1 - (U2 + V1) = 2.

S2,4 = С2,4 - (U2 + V4) = -1 .

S3,2 = С3,2 - (U3 + V2) = 17.

S3,3 = С3,3 - (U3 + V3) = 15.

S3,4 = С3,4 - (U3 + V4) = 10.

Имеем две клетки с отрицательными оценками – (1,1) и (2, 4). Выбираем клетку с наименьшей оценкой (1, 1) и строим для нее цикл.

Перемещаем по циклу груз величиной в 90 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

В результате перемещения по циклу получим новый план:

Целевая функция (транспортные расходы) z = 11860 . Значение целевой функции изменилось на 180 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

U1=0

V1=C1,1-U1= 20

V4=C1,4-U1= 15

U3=C3,1-V1=-14

V5=C3,5-U3= 22

U2=C2,5-V5=7

V2=C2,2-U2= 8

V3=C2,3-U2= 9

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = С1,2 - (U1 + V2) = 15.

S1,3 = С1,3 - (U1 + V3) = 11.

S1,5 = С1,5 - (U1 + V5) = 2.

S2,1 = С2,1 - (U2 + V1) = 2.

S2,4 = С2,4 - (U2 + V4) = -3 .

S3,2 = С3,2 - (U3 + V2) = 17.

S3,3 = С3,3 - (U3 + V3) = 15.

S3,4 = С3,4 - (U3 + V4) = 8.

Имеем клетку (2, 4) с отрицательной оценкой, план не оптимален. Строим для этой клетки цикл.

Похожие работы

  • Изучение и описание живой и неживой системы с точки зрения классификации информационных систем

    Северо-Казахстанский государственный университет Кафедра информационных систем Доклад На тему: «Изучение и описание живой и неживой системы с точки зрения классификации информационных систем»

  • Планирование организации работ над проектом программ

    МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ДОНЕЦКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Лабораторная работа № 2 По дисциплине: «Технология программирования и создания программных продуктов»

  • Решение транспортных задач в Excel

    Министерство образования Российской Федерации Саратовский Государственный Технический Университет Кафедра «Организация перевозок и управление на транспорте»

  • Решение практической задачи на паскале

    ГОУ ВПО «Московский государственный открытый университет» Чебоксарский политехнический институт (филиал) Кафедра информационных технологий и программирования

  • Межорганизационные информационные системы 2

    МЕЖОРГАНИЗАЦИОННЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ Многие специалисты считают, что в настоящее время происходит поворот от индустриальной к информационной экономике. За последние три десятилетия скорость развития и функциональная направленность использования ИТ возросли, заставляя переосмыслить ценность информации.

  • Внедрение беспроводной связи для Ж Д GSM-R

    Курсовая работа по курсу «Управление проектами в области информационных систем» На тему: «Внедрение беспроводной связи для Ж/Д GSM-R» Планирование основных фаз и операций в проекте, определение длительности работ

  • Системные программы

    Контрольная работа по дисциплине: "Информатика" СОДЕРЖАНИЕ Системные программы Введение……………………………………………………………………………...3 1.Системное программное обеспечение. Понятие и функции……………………4

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

    Лабораторная работа 2 Теоретическая часть Задача о размещении(транспортная задача) – это распределительная задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов.

  • Алгоритм оптимального календарного планирования работ по упреждению аварийных ситуаций

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

  • Управление проектами с помощью Instant Business Network

    ГОУ ВПО «РЭУ им. Г.В. Плеханова» Факультет «Финансы и кредит» Кафедра информационных технологий Доклад на тему: «Управление проектами с помощью Instant Business Network»