Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-12-21 | 163 |
5.00
из
|
Заказать работу |
|
|
31) Транспортная задача линейного программирования, ее математическая модель.
Под названием транспортная задача объединяется широкий круг задач ЛП с единой математической моделью, т.к. это задача ЛП, то для ее решения может применятся один из уже известных методов(симплексный, двойственный, искусственный базис) Однако, в силу специфики мат. модели для их решения был разработан специальный метод- метод потенциала. Данный метод, как и симплексный, начинается с поиска начального решения, затем найденное решение проверяется на оптимальность и при необходимости осуществляется построение более оптимального плана.
Постановка задачи:
Однородный груз сосредоточен у m поставщиков А1, А2…..Am в объемах а1, а2…аm.
Данный груз необходимо доставлять n потребителям В1, В2…Вn, которые формируют заявки на груз в объемах в1, в2…вn.
Известны затраты (тарифы) на перевозку единицы груза от i-го поставщика J-му потребителю.
Сij(i=1,m, j=1,n)- затраты на перевозку.
Требуется составить такой план перевозки, при котором запасы всех поставщиков будут вывезены, заявки всех потребителей удовлетворены, а суммарные затраты на перевозку всех грузов будут минимальны.
Занесем все условия задачи в специальную транспортную таблицу
Потребит поставщ | B1 | B2 | … | Bn | Запасы ai |
A1 | c11 x11 | c12 x12 | … | c1n x1n | a1 |
A2 | c21 x21 | c22 x22 | … | c2n x2n | a2 |
… | … | … | … | … | … |
Am | cm1 xm1 | cm2 xm2 | … | cmn xmn | am |
Спрос bj | b1 | b2 | … | bn | ∑ai(i=1,m) ∑bj(j=1,n) |
Математическая модель транспортной задачи:
Пусть Х= х11 х12… х1n
х21 х22… х2n
………………………
xm1 xm2…xmn
- это план перевозки грузов
от каждого поставщика к каждому потребителю хij≥0 (i=1,m; j=1,n)
Суммарные затраты на перевозку грузов будут составлять ∑∑сij xij.
|
Поскольку эти затраты нужно минимизировать, то имеем целевую функцию
F(X)= ∑∑cij xij->min
Груз, выводимый от одного поставщика, определяется суммой всех переменных по строке
∑ xij(j=1,n).
И так как весь груз должен быть выведен, то эта сумма должна равняться запасам поставщика
∑xij=ai(j=1,n) i=1,m.
Груз, направляемый одному потребителю, т.е. сумма переменных по столбцу должен полностью удовлетворять его потребностям
∑xij= bj (i=1,n)
J=1,n
Т.о. математическая модель задачи принимает вид: найти оптимальный план перевозки грузов от поставщиков к потребителям, минимизирующие затраты на перевозку
F(x)= ∑∑cij xij->min при ограничениях:
∑хij=ai(j=1,n)
∑xij=bj(i=1,m)
xij≥0
32)Открытая и закрытая модели транспортной задачи. Приведение открытой модели к закрытой.
Модель ТЗ называется закрытой(задача с правильным балансом), если суммарные запасы поставщиков совпадают с суммарным спросом потребителей.
Если данное условие не выполняется, т.е. ∑ai≠∑bj (i=1,m, j=1,n), то модель открытая, а задача с неправильным балансом.
Открытую модель необходимо привести к закрытому виду, при этом возможно 2 случая:
1) ∑ai>∑bj (i=1,m. j=1,n) запасов больше, чем заявок. В этом случае вводят фиктивного потребителя Вn+1, который формирует спрос на груз в объеме bn+1=∑ai-∑bj(i=1,m j=1,n).
Тарифы данного потребителя считаем равными нулю.
2) ∑ai< ∑ bj(i=1, m j=1,n) спрос превышает имеющиеся запасы, в этом случае вводят фиктивного поставщика Am+1,запасы которого составляют am+1= ∑bj- ∑bi(j=1,n i=1,m).
Тарифы для данного поставщика равны нулю.
После того, как задача приведена к закрытому виду можно приступать к поиску начального опорного решения.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!