- •Содержание
- •Модели линейного программирования
- •Примеры задач линейного программирования
- •Фирма выпускает четыре вида персональных компьютеров
- •Выражения (1), (2) и (3) составляют экономико-математическую модель задачи линейного программирования.
- •Условия неотрицательности получаемого решения
- •Условие неотрицательности решения
- •Условие неотрицательности решения
- •Общая задача линейного программирования
- •Стандартная (симметричная) задача линейного программирования
- •Каноническая (основная) задача линейного программирования
- •Представление задачи линейного программирования в канонической форме
- •Геометрическая интерпретация задачи линейного программирования
- •Решение задач линейного программирования симплекс-методом
- •Транспортная задача
- •Нахождение первоначального плана
- •Циклы пересчета
- •Открытая транспортная задача
- •Определение оптимального плана транспортных задач,имеющих дополнительные условия
- •Распределительный метод решения транспортной задачи
- •Метод потенциалов
- •Модель межотраслевого баланса
- •Характеристика основных разделов и схема межотраслевого баланса
- •Основные балансовые соотношения
- •Экономико-математическая модель межотраслевого баланса. Модель Леонтьева
- •Методы отыскания вектора валовых выпусков и вектора конечной продукции
- •Смешанная задача межотраслевого баланса
- •Элементы и теория игр Основные понятия теории игр
- •Матричные игры
- •Игра с седловой точкой
- •Игра в смешанных стратегиях
- •Решение игры в смешанных стратегиях
- •Игра два на два (2 х 2)
- •Литература
Открытая транспортная задача
Если не соблюдается баланс предложения и спроса, то есть
,
то такая задача называется открытой. Для решения такой задачи, если общее предложение превышает общий спрос, то есть
> ,
необходимо ввести в модель фиктивный пункт потребления (Вn+1) в n + 1-м столбце матрицы транспортной задачи. При этом стоимости перевозки для фиктивного пункта потребления равны нулю: Ci,n+1 = 0; i = .
Потребность в грузе фиктивного пункта назначения равна разности предложения и спроса:
Пункты отправления |
Пункты назначения |
Запасы (предложение) |
|||||
В1 |
… |
Вj |
… |
Вn |
(Вn+1) |
||
А1 |
С11 |
|
C1j |
|
C1n |
0 |
а1 |
… |
|
… |
|
… |
|
|
|
Аi |
Сi1 |
|
Сij |
|
Сin |
0 |
аi |
… |
|
… |
|
… |
|
|
|
Аm |
Сm1 |
|
Сmj |
|
Сmn |
0 |
аm |
Потребности (спрос) |
b1 |
… |
bj |
… |
bm |
(bn+1 = аi - bj) |
Если величина суммарного спроса превышает суммарное предложение, то есть
< ,
необходимо ввести в модель фиктивный пункт отправления грузов (Аm+1) в m+1-ю строку матрицы транспортной задачи. При этом стоимости перевозки от фиктивного пункта отправления равны нулю: Cm+1,j = 0; j = .
Предложение фиктивного пункта отправления равно разности суммы потребностей и запасов грузов:
Пункты отправления |
Пункты назначения |
Запасы (предложение) |
||||
В1 |
… |
Вj |
… |
Вn |
||
А1 |
С11 |
|
C1j |
|
C1n |
а1 |
… |
|
… |
|
… |
|
|
Аi |
Сi1 |
|
Сij |
|
Сin |
аi |
… |
|
… |
|
… |
|
|
Аm |
Сm1 |
|
Сmj |
|
Сmn |
аm |
(Аm+1) |
0 |
|
0 |
|
0 |
(Аm+1 = bj - аi) |
Потребности (спрос) |
b1 |
… |
bj |
… |
bm |
__ |
Определение оптимального плана транспортных задач,имеющих дополнительные условия
1. Если по каким-либо причинам перевозки грузов из некоторого пункта отправления Аi в некоторый пункт назначения Вj не могут быть осуществлены, тогда для определения оптимального плана полагают, что стоимость этой перевозки является сколь угодно большой величиной, например, равной миллиарду денежных единиц. Для краткости эту величину обозначим буквой М. Такой прием, называемый блокированием, дает возможность исключить эту перевозку из плана как невыгодную.
2. Если из пункта отправления Аi в пункт назначения Вj требуется перевезти определенное количество грузов dij, тогда в соответствующей клетке устанавливается блокировка М как стоимость перевозки, для исключения дальнейших перевозок по данному маршруту. Соответствующий запас корректируется на величину фиксированной перевозки аi - dij, аналогично и соответствующая потребность корректируется на ту же величину bj - dij. После решения скорректированной задачи в оставшуюся свободной клетку i, j проставляется значение обязательной перевозки dij, а стоимость перевозки единицы этого груза берется из исходных данных равной Cij.
3. Если необходимо решить транспортную задачу на максимум функции цели, тогда поступают следующим образом:
исходная матрица стоимости перевозок C = ;
максимальное значение стоимости перевозки С13 = 7;
вычтем из максимальной стоимости все элементы матрицы
перевозок C = = ;
задачу решают на минимум, используя матрицу С, а при нахождении функции цели в последней итерации используют матрицу С.
4. Если задача открытая и из пункта Аi весь груз должен быть выведен, то вместо нулевой стоимости перевозки из пункта Аi фиктивному потребителю используют блокировку (М). Тогда груз будет перевозиться только реальным потребителям.
Если же потребности пункта Вj надо полностью удовлетворить, тогда вместо нулевой стоимости перевозки от фиктивного поставщика к пункту Вj используют блокировку (М). Этим исключают из плана фиктивные перевозки к пункту Вj.