- •6.030509, 6.030504, 6.030601Дневной и заочной форм обучения
- •1.Решение систем линейных уравнений методом гаусса – жордана
- •1.1. Основные понятия
- •1.2. Приведение системы линейных уравнений к жордановой форме
- •1.3. Понятие общего, частного и базисного решений.
- •2. Общие свойства задачи линейного программирования
- •2.І. Пример задачи линейного программирования - задача об использовании оборудования.
- •2.2. Задача об использовании сырья.
- •2.3. Задача составления рациона (задача о диете).
- •2.4. Общая постановка задачи линейного программирования
- •2.5. Геометрический метод решения злп.
- •Пример 1
- •2.6. Канонический вид злп.
- •2.7. Понятие опорного плана злп.
- •3. Симплексный метод решения злп
- •3.1. Общая характеристика и основные этапы симплекс – метода
- •3.2. Табличный вид злп. Симплекс - таблицы.
- •3.3. Условие оптимальности опорного плана.
- •3.4. Условие неразрешимости злп из-за неограниченности снизу на одр целевой функции.
- •3.5. Переход к новому опорному плану.
- •3.6. Табличный симплекс-алгоритм.
- •После выбора генерального элемента переходим к таблице 3.11
- •Снова выбираем генеральный элемент и переходим к таблице 3.14
- •3.7. Отыскание исходного опорного плана злп методом искусственного базиса
- •3.8. Вырожденность опорного плана. Зацикливание.
- •Двойственность в линейном программировании
- •Экономическая интерпретация двойственных задач
- •Понятие двойственной задачи
- •Теоремы двойственности
- •Транспортная задача.
- •Задача о перевозках.
- •Общая постановка транспортной задачи.
- •Отыскание исходного опорного плана перевозок.
- •5.4. Циклы пересчета
- •5.4.1. Понятие цикла пересчета
- •5.4.2. Максимально допустимый сдвиг по циклу пересчета.
- •5.4.3. Цена цикла пересчета
- •5.5. Потенциалы.
- •5.6. Алгоритм решения транспортной задачи методом потенциалов.
- •5.7. Открытые транспортные задачи.
- •6. Целочисленное линейное программирование
- •6.1. Общая постановка задачи целочисленного линейного программирования (зцлп).
- •6.2. Целочисленная задача об использовании сырья.
- •6.3. Задача о рюкзаке.
- •6.4. Решение зцлп методом округления.
- •6.5. Метод ветвей и границ.
- •Оптимальный план оптимальный план
- •7. Общая постановка и разновидности задач математического программирования
- •Литература
- •Содержание
5.4.3. Цена цикла пересчета
Ценой цикла пересчета называется разность между суммой стоимостей, стоящих в положительных клетках, и суммой стоимостей, стоящих в отрицательных клетках.
Например, цена цикла пересчета, указанного в таблице 5.5, равна (– 4).
Цена цикла пересчета - это приращение целевой функции при сдвиге h=1 по циклу пересчета.
Если, например, сделать единичный сдвиг по циклу пересчета таблицы 5.5, получится план перевозок, суммарная стоимость которого 430–4 = 426.
Имеет место, следующее утверждение: при сдвиге на величину h ≥ 0 по циклу пересчета, имеющему цену γ, приращение Δf целевой функции вычисляется по формуле
Δf = γ · h (5.5)
В справедливости формулы (5.5) можно убедиться и на примерах (таблицы 5.4, 5.5, 5.6). Из формулы (5.5) вытекает, что при положительном сдвиге по циклу пересчета с отрицательной ценой значение целевой функции уменьшается. Поэтому поиск оптимального плана перевозок сводится к выявлению циклов пересчета с отрицательной ценой и осуществлению максимально допустимых сдвигов по ним. А если циклов пересчета с отрицательной ценой не окажется?
Теорема: Опорный план перевозок, при котором все циклы пересчета имеют неотрицательные цены, оптимален.
Выявить цикл пересчета с отрицательной ценой при имеющемся опорном плане (или обнаружить, что такого цикла нет) можно было бы так: для каждой свободной клетки построим цикл пересчета и вычислим его цену. Однако в методе потенциалов для этой цели разработана менее трудоемкая процедура.
5.5. Потенциалы.
Пусть в транспортной задаче с пунктами отправления А1, А2,..., Аm и пунктами назначения В1, В2,..., Вn имеется некоторый опорный план перевозок. Сопоставим каждому пункту отправления Ai число αi (), каждому пункту назначения Вj - число βj () так, чтобы для каждой базисной клетки (p,q) выполнялось равенство
αp + βq = cpq (5.6)
Числа αi и βj называются потенциалами пунктов отправления и назначения соответственно.
Для отыскания потенциалов нужно для каждой базисной клетки составить уравнение вида (5.6) и решить полученную систему m + n – 1 уравнений с m + n неизвестными. Такая система имеет бесконечно много решений. Чтобы получить конкретное решение, один из потенциалов полагают равным 0.
Найдем, например, систему потенциалов для опорного плана, данного в таблице 5.6. Составим систему уравнений:
Положим α1=0. Тогда β1=2; β3=1; α2=2; α3=1; β2=1. Дополним таблицу 5.6 столбцом с потенциалами αi и строкой с потенциалами βj, получим таблицу 5.7.
Таблица 5.7
Пн По |
В1 |
В2 |
В3 |
Запасы |
αi |
А1 |
2 2 0 |
1 3
|
1 1 40 |
40 |
0 |
А2 |
4 4 60 |
3 2
|
3 5
|
60 |
2 |
А3 |
3 3 10 |
2 2 40 |
2 6
|
50 |
1 |
Потребности |
70 |
40 |
40 |
150=150 |
|
βj |
2 |
1 |
1 |
|
|
Назовем псевдостоимостью перевозки единицы груза из пункта Аi в пункт Вj величину
Рассчитанные для таблицы 5.7 псевдостоимости помещены в левых верхних углах этой таблицы.
Потенциалы и псевдостоимости имеют любопытную экономическую интерпретацию. Предположим, что имеется перевозчик, который взимает с пункта Аi плату αi за вывоз единицы груза, а с пункта Вj - плату βj за ввоз единицы груза. Тогда псевдостоимость – это та выручка, которую получает перевозчик за перевозку единицы груза из пункта Аi в пункт Вj. Полезно применить эту интерпретацию для лучшего понимания того условия оптимальности опорного плана, которое будет приведено ниже.
А пока докажем следуйте утверждение:
цена γij цикла перерасчета, проходящего через свободную клетку (ij), выражается формулой:
Для доказательства рассмотрим рисунок 5.1.
Рис. 5.1.
Клетка (ij) - единственная свободная клетка изображенного цикла пересчета. Цена γij цикла пересчета, согласно определению, равна
Так как для базисных клеток выполняются равенства (5.6), то можно записать:
, что и требовалось доказать.
Из формулы (5.7) вытекает, что если для свободной клетки псевдостоимость больше стоимости, то через эту свободную клетку проходит цикл пересчета с отрицательной ценой. В частности, условие оптимальности опорного плана перевозок можно сформулировать так:
если, опорный план перевозок таков, что для всех свободных клеток псевдостоимость не превосходит стоимости, то этот план оптимален.
Например, опорный план перевозок таблицы 5.7 не является оптимальным, так, как для клетки (2.2) псевдостоимость больше стоимости. Цена, цикла пересчета, проходящего через эту клетку отрицательна и равна 2–3=–1 (в этом можно лишний раз убедиться, подсчитав цену, исходя из определения). Сделав максимально допустимый сдвиг величины h=40, получим таблицу 5.8.
Таблица 5.8
Пн По |
В1 |
В2 |
В3 |
Запасы |
αi |
А1 |
2 2 0 |
0 3
|
1 1 40 |
40 |
0 |
А2 |
4 4 20 |
2 2 40 |
3 5
|
60 |
2 |
А3 |
3 3 50 |
1 2
|
2 6
|
50 |
1 |
Потребности |
70 |
40 |
40 |
150=150 |
|
βj |
2 |
0 |
1 |
|
|
Построим систему потенциалов для таблицы 5.8. При небольшом навыке это можно сделать, не выписывая систему уравнений. Рассчитав затем псевдостоимости, видим, что для всех свободных клеток псевдостоимости не превосходят стоимостей. Следовательно, опорный план таблицы 5.8 оптимален.
fmin=40•1+20•4+40•2+50•3=350