6.1.Транспортная задача линейного программирования
Постановка задачи
Некоторый однородный продукт, сосредоточенный у m поставщиков Аi в количестве аi(i = 1, ..., m) единиц соответственно, необходимо доставить n потребителям Вj в количестве bj(j = 1,..., n) единиц. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.
Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.
Обозначим через хij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке хij единиц груза, то стоимость перевозки составит сijxij.
Стоимость всего плана выразится двойной суммой:
.
Систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть перевезены, т.е.
б) все потребности должны быть удовлетворены, т.е.
.
Таким образом, математическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции
; (6.1)
при ограничениях
; (6.2)
(6.3)
xij ³ 0, i = 1,…,m; j = 1,…, n. (6.4)
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.
. (6.5)
Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (6.5), называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая:
а) суммарные запасы превышают суммарные потребности
;
б) суммарные потребности превышают суммарные запасы
.
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции:
.
При ограничениях
(случай «а»)
(случай «б»)
Открытая модель решается приведением к закрытой модели.
В случае «а», когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вn + 1, потребность которого:
.
В случае «б», когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аm + 1, запасы которого:
.
Как стоимость перевозки единицы груза до фиктивного потребителя, так и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, поскольку груз в обоих случаях не перевозится.
Транспортная задача имеет n + m уравнений с mn неизвестными.
Матрицу Х = (хij)m,n, удовлетворяющую условиям (6.2) - (6.4), называют планом перевозок транспортной задачи (хij-перевозками).
План Х*, при котором целевая функция (6.1) обращается в минимум, называется оптимальным.
Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса:
.
План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов (i = 1. . m, j = 1. . n), где – векторы при переменных хij (i = 1. . m, j = 1. . n) в матрице системы ограничений (6.2) - (6.4).
Теорема 2. Существует план, содержащий не более m + n – 1 положительных перевозок, при этом система векторов , соответствующая таким перевозкам (хij > 0), линейно независима.
Таким образом, опорный план транспортной задачи содержит m + n – 1 положительных перевозок. Если менее (m+n-1) компонент оперного плана положительны, то он называется вырожденным. Дадим другое определение опорного плана.
План транспортной задачи называется опорным, если из его основных коммуникаций невозможно составить замкнутый маршрут.
- Учебное пособие
- Оглавление
- 2. Элементы линейной алгебры 21
- 3. Линейное программирование 48
- 4. Теория двойственности в линейном программировании 98
- 5. Целочисленные модели исследования операций 137
- 6. Экономические задачи, сводящиеся к транспортной модели 160
- Введение в исследование операций
- 1.1 Основные определения
- Этапы исследования операций
- Домашнее задание №1
- 2. Элементы линейной алгебры
- 2.1. Алгебра матриц
- 2.1.1. Виды матриц
- 2.1.2. Действия над матрицами
- Домашнее задание №2
- 2.2. Вычисление определителей
- Домашнее задание №3
- 2.3. Решение систем алгебраических уравнений
- 2.3.1. Основные понятия и определения
- 2.3.2. Формулы крамера и метод обратной матрицы
- 2.3.3. Метод жордана-гаусса
- Домашнее задание №5
- 2.4. Векторное пространство
- 2.4.2. Размерность и базис векторного пространства
- Домашнее задание №6
- 2.5. Решение задач линейной алгебры с помощью ms excel
- 3. Линейное программирование
- 3.1. Постановки задачи линейного программирования
- 3.1.1. Общая постановка задачи линейного программирования
- 3.1.2. Основная задача линейного программирования
- 3.1.3. Каноническая задача линейного программирования
- 3.2. Графический метод решения злп
- Домашнее задание №7
- Домашнее задание №8
- 3.3. Анализ решения (модели) на чувствительность
- Домашнее задание №9
- 3.4. Решение линейных моделей симплекс-методом.
- Переход от одной к-матрицы злп к другой к-матрице
- Алгоритм симплекс-метода
- Домашнее задание №10
- 3.4. Двойственный симплекс-метод (р-метод)
- Определение р-матрицы злп
- Условия перехода от одной р-матрицы злп к другой
- Алгоритм р-метода
- Решение задач р-методом
- Домашнее задание №11
- Домашнее задание №12
- 3.5. Решение злп двухэтапным симплекс-методом
- Первый этап - решение вспомогательной задачи
- Второй этап - решение исходной задачи
- Домашнее задание №13
- 4. Теория двойственности в линейном программировании
- 4.1. Определение и экономический смысл двойственной злп
- 4.2. Основные положения теории двойственности
- Получение оптимального плана двойственной задачи на основании теоремы 4
- На первой итерации получен оптимальный план злп (4.24).
- 4.3. Решение злп с помощью Ms Excel
- 4.4. Анализ решения злп на основе отчетов ms excel
- 5. Целочисленные модели исследования операций
- 5.1. Метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)
- X1, х2 0, целые.
- Подробное описание метода
- 5.2. Задача коммивояжера
- Применение метода ветвей и границ для решения задачи коммивояжера
- Ветвление
- Построение редуцированных матриц и и вычисление оценок снизу
- Формирование списка кандидатов на ветвление
- 6. Экономические задачи, сводящиеся к транспортной модели
- 6.1.Транспортная задача линейного программирования
- Методы составления первоначальных опорных планов
- Метод потенциалов решения транспортной задачи
- Проверка выполнения условия оптимальности для незанятых клеток
- Выбор клетки, в которую необходимо поместить перевозку
- Построение цикла и определение величины перераспределения груза
- Проверка нового плана на оптимальность
- Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке
- 6.2.Экономические задачи, сводящиеся к транспортной модели
- Оптимальное распределение оборудования
- Формирование оптимального штата фирмы
- Задача календарного планирования производства
- Модель без дефицита
- Модель с дефицитом
- 6.3.Задача о назначениях
- Венгерский алгоритм
- Оптимальное исследование рынка
- Оптимальное использование торговых агентов