- •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.1 - 5.4). Хотя в системе (5.2 - 5.3) m+n уравнений, опорный план содержит только m+n–1 базисных переменных. Это объясняется тем, что одно из уравнений является следствием остальных, и в жордановой форме m+n–1 уравнений.
Опишем метод отыскания исходного опорного плана, называемый методом минимального элемента.
Возьмем клетку (Аi,Вj) с наименьшей стоимостью перевозок. Проставим в нее перевозку, равную min(ai,bj). Затем "уменьшаем" транспортную таблицу, руководствуясь правилами:
если ai < bj, то исключаем из дальнейшего рассмотрения пункт отправления (ПО) Аi (и соответствующую строку); а в "меньшей" таблице потребность пункта назначения (ПН) Вj полагаем равной bj - ai ;
если bj <ai, то исключаем ПН Вj (и соответствующий столбец); в "меньшей" таблице полагаем запас ПО Аi равным ai - bj;
если ai = bj, то:
а) если в таблице только один ПО Аi и один ПН Вj, то алгоритм останавливается;
б) если в таблице один ПО Аi и несколько ПН, то исключаем Вj , считая в "меньшей" таблице запас пункта Аi равным 0;
в) если в таблице один ПН Вj и несколько ПО, то исключаем Аi, считая в "меньшей" таблице потребность пункта Вj, равной 0;
г) если в таблице несколько ПО и несколько ПН, то исключаем либо ПО Аi, полагая в "меньшей" таблице потребность ПН Вj равной 0, либо исключаем ПН Вj, полагая запас ПО Аi равным 0.
Подобные шаги проделывают до тех пор, пока не будут исключены все строки и столбцы.
В результате применения метода минимального элемента некоторые клетки заполнены, некоторые – нет. Заполненные клетки называются базисными (даже если стоит 0), незаполненные – свободными. Докажем, что число базисных клеток равно m+n-1.
Действительно, на каждом шаге, кроме последнего, исключаем либо строку, либо столбец. На последнем шаге исключаем и строку, и столбец. Так как число строк и столбцов в сумме равно m+n, то всего будет проделано m+n-1 шагов, а на каждом шаге заполняется одна клетка, т.е. число базисных клеток m+n-1.
Воспользуемся примером (табл. 5. 2).
Таблица 5.2
Пн По |
В1 |
В2 |
В3 |
В4 |
Запасы |
А1 |
10 4 |
15 3 |
5 |
7 |
25 |
А2 |
2 |
5 1 |
8 |
6 |
5 |
А3 |
0 4 |
9 |
30 3 |
15 2 |
45 |
Потребности |
10 |
20 |
30 |
15 |
75=75 |
Рассмотрим произвольную клетку (Аi, Вj) - клетку транспортной таблицы с наименьшей стоимостью перевозок - клетку (2.2). Проставим в неё перевозку x22=min(a2,b2)=min(20,5)=5. После этого запас пункта А2 полностью исчерпан. Исключим мысленно из таблицы вторую строку. В меньшей транспортной таблице потребность пункта В2 положим равной 25–10=15. Рассматриваем клетку с минимальной стоимостью новой таблицы. Руководствуясь тем же правилом, проставляем в неё перевозку х34=15. Потребность пункта В4 полностью удовлетворена, и мы исключаем из таблицы четвертый столбец, а в полученной транспортной таблице запас пункта А3 делаем равным 45–15 = 30. В клетку (3,3) с минимальной стоимостью, равной 3, проставляем перевозку х33=min(30,30)=30. При этом одновременно исчерпывается запас пункта А3 и удовлетворяется потребность пункта В3.
Переходя к новой таблице, нельзя одновременно убрать и столбец, и строку. Нужно убрать либо столбец, либо строку. Уберем, например, столбец. Третья строка еще не исключена из таблицы, запас пункта А3 полагаем равным 0, поэтому в клетку (3,1) с минимальной стоимостью, равной 4, ставим перевозку х31=min(10,0)=0. После этого исключаем третью строку из рассмотрения. Далее полагаем х12=min(15,25)=15, исключаем второй столбец, а запас пункта А1 делаем равным 25-15=10. Наконец, в клетку (1,1) проставляем х11=10. Исходный опорный план найден. Базисными переменными являются х11, х12, х22, х31, х33, х34. Значения базисных переменных в опорном плане равны перевозкам, проставленным в соответствующих клетках. Опорный план является вырожденным, так как х31=0. Число базисных переменных равно m+n–1, т.е. 3+4–1=6.
Метод минимального элемента усваивается очень легко. Чтобы убедиться в этом, проделайте самостоятельно такой пример (табл. 5.3.):
Таблице 5.3
Пн По |
В1 |
В2 |
В3 |
Запасы |
А1 |
2 |
3 |
1 |
40 |
А2 |
4 |
2 |
5 |
60 |
А3 |
3 |
2 |
6 |
50 |
Потребности |
70 |
40 |
40 |
150=150 |
У вас должен получиться результат, зафиксированный в таблице 5.4.
Таблица 5.4
Пн По |
В1 |
В2 |
В3 |
Запасы |
А1 |
2
|
3
|
40 1
|
40 |
А2 |
20 4
|
40 2
|
0 5
|
60 |
А3 |
3 50 |
2
|
6
|
50 |
Потребности |
70 |
40 |
40 |
150=150 |