Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Вербальная постановка задачи
Планируются перевозки одного вида материально-техни- ческих средств (МТС) от нескольких поставщиков нескольким потребителям. Известны запасы материально-технических средств поставщиков и потребности в МТС потребителей. Из- вестна или может быть вычислена стоимость перевозки едини- цы МТС из каждого исходного пункта (каждого поставщика) в каждый пункт назначения (каждому потребителю). Величина транспортных расходов на любом маршруте прямо пропорци- ональна объему перевозимых МТС. Потребности каждого пот- ребителя могут удовлетворяться за счет нескольких постав- щиков. Цель планирования состоит в определении количества МТС, которые следует перевезти от каждого поставщика каж- дому потребителю, с тем чтобы общие транспортные расходы были минимальными (рис. 10.1).
(10.1)
которую можно обозначить ||Xij ||. Совокупность неизвестных Xij (10.1), удовлетворяющая ог- раничениям первой и второй групп в (10.2), называется планом перевозок. План, для которого достигается минимум первого выражения в (10.2), называется оптимальным. Величины же Xij называются перевозками. Поставщики Потребители
a1 b1
ai bi
am bn Рис. 10.1. Организация перевозок МТС: m — количество поставщиков; n — количество потребителей; ai — запасы МТС i-го поставщика; bj — потребности в МТС j-го потребителя; cij — стоимость перевозок; xij — количество перевозимых МТС
В нашем случае математическая постановка транспор- тной задачи линейного программирования в общем виде будет выглядеть следующим образом:
при ограничениях (10.2)
x ij ≥ 0 для всех i и j Первая группа ограничений указывает, что суммарный объем перевозимых МТС от некоторого поставщика не мо- жет превышать сосредоточенных в нем запасов МТС. Вторая группа ограничений требует, чтобы суммарные перевозки МТС некоторому потребителю полностью удовлетворяли бы его спрос.
Если в задаче (10.2) все неравенства выполняются как ра- венства, т. е. суммарный объем запасов МТС равен суммар- ному спросу, то транспортную модель называют сбалансиро- ванной транспортной моделью. Именно для сбалансированной транспортной модели разработаны эффективные методы ре- шения. Если суммарный спрос меньше суммарных запасов, т. е.: то переход к сбалансированной модели осуществляют путем введения в рассмотрение фиктивного потребителя с номером n+1 с заявкой: При этом стоимость перевозки МТС фиктивному потреби- телю принимается равной нулю (c i, n +1 = 0, ∀ i). Если суммарные запасы меньше суммарного спроса, т. е.: то вводят фиктивного поставщика с номером m + 1 и запасом при нулевой стоимости перевозок МТС от этого поставщика (c m +1, j = 0, ∀ j). Следует заметить, что в оптимизационной задаче (10.2) маршруты перевозок должны быть маршрутами “минималь- ной стоимости”. Для более компактного представления транспортной моде- ли используют так называемую транспортную таблицу, кото- рая может иметь следующий вид:
Приведем наглядный пример: необходимо со склада города (гор.) и области (обл.) перевезти потребное число МТС потреби- телям (потр.). Тогда транспортная таблица будет иметь следу- ющий вид (табл. 10.1): Таблица 10.1
*ВП — возможности поставщиков. Стоимость перевозки будет иметь вид: Сij = νij · Lij, где Lij — расстояние между i и j пунктами; νij — стоимость перевозки 1 условной единицы груза на 1 единицу расстояния. Если νij = 1 условной единице, то Сij = Lij.
Решение транспортной задачи Так как транспортная задача является задачей линейного программирования, то основные этапы ее решения будут таки- ми же, как и при решении задачи линейного программирования симплекс-методом, а именно:
I этап. Нахождение начального допустимого решения. II этап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то сле- дует закончить вычисления; в противном случае — перейти к III этапу. III этап. Выбор выводимой из базиса переменной (исполь- зуя условия допустимости) из числа переменных текущего ба- зиса; затем нахождение нового базисного решения и возвраще- ние ко II этапу. Рассмотрим подробнее каждый этап решения транспорт- ной задачи, учитывая ее специфику.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-01-14; просмотров: 121; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.84.33 (0.01 с.) |