- •1. Содержание математического программирования. Постановка общей и основной задач линейного программирования.
- •1. Линейное программирование
- •1.1. Примеры задач линейного программирования
- •1.2. 0Бщая и основная задачи линейного программирования
- •2. Свойства задач линейного программирования. Графический метод решения задач линейного программирования.
- •1.3. Свойства задач линейного программирования
- •1.4.1. Графический метод решения задач линейного программирования
- •3. Алгоритм симплекс-метода решения общей задачи линейного программирования.
- •1.4.2. Симплекс-метод
- •Алгоритм симплекс-метода
- •4. Метод искусственного базиса
- •1.4.3. Методы искусственного базиса
- •5. Двойственная задача линейного программирования. Экономическая интерпретация двойственной задачи линейного программирования.
- •1.5. Двойственная задача линейного программирования
- •1.5.1. Экономическая интерпретация двойственной задачи
- •6. Постановка транспортной задачи. Методы нахождения первого допустимого решения транспортной задачи.
- •1.6. Транспортная задача
- •1.6.1. Пocтaнoвкa тpaнcпopтнoй зaдaчи
- •1.6.2. Методы нахождения начального допустимого плана перевозок груза
- •1. Правило "северо-западного yглa"
- •2. Метод наименьшей стоимости
- •7. Метод потенциалов.
- •1.6.3. Метод потенциалов
- •Алгоритм решения транспортной задачи методом потенциалов
Алгоритм решения транспортной задачи методом потенциалов
Алгоритм состоит из предварительного шага и повторяющегося общего шага.
На предварительном шаге выполняется следующее:
1) составляется первоначальный план одним из рассмотренных выше методов;
2) для полученного плана определяется система потенциалов, т.е. находятся m+n чисел u1,...,um ; v1,...,vn из системы m+n-1 линейных уравнений: vj - ui = сij, где номера i,j соответствуют загруженным клеткам таблицы. Поскольку число неизвестных превышает на единицу число уравнений, то одну из неизвестных полaгaeм равной произвольному числу, например u1 = 0. Остальные неизвестные находятся из указанной выше системы линейных уравнений;
3) проверяется оптимальность плана по критерию оптимальности задачи. Такая проверка осуществляется, например, следующим образом. Для всех свободных клеток таблицы находим числа: Wij =vi - ui - сij . Если все числа wij <= 0 , то критерий оптимальности выполняется. В противном случае - нет.
Общий шаг (применяется, если план, построенный на предыдущем шаге, не оптимален) состоит из трех этапов:
1) улучшение плана. Поскольку текущий план не является оптимальным, то существует свободная клетка таблицы, для которой справедливо неравенство wij>0. Свободную клетку таблицы, у которой положительное число wij>О является наибольшим, помечаем символом * (звездочка). Далее строим многоугольник, вершины которого лежат в загруженных клетках таблицы и в свободной клетке, помеченной звездочкой. Помечаем клетки-вершины полученного многоугольника попеременно знаками "+" и "-". Свободная клетка помечается знаком "+". Переход к новому плану перевозок груза осуществляется следующим образом. Наименьшая поставка, стоящая в клетках-вершинах многоугольника и помеченная знаком "-", прибавляется к перевозкам всех клеток-вершин, помеченных знаком "+", и вычитается из поставок всех клеток-вершин, помеченных знаком "-"‚. В результате; ранее свободная клетка становится заполненной (загруженной), а клетка, помеченная знаком "-", в которой стояла наименьшая поставка, превращается в свободную клетку. Общее число занятых клеток остается равным n+m-1. Если в пределах данного многоугольника минимальную поставку имели две клетки или более, то освобождаться может лишь одна из них, а остальные считаются загруженными с нулевыми поставками;
2) для полученного плана определяется система потенциалов;
3) проверяется оптимальность плана по критерию оптимальности задачи.