КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Задачи линейного программирования
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Типичные классы задач Накопленный опыт в решении практических задач исследования операций позволяет выделить по содержательной постановке типичные классы задач[1,2}. 1. Управления запасами 2. Распределения ресурсов 3 Ремонта и замены оборудования 4 Массового обслуживания 5 Упорядочения 6 Сетевого планирования и управления 7 Выбора маршрута 8 Комбинированные
Среди известных разделов математического программирования наиболее развитым и законченным является линейное программирование (ЛП). Несмотря на требования линейности целевой функции и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи, задачи теории расписаний и т.д. В качестве примера рассмотрим задачу о перевозках. Имеется m cкладов: С1, С2,……., Сm и n пунктов потребления П 1, П 2,……,П n. Необходимо составить план перевозок со складов С1, С2,……., Сm в пункты П 1, П 2,……,П n некоторого товара. На складах имеются запасы товара в количествах а1, а2,……, аm единиц. Пункты потребления подали заявки соответственно на b1, b2,…..bn единиц товара. Заявки выполнимы, т.е. сумма всех заявок не превосходит суммы всех имеющихся запасов: ∑b ≤ ∑a, Склады С1, С2,……., Сm связаны с пунктами потребления П 1, П 2,……,П n какой-то сетью дорог с определенными тарифами на перевозки. Стоимость перевозки со склада Сi в пункт Пj равна сij (i = 1,2,...,m, j = 1,2,…, n). Требуется составить план перевозок, т.е. указать, с какого склада в какие пункты и какое количество товара нужно направлять так, чтобы заявки были выполнены, а общие расходы на все перевозки были минимальными.
Обозначим x i j -- количество единиц товара, направляемое со склада Сi в пункт Пj. Решение (план перевозок) состоит из mn чисел:
x 11, x12,.......,x1n x 21, x22,.......,x2n ...................... x m1, xm2,.......,xmn
образующих прямоугольную таблицу (матрицу). Сокращенно ее обозначают (x i j). Требуется такие неотрицательные значения переменных x i j, чтобы были выполнены следующие условия: 1.Емкость складов не должна быть превышена, т.е. общее количество товара, взятое с каждого склада, не должно превышать имеющихся в нем запасов:
x 11 + x12 +...... x1n ≤ a1; x 21, + x22 +....... + x2n ≤ a2; ...................... x m1 + xm2 +....... + xmn ≤ am, . 2.Заявки, поданные пунктами потребления, должны быть выполнены:
x 11 + x12 +....... + x1n = b1; x 21, + x22 +....... + x2n = b2; ...................... x m1 + xm2 +....... + xmn = bm, Общая стоимость перевозок L L = c11 x11 + c12 x12 +.... + c1n x1n + c21 x21 + c22 x22 +.... + c2n x2n + ......+ cm1 xm1 + cm2 xm2 +.... + cm n xm n,
или, гораздо короче, m n L = ∑ ∑ cij xij. i = 1 j = 1 Требуется так выбрать план перевозок (x i j), чтобы стоимость L этих перевозок обратить в минимум. В данном случае мы имеем задачу линейного программирования, в которой ограничительные условия имеют вид как линейных неравенств, так и линейных равенств. Такая задача о перевозках носит название транспортной задачи.
Дата добавления: 2014-01-07; Просмотров: 319; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |