Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Математическая экономика / ЛАБОРАТОРНАЯ РАБОТА №5

.doc
Скачиваний:
22
Добавлен:
14.05.2015
Размер:
68.1 Кб
Скачать

ЛАБОРАТОРНАЯ РАБОТА № 5

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

    1. Цель работы. Построение оптимального плана транспортной задачи линейного программирования. Проверка теоретических положений при помощи численного эксперимента.

    2. Краткие теоретические сведения.

При определении оптимального плана транспортной задачи (как и в более общем случае основной задачи линейного программирования) естественно встает вопрос о возможности формулирования необходимого и достаточного условия оптимальности. Ответ на этот вопрос дает следующая теорема.

ТЕОРЕМА (О потенциалах). Если для некоторого опорного плана Х = (хij) транспортной задачи существуют такие числа u1, u2, ..., um, и v1, v2, ..., vn, называемые потенциалами, такие что

ui + vj = cij при хij > 0

ui + vj  cij при хij = 0

для всех , то Х = (хij) - оптимальный план транспортной задачи.

ЗАМЕЧАНИЕ. Доказательство Теоремы о потенциалах проводится прямым применением Второй теоремы о двойственности. При этом потенциалы рассматриваются как переменные задачи, двойственной к транспортной задаче.

Определение Циклом (циклом пересчета) в таблице планирования транспортной задачи называется ломаная линия, вершины которой (точки, в которых ломаная меняет направление) расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем одно звено каждой вершины находится в строке, а другое в столбце. Точки пересечения звеньев цикла не являются вершинами.

Утверждение (О возможности построения цикла). Добавляя любую свободную (незанятую) клетку к занятым клеткам таблицы планирования, соответствующим невырожденному опорному плану транспортной задачи, всегда можно построить цикл пересчета, в который в качестве вершин будут входить некоторые из этих клеток (но свободная клетка обязательно).

Утверждение (О единственности цикла пересчета). Множество клеток таблицы планирования транспортной задачи, состоящее из произвольно выбранной свободной клетки и занятых клеток, соответствующих базисным компонентам опорного плана, может содержать лишь один цикл пересчета.

ЗАМЕЧАНИЕ. Доказательство этих утверждений основывается на аналогичных по сути, хотя и выраженных в других терминах, утверждениях из общей теории линейного программирования о свойствах опорных планов (вершин многогранника решений) основной задачи линейного программирования.

Алгоритм сдвига по циклу пересчета.

Рассмотрим процедуру, называемую сдвигом по циклу пересчета. Эта процедура состоит в переходе от ранее полученного опорного плана к новому опорному плану, содержащему в качестве базисной ранее свободную переменную. Соответствующая этой переменной свободная клетка вместе с некоторыми из занятых клеток ранее полученного опорного плана составляют цикл. Далее необходимо "переместить" грузы в пределах цикла. Это перемещение производится по следующим правилам:

1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке – знак плюс, а всем остальным клеткам при движении вдоль цикла – поочередно знаки минус и плюс (эти клетки называют минусовыми и плюсовыми);

2) в свободную клетку переносят минимальное из значений перевозок хij, стоящих в минусовых клетках. Одновременно это число прибавляют к значениям перевозок, стоящим в плюсовых клетках, и вычитают из значений перевозок, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а клетка, в которой стояло минимальное среди минусовых клеток значение перевозок, считается свободной.

В результате указанных перемещений груза в пределах клеток, связанных циклом с данной свободной клеткой, определяют новый опорный план транспортной задачи. Данная процедура по своему смыслу полностью аналогична процедуре перехода в рамках симплексного метода от одного опорного плана основной задачи линейного программирования к другому с помощью жордановского исключения. Процедура сдвига по циклу пересчета играет ту же роль в методе потенциалов.

Алгоритм метода потенциалов.

1. Нахождение первого опорного плана.

2. Нахождение потенциалов, соответствующих этому опорному плану из уравнений ui + vj =cij записанных для занятых клеток таблицы планирования с учетом дополнительного соотношения u1 = 0.

3. Определение оценок ui + vj - cij для всех свободных клеток таблицы планирования. Если среди них нет положительных, то получен оптимальный план транспортной задачи; если же они имеются, то необходимо переходить к новому опорному плану.

4. Среди положительных оценок свободных клеток выбирается максимальная, и для данной свободной клетки строится цикл и производится сдвиг по циклу пересчета. Построив новый опорный план, необходимо перейти к этапу 2 и продолжить последовательное выполнение этапов до тех пор, пока проверка знаков оценок на этапе 3 не позволит сделать вывод о нахождении оптимального плана транспортной задачи.

ЗАМЕЧАНИЕ. Необходимость дополнения уравнений ui+vj=cij дополнительным соотношением ui = 0, вызвана тем, что эта система состоит из m+n-1 линейно независимых уравнений, но содержит m+n неизвестных ui , vj . Тем самым, для однозначного решения данной системы линейных алгебраических уравнений недостает одного уравнения. Неоднозначность определения потенциалов не сказывается на значения оценок, но для численного решения задачи удобно доопределить эту систему так, чтобы иметь дело с конкретными значениями.

Алгоритм распределительного метода.

1. Нахождение первого опорного плана.

2. Нахождение алгебраических сумм тарифов для всех свободных клеток таблицы планирования.

3. Если все полученные алгебраические суммы неотрицательны, то оптимальный план получен и конец работы алгоритма.

4. Сдвиг по циклу пересчета для клетки с наибольшей по абсолютной величине отрицательной алгебраической суммой. Переход к п.2.

    1. Варианты заданий.

При решении задачи

а) методом потенциалов

в) распределительным методом

использовать числовые данные лабораторной работы № 4 (в соответствии с № варианта)

    1. Cодержание отчета

  1. Описание используемого метода.

  2. Промежуточные результаты выполнения алгоритма

  3. Таблица результатов.

    1. Вопросы для самопроверки

  1. В чем заключается основная идея метода потенциалов?

  2. Что такое потенциалы?

  3. Что такое цикл пересчета и в чем состоит сдвиг по циклу пересчета?

  4. Что является условием оптимальности в методе потенциалов?

  5. Что такое алгебраическая сумма тарифов?

  6. В чем отличие распределительного метода от метода потенциалов?

  7. Что является признаком неединственности оптимального плана в методе потенциалов и в распределительном методе?

  8. Закрытая задача.

3