Необходимое и достаточное условия разрешимости транспортной задачи. Рассмотрение методов построения начального опорного решения. Особенности решения транспортных задач с неправильным балансом. Алгоритм решения транспортной задачи методом потенциалов.
Аннотация к работе
Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин. Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальным выходом заготовок).В простейшем виде, когда распределяется один вид продукта и потребителям все равно, от кого из поставщиков его получать, задача формулируется следующим образом. Исходная информация: Mi - количество единиц груза в i-м пункте отправления (i = 1, 2, …, k ); Обозначим через xij планируемое количество единиц груза для перевозки из i-ro пункта в j-й. В простейшем случае должны выполняться следующие очевидные условия: Таким образом, математической формулировкой транспортной задачи будет: найти при условиях ; ;Простейшими транспортными задачами являются задачи о перевозках некоторого однородного груза из пунктов отправления (от поставщиков) в пункты назначения (к потребителям) при обеспечении минимальных затрат на перевозки. Например, для k поставщиков и l потребителей такая задача имеет следующий вид: Здесь показатели aij означают затраты на перевозку единицы груза от i-го поставщика (i =1,2,…,k ) к j-тому потребителю (j =1,2,…,l ), Mi - мощность i-того поставщика в планируемый период, Nj - спрос j-того потребителя на этот же период. Обозначим через xij поставку (количество груза), которая планируется к перевозке от i-того поставщика к j-тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, т.е. функции при ограничениях Система ограничений включает k уравнений, связывающих поставки i-того поставщика с мощностью Mi (i=1,2,…,k ) этого поставщика, и l уравнений, связывающих поставки j-тому потребителю со спросом Nj (j =1,2,…,l ) этого потребителя.Ограничение и условия не отрицательности переменных, исключающие обратные перевозки xij >0; i= 1, 2, …, k ; j = 1, 2,., l. Эти условия образуют систему ограничений. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения. Сложим элементы xij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим . Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие .Согласно теореме о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться r отличных от нуля координат, где r - ранг системы ограниченийОпорное решение (опорный план, базисное решение, basic solution) - одно из допустимых решений, находящихся в вершинах области допустимых решений. При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких "вершинных" решений, не обязательно оптимальное, и принять его за исходный пункт расчетов.Начав заполнение с клетки (1.1) - "северо-западного угла" таблицы, ступенями спускаются вниз до клетки (k, l ), вычеркивая либо одну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k-я) строка и последний (l-й) столбец.При построении первоначального плана по способу северо-западного угла совершенно не учитываются тарифы, потому план получается весьма далеким от оптимального. Способ минимального элемента учитывает тарифы и потому позволяет найти план, более близкий к оптимальному. В клетку с минимальным тарифом записываем наибольшую возможную перевозку (исходя из запасов и потребностей), затем заполняем очередную по порядку клетку и т.д., пока не получим план. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений. Наличие положительной оценки свободной клетки () при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению.Распределительный метод решения транспортной задачи отличается от метода потенциалов некоторым изменением вычислительного процесса и иным (по форме) критерием оптимальности.
План
Содержание
Введение
1. Формулировка транспортной задачи
2. Математическая модель транспортной задачи
3. Необходимое и достаточное условия разрешимости транспортной задачи
4. Свойство системы ограничений транспортной задачи
5. Опорное решение транспортной задачи
6. Методы построения начального опорного решения
6.1 Построение первоначального плана по способу северо-западного угла
6.2 Построение первоначального плана по способу минимального элемента
7. Переход от одного опорного решения к другому
8. Распределительный метод
9. Метод потенциалов
10. Особенности решения транспортных задач с неправильным балансом
11. Алгоритм решения транспортной задачи методом потенциалов
11.1 Предварительный шаг
11.2 Общий повторяющийся шаг
12. Транспортная задача с ограничениями на пропускную способность
13. Транспортная задача по критерию времени
14. Применение транспортной задачи для решения экономических задач