Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 22
Текст из файла (страница 22)
Этот упрошенный метод мы и опишем ниже. Предварительно докажем некоторые утверждения, имеющие место лля транспортных задач. Лемма 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 достаточно доказать, что соответствующие базисным элементам столбцы матрицы А линейно независимы. Отметим, что описанные методы нахождения первоначального плана перевозок содержат общий элемент действия: на каждом этапе мы выводим из рассмотрения либо столбец, либо строку матрицы Х. Доказательство можно провести индукцией по числу гл+ и = й.
Пусть ль+ л = 2 — минимально возможное число. Матрица А состоит из единственного элемента н утверждение очевидно. Предположим, что для пз + л = й получаемые этим методом столбцы линейно независимы. Докажем соответствующее утверждение для го+о = й+1. Не ограничивая общности, считаем, что на первом этапе выводится из рассмотрения первая строка или первый столбец (в противном случае мы можем строки или столбцы переобозначить и поменять местами). Если мы выводим из рассмотрения первую строку матрицы, то зто означает, что первый пункт отправления А, обслужен полностью, зп — базисный элемент, а все элементы хц = О, 7' = 2,...,л.
Первое ограничение уравнений (а) выполнено, в матрице ограничений А можно убрать первую строку и первые и столбцов. Получилась меньшая матрица размера (т — 1+ л) х (т — 1)л, а для нее по предположению индукции соответствующие столбцы являются линейно независимыми. Добавление столбца с единицей на первом месте (и еще на одном из последних л мест) к ль -1- л — 2 столбцам, расширенным и начинающимся с нуля образует систему ш+ л — 1 линейно независимых столбцов. Если мы выводим из рассмотрения первый столбец матрицы, то зто означает, что первый пункт назначения обслужен полностью, пн— базисный элемент, а все элементы ап = О, 1 = 2,...,гл. Первое ограничение уравнений (Ь) выполнено, в матрице ограничений А можно убрать гл+ 1-ю строку и соответствующие гп столбцов.
Получилась подобная меньшая матрица размера (ш + и — 1) х (и — 1)гл, а для нее по предположению индукции соответствующие столбцы являются линейно независимыми. Добавление столбца с единицей на гл+ 1-м месте (и еще на одном из первых лз мест) к го+ л — 2 линейно независимым столбцам, расширенным и имеющим на гп+ 1-м месте нули образует систему из ш+ и — 1 линейно независимых столбцов. Индукция закончена. 128 Глава 2. Линейное программирование 5.4. Метод потенциалов Сформулируем правило решения транспортной задачи методом потенциалов (обоснование этого метода булет дано в п. 5.7).
! . Привести задачу к замкнутой модели (см. п. 5.1). 2. Найти первоначальный план перевозок х, являюизийгя крайней точкой мноягества допустимых элементов. 3. Исследование плана перевозок х. Для найденного плана х построить матрицу С = (су) щ!,, с;,". = и! + е,, определяя гп+ и потенциалов и;,е из системы го+ и — 1 уравнений: я, + о. = с; для базисных индексов з,31 Эти уравнения линейно независимы (зто следует из линейной независимости столбцов, соответствующих базисным элементам), поэтому для однозначного определения потенциалов и„о положим заранее один из потенциалов заданной величине, например, положим и! — — О. Замечание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
