Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 22
Текст из файла (страница 22)
Добавляя новые неотрицательные переменные хт„+1, 1 = 1,..., тп, приходим к замкнутой модели транспортной задачи с ограничениями в виде равенств (а) — (Ь). Если суммарные запасы отправителей меньше суммарных запросов л3 л пунктов назначения, т.е. 2,'а, ( 2 Ь, то равенства (Ь) заменяются у=! а условие (а) остается без изменений.
В этом случае вводится фиктивный л пункт отправления А +! с требуемой величиной вывоза а +, — — 2 6— у=! 2 ау и нулевыми стоимостями перевозок из этого пункта. Добавляя 1=1 новые неотрицательные переменные х 11;, у = 1,...,и, приходим к замкнутой модели транспортной задачи с ограничениями в виде равенств (а)-(Ь). 125 $5. Траиеяортяая задача Глава 2. Ляеейиое ирограммироваиие 124 5.2. Особенностн задача Доказательство.
выполняться: и н хб = Транспортная задача является задачей линейного программирования и может быть решена симплекс-методом, который значительно упрощается в зилу простого строения системы ограничений (а)-(Ь). Этот упрошенный метод мы и опишем ниже. Предварительно докажем некоторые утверждения, имеющие место лля транспортных задач. Лемма 1.
Ялл любой транснартнай задачи существует данусгниммй алан перевозок (Рр ~ !г!). Положим *;, = -'-', тогда уравнения (а) будут а; а; — Ь. = — И =ан т=!,...,т. их- и т=! Аналогично показывается выполнение уравнений (Ь). Значит хб допустимый план перевозок. Отметим, что поскольку значение задачи ограничено снизу нулем и допустимый план перевозок имеется по лемме 1, то в задаче (Р) по теореме существования решения п.3.! (!Яр( ( +со ~ АгдР ~ И) оптимальный план существует. Лемме 2.
Ранг систнемм ограничений (а) — (Ь) равен т+ и — 1. Доказательство. Если сложить первые тп строк матрицы ограничений А и вычесть из них последние п строк, то получим нулевую строку. Следовательно, ранг матрицы А меньше тп+ п. С другой стороны„располагая т — ! строку матрицы А (начиная со второй), под п последними строками, получим треугольную матрицу из тп+и — ! строк, ранг которой равен количеству уравнений (т+и — 1). Таким образом, ранг матрицы А равен т+ п — 1. По предложению ! п.3.2 (столбцы матрицы ограничений, соответствующие положительным координатам крайней точки, линейно независимы) и лемме 2 (количество линейно-независимых столбцов не превышает тп + и — 1) крайняя точка в задаче может иметь не более т+ п — 1 положительных координат.
Лемме 3. Любие та + п — 1 строк матрицы А линейно неэависимы. Ялнзззтельстзо. Любая строка матрицы А (для определенности возьмем строку из системы уравнений (а)) равна сумме всех строк системы уравнений (Ь) минус сумма всех строк уравнений (а) без этой строки, то есть является линейной комбинацией оставшихся тп+ и — ! строк. А так как ранг матрицы А равен та+ и — 1, то оставшиеся строки линейно независимы. Отметим, что не любые тп+ п — ! столбцов матрицы А являются линейно независимыми (приведите пример!). 5.3.
Методы нахождення начальной крайней точки Рассмотрим замкнутую модель транспортной задачи. 1. Метод ггеверо-занаднага угла*. Назначим максимально возможную перевозку из пункта отправления А, в пункт назначения Во То есть заполняем верхний левый элемент матрицы Х первоначальной крайней точки. При этом либо пункт отправления Аы либо пункт назначения Вм либо оба эти пункта окажутся полностью обслуженными. Если пункт отправления А~ оказался полностью обслуженным, то в дальнейшем при нахождении первоначального плана перевозок выводим из рассмотрения первую строку матрицы Х и рассматриваем только оставшуюся часть матрицы.
Если пункт назначения В~ оказался полностью обслуженным, то аналогично выводим первый столбец из дальнейшего рассмотрения. Если же и пункт отправления, и пункт назначения оказались полностью обслуженными (так может случиться только в вырожденной задаче), то вывести из рассмотрения следует или первый столбец, или первую строку матрицы Х. Условимся для определенности выводить из рассмотрения первый столбец матрицы.
В этом случае в число базисных элементов на следующем этапе введем элемент с нулевым значением перевозки, стоящий в северо-западном углу оставшейся части матрицы Х, т.е.' в базис войдет второй элемент в строке, считая вычеркиваемый элемент первым. Эту процедуру продолжаем до тех пор, пока все пункты отправления и пункты назначения не будут обслужены. Последней перевозкой будет перевозка из пункта отправления А в пункт назначения В„. На каждом шаге обслуживается один из пунктов отправления или назначения, а на последнем шаге обслуживаются и последний пункт отправления и последний пункт назначения. Поэтому число базисных элементов будет ровно тп+ и — 1. Найденный план будет допустимым планом перевозок, содержащим не более та+ п — ! положительных координат и являющийся (как будет показано ниже) крайней точкой множества допустимых элементов.
Отметим, что данный метод нахождения первоначальной крайней точки не учитывает стоимости перевозок. Поэтому начальный план может оказаться далеко не оптимальным. Приведем другие методы нахождения начальной точки, учитывающие стоимости перевозок. 127 !26 Глава 2. Линейное программирование ф 5. Т)гаислоргиая залача 2. Минимум по матрице. Выберем в платежной матрице С минимальный элемент.
Пусть ш1п су = с;,;. Назначим максимально воз- Ф,Я можную перевозку из пункта отправления Ач в пункт назначения В,„. Если минимальная стоимость перевозки достигается на нескольких элементах, то выбираем любой из них. Тем самым пункт отправления Ач или пункт назначения В„(или оба пункта одновременно) будет обслужен. А в платежной матрице соответствующая строка или столбец выводятся из дальнейшего рассмотрения. Если и пункт отправления, и пункт назначения одновременно обслужились, то для определенности как и в и.
1 будем выводить из рассмотрения столбец матрицы Х. В оставшейся части платежной матрицы вновь ищется минимальный элемент и процедура повторяется ло тех пор, пока первоначальный план перевозок не будет получен. Найденный план будет допустимым планом перевозок, содержащим не более го+ л — ! положительных координат с числом базисных элементов го+о-1 и являющийся крайней точкой множествадопустимых элементов. 3.
Минимум по спцюкв. Выберем в первой строке платежной матрицы С минимальный по величине элемент. Предположим ш)пс~ — — с, „. Назначим максимально возможную перевозку из пункта отправления А~ в пункт назначения Вм. Если минимум достигается на нескольких элементах, то выбираем любой из них. Тем самым пункт отправления А~ или назначения В, (или оба пункта одновременно) будет обслужен.
А в платежной матрице первая строка или соответствующий столбец выводятся из дальнейшего рассмотрения. В первой строке оставшейся части матрицы вновь ищется минимальный элемент и процедура повторяется до тех пор пока первоначальный план перевозок не будет получен (первой строкой может оказаться вновь первая строка исходной матрицы без какого-то элемента или вторая строка исходной матрицы без какого-то элемента). В итоге получаем крайнюю точку множества допустимых элементов задачи. 4.
Минимум по столбцу. Выберем в первом столбце платежной матрицы С минимальный элемент. Предположим ш!и с,1 — — сч, Назначим г максимально возможную перевозку из пункта отправления А„в пункт назначения В,. Если минимум достигается на нескольких элементах, то выбираем любой из них. Тем самым пункт отправления А„или пункт назначения В~ будет обслужен. А в платежной матрице соответствующая строка или первый столбец выводятся из дальнейшего рассмотрения.
В первом столбце оставшейся части платежной матрицы вновь ищется минимальный элемент и процедура повторвется до тех пор пока первоначальный план перевозок не булат получен (первым столбцом меж жег оказаться вновь первый столбец исходной матрицы без какого-то элемента или второй столбец исходной матрицы без какого-то элемента). В итоге получаем первоначальную крайнюю точку. Лемма 4. Описанные выше методы нахопсдвния первоначального алана перевозок, приводят к первоначальной крайней точке множества допустимых элементов. Доказательство. По предложению 1 достаточно доказать, что соответствующие базисным элементам столбцы матрицы А линейно независимы. Отметим, что описанные методы нахождения первоначального плана перевозок содержат общий элемент действия: на каждом этапе мы выводим из рассмотрения либо столбец, либо строку матрицы Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
