![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Программирования.
Это отдельный вид задачи ЛП. Экономически эта задача формулируется так: Есть Обозначим через
Система ограничений состоит в том, что вывоз продукции ограничен объемом производства, а доставка объемами потребления. Система ограничений зависит от соотношения суммарного объема производства к суммарному объему потребления. Возможны три случая:
В первом случае вся продукция из пунктов производства вывозится и доставляется потребителям в необходимом объеме. Ограничения записываются в виде равенств, т.е.
Транспортная задача в постановке 10 – 11 называется сбалансированной задачей, а вид записи – каноническим. Во втором случае изготавливается продукции больше, чем потребляется. Т.е., часть продукции остается не потребленной. Ограничения задачи записываются так:
ТЗ в постановке 10, 12 называется несбалансированной, случай перепроизводства. В третьем случае продукции, которая производится недостаточно для удовлетворения спроса. Т.е. не все потребители получат достаточное количество продукции. Ограничения задачи запишутся так:
ТЗ в постановке 10, 13 называется несбалансированной, случай недопотребления. Любая несбалансированная задача может быть приведена к сбалансированной. Для случая перепроизводства вводится фиктивный потребитель, который заберет весь остаток не потребленной продукции. А практически это означает, что продукция останется на складах предприятий производителей. Для случая недопроизводства вводится фиктивный производитель, который условно дает всю не достающую продукцию. А практически это означает, что потребители не дополучили продукцию. Ввод фиктивного потребителя или фиктивного производителя это абсолютно математический прием, который нужен для возможности решения задачи. Таким образом, если 1) 2)
И так чтобы начать решение транспортной задачи мы должны представить ее в сбалансированном виде (каноническом виде). Планом ТЗ будет матрица, в которой соблюдается баланс строк и столбцов.
Начальный опорный план может быть определен разными способами. Наиболее распространенными из них являются метод северо – западного угла и метод наименьшего элемента. Рассмотрим на примере эти два метода. При использовании метода северо-западного угла заполнения матрицы положительными элементами начинают из компоненты Следующим ненулевым элементом будет При определении опорного плана методом наименьших элементов принимает участие матрица стоимостей, элементы которой направляют. В матрице Рассмотрим пример.
Пример:
Задача не сбалансирована. Случай перепроизводства. Вводим фиктивного потребителя.
Построим начальный опорный план методом северо-западного угла:
Построим начальный опорный план методом минимального элемента:
Решить транспортную задачу можно используя метод потенциалов.
Вопрос для самоподготовки 1. От чего зависит структура системы ограничений транспортной задачи? 2. Экономическое значение фиктивного потребителя. Как это использовать при определении количеству нужного продукта? 3. Чем отличаются и что общее для методов северо-западного угла и метода наименьших элементов?
ЛЕКЦИЯ 8.
|