- •Лекция по линейному программированию Введение. Предмет математического программирования
- •Запись задачи математического программирования
- •Классификация методов математического программирования
- •Линейное программирование Основная задача линейного программирования (злп)
- •Экономико-математические модели задач лп эмм планирования производства (задача о наилучшем использовании ресурсов)
- •Задача о смесях (выбор диеты, составление кормового рациона, приготовление различных смесей)
- •Формы записи злп
- •Задача о смесях в канонической форме
- •Графический метод решения злп
- •Взаимосвязь однородной и канонической форм записи
- •Следующие примеры дают представление о реализации указанных преобразований. Задача планирования производства в канонической форме
- •Симплексный метод линейного программирования Преобразование канонической модели в симплексную. Основная идея симплекс-метода
- •Алгоритм симплекс-метода
- •Теория двойственности в линейном программировании Построение двойственной злп
- •Исследование пары двойственных задач
- •Определение двойственных оценок злп
- •Экономическая интерпретация двойственных оценок
- •Устойчивость двойственных оценок
- •Транспортная задача Постановка транспортной задачи
- •Основные свойства тз
- •Методы построения первоначального плана
- •Метод северо-западного угла
- •Метод минимальной стоимости
- •Метод двойного предпочтения
- •Метод потенциалов получения оптимального плана тз Теорема о потенциалах
- •Алгоритм метода потенциалов
- •Другие типы транспортных задач Открытые мадели тз
- •В пунктах отправления имеются избыточные запасы тавара
- •Открытая модель тз с дефицитом ресурсов.
- •Тз с дополнительными требованиями
- •Тз с блокированием перевозок.
- •Ограничения типа .
- •Ограничения типа .
- •Транспортная задача по критерию времени
Основные свойства тз
Транспортная задача имеет закрытую модель, если суммарный запас равен суммарной потребности, то есть
|
(5) |
иначе будет открытая модель:
|
(6) |
ТЗ всегда имеет решение для закрытой модели.
Число уравнений задачи (1)-(4) равно (m+n), а число переменных – mn.
Коэффициенты при переменных в урвнениях (1) и (2) равны 1.
Количество независимых уравнений будет (m+n-1), так как сумма m уравнений (1) всегда равна сумме n уравнений (2) (рассматривается закрытая модель). Значит, базисных переменных будет (m+n-1), а свободных переменных – (m-1)(n-1) (столько нулей, по крайней мере, будет в оптимальном плане).
Методы построения первоначального плана
Решение транспортной задачи проводится в два этапа.
На первом этапе находится первоначальный опорный план.
На втором этапе на базе опорного плана методом потенциалов определяется оптимальный план.
Обычно первоначальный план находят несколькими методами. Затем подсчитывают стоимость каждого из этих первоначальных планов, сравнивают стоимости между собой, выбирают самый выгодный (самый дешевый) и уже этот единственный план подвергают окончательной оптимизации.
Самыми простыми методами построения первоначального плана ТЗ являются:
Метод северо-западного угла (или диагональный метод).
Метод минимальной стоимости (или минимального элемента, или минимального тарифа).
Метод двойного предпочтения.
Из методов оптимизации первоначального плана самым распространенным является метод потенциалов.
Метод северо-западного угла
Рассмотрим транспортную задачу по следующим исходным данным, представленным в виде таблицы:
ПО |
В1 |
В2 |
В3 |
В4 |
В5 |
Запасы аi |
А1 |
4
|
11
|
6
|
5
|
15
|
200 |
А2 |
8
|
7
|
9
|
13
|
10
|
200 |
А3 |
10
|
5
|
12
|
7
|
20
|
100 |
Потребнос- ти bj |
70 |
80 |
150 |
110 |
90 |
|
В методе северо-западного угла, или диагональном, заполнение транспортной таблицы всегда начинается с клетки (А1 , В1), т.е. “северо-западного угла” таблицы. Далее заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка ( А3 , В5 )). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя. Отсюда:
х11 = min { a1 , b1 } = { 200 ; 70 } = 70.
Таким образом, заявка первого потребителя выполняется в полном объеме, поскольку на базе имелся больший запас товара. Поэтому остальные клетки первого столбца не нужны и остаются пустыми.
Далее наступает очередь второго заказчика, который со своей заявкой приходит на первую базу, где еще остался товар:
х12 = min { 200 - 70 ; 80 } = { 130 ; 80 } = 80.
Он также получает всё, и остальные клетки второго столбца также будут пустыми.
Теперь на первой базе осталось только 50 т груза. Поэтому третий заказчик получит только эти 50 т, хотя ему требуется 150 т.
х13 = min { 200 – 70 – 80 ; 150} = 50.
Поскольку на первой базе больше не осталось товара, остальные клетки первой строки будут пустыми.
Остальную часть своего заказа второй заказчик получит на второй базе:
х23 = min { 200 ; 150 – 50 } = 100.
Далее поцесс повторяется для остальных заказчиков, в результате чего получаем опорный план:
ПО |
В1 |
В2 |
В3 |
В4 |
В5 |
аi |
А1 |
4 70 |
11 80 |
6 50 |
5 |
15 |
200 |
А2 |
8 |
7 |
9 100 |
13 100 |
10
|
200 |
А3 |
10 |
5 |
12 |
7 10 |
20 90 |
100 |
bj |
70 |
80 |
150 |
110 |
90 |
|
В этом опорном плане семь занятых клеток. Поскольку их должно быть m +n –1, где m – число баз, n - число заказчиков, план является невырожденным. Если бы клеток было меньше, чем m +n –1, план был бы вырожденным.
Осталось подсчитать общую стоимость перевозок. Она складывается из произведений объемов перевозок и тарифов по всем занятым клеткам, т.е.:
F ( X1 ) = 70 4 + 80 11 + 50 5 + 100 9 + 100 13 + 10 7 + 90 20 = 5530.
Как видим, при распределении грузов совсем не учитывается стоимость перевозок. Поэтому, как правило, метод северо-западного угла дает опорный план, далекий от оптимального.

ПН
ПН