- •Тема I. Линейное программирование …………………………….5
- •Тема II. Дискретное линейное программирование …………….27
- •Тема III. Теория транспортных задач линейного
- •Тема IV. Нелинейное программирование……………………….61
- •Введение
- •Тема I. Линейное программирование лабораторная работа № 1
- •Алгоритм нахождения базисных решений методом Жордана
- •1.4. Содержание отчета.
- •Лабораторная работа № 2
- •Нахождение оптимального плана или установление неразрешимости задачи симплексным методом.
- •2.4. Содержание отчета.
- •2.5. Вопросы для самопроверки.
- •Лабораторная работа № 3 Тема: Решение основной задачи линейного программирования двойственным симплексным методом.
- •3.2. Краткие теоретические сведения.
- •Алгоритм двойственного симплексного метода.
- •3.4. Содержание отчета.
- •3.5. Вопросы для самопроверки.
- •Тема II. Дискретное линейное программирование
- •Условия прекращения роста ветвей.
- •4.3. Варианты заданий.
- •4.5. Вопросы для самопроверки
- •5.1. Цель и задачи работы.
- •5.2. Краткие теоретические сведения.
- •Алгоритм нахождения оптимального плана основной целочисленной (частично целочисленной) задачи линейного программирования методом Гомори.
- •5.3. Варианты заданий.
- •5.4. Cодержание отчета.
- •4.5. Вопросы для самопроверки
- •Тема III. Транспортная задача линейного программирования
- •Планов транспортной задачи
- •6.1. Цель и задачи работы.
- •6.2. Краткие теоретические сведения.
- •6.3. Варианты заданий:
- •6.4. Содержание отчета
- •Алгоритм сдвига по циклу пересчета.
- •Алгоритм метода потенциалов.
- •Алгоритм распределительного метода.
- •Лабораторная работа № 8
- •8.1. Цель работы и задачи работы.
- •8.2. Краткие теоретические сведения.
- •8.3. Варианты заданий.
- •Алгоритм решения задачи дробно-линейного программирования
- •9.4. Содержание отчета.
- •10.4. Содержание отчета.
- •10.5. Вопросы для самопроверки
Алгоритм сдвига по циклу пересчета.
Рассмотрим процедуру, называемую сдвигом по циклу пересчета. Эта процедура состоит в переходе от ранее полученного опорного плана к новому опорному плану, содержащему в качестве базисной ранее свободную переменную. Соответствующая этой переменной свободная клетка вместе с некоторыми из занятых клеток ранее полученного опорного плана составляют цикл. Далее необходимо "переместить" грузы в пределах цикла. Это перемещение производится по следующим правилам:
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 (i=1,2,…m; j=1,2,…n). Тем самым, для однозначного решения данной системы линейных алгебраических уравнений недостает одного уравнения. Неоднозначность определения потенциалов не сказывается на значениях оценок, но для численного решения задачи удобно доопределить эту систему так, чтобы иметь дело с конкретными значениями.
Определение 7.2. Алгебраической суммой тарифов цикла пересчета таблицы планирования транспортной задачи называется сумма, в которые тарифы плюсовых клеток цикла входят со знаком «плюс», а минусовых – со знаком «минус».