- •Глава 1. Линейное программирование 3
- •Глава 2. Транспортная задача линейного программирования (тз) 68
- •Глава 3. Динамическое программирование 98
- •Глава 1. Линейное программирование
- •1.1. Математическая модель задачи линейного программирования
- •1.2. Формы записи задач линейного программирования
- •Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой
- •1.3. Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными
- •Алгоритм графического метода решения злп с двумя переменными
- •1.4. Графический метод решения задач линейного программирования сnпеременными
- •1.5. Симплексный метод решения задач линейного программирования
- •Алгоритм решения злп симплексным методом
- •Нахождение начального опорного плана злп ( )
- •Нахождение начального опорного плана злп методом искусственного базиса
- •Нахождение начального опорного плана злп методом Жордановых исключений
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при решении злп на
- •Переход к новому опорному плану
- •1.6. Двойственные задачи линейного программирования
- •Правила построения двойственной задачи.
- •Глава 2. Транспортная задача линейного программирования (тз)
- •2.1. Математическая модель транспортной задачи
- •Закрытая и открытая модели транспортной задачи
- •2.2. Решение транспортной задачи
- •Алгоритм решения транспортной задачи
- •Нахождение начального опорного плана методом «минимального элемента»
- •Нахождение начального опорного плана методом «северо-западного угла»
- •Нахождение начального опорного плана методом Фогеля
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов
- •Переход к новому опорному плану
- •Цикл пересчета
- •Глава 3. Динамическое программирование
- •3.1. Задача оптимального распределения ресурсов
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •3.2. Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •Список использованной литературы
Закрытая и открытая модели транспортной задачи
Модель ТЗ называют закрытой (сбалансированной), если суммарный объем груза всех поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство:
. (2.3)
Если для транспортной задачи выполняется одно из условий:
, (2.4)
, (2.5)
то модель задачи называют открытой (несбалансированной).
Для составления математической модели и для решения ТЗ с открытой моделью необходимо преобразовать ее в закрытую модель.
Так, при выполнении условия (2.4) необходимо ввести фиктивного (n+1)-ого потребителя , то есть в матрице задачи добавляется столбец. Спрос фиктивного потребителя полагают равным небалансу, то есть, а тарифы равными нулю, то есть. Переменные– это объем груза, который останется уi-ого поставщика.
Аналогично, при выполнении условия (2.5) вводится фиктивный поставщик , то есть в матрице задачи добавляется строка. Запас груза фиктивного поставщика равен:, а тарифы равными нулю, то есть. Переменные– это объем груза, на который запросj-ого потребителя останется неудовлетворенным.
При преобразовании открытой модели задачи в закрытую модель, целевая функция не изменяется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
Целевая функция (2.1) и система ограничений (2.2) являются математической моделью сбалансированной ТЗ.
Пример 2.1
В трех хранилищах иимеется соответственно 70, 90 и 50 т топлива. Требуется спланировать перевозку топлива четырем потребителями, спрос которых равен соответственно 50, 70, 40 и 40т так, чтобы затраты на транспортировку были минимальными. Стоимость перевозки 1т (в усл. ден. ед.) указана в табл. 2.2.
Таблица 2.2
|
Потребители |
Запас топлива, т | ||||||||
Хранилища |
|
|
|
| ||||||
|
|
5 |
|
4 |
|
3 |
|
6 |
70 | |
|
|
|
|
|
|
|
| |||
|
|
4 |
|
3 |
|
5 |
|
1 |
90 | |
|
|
|
|
|
|
|
| |||
|
|
2 |
|
4 |
|
1 |
|
5 |
50 | |
|
|
|
|
|
|
|
| |||
Потребность в топливе, т |
50 |
70 |
40 |
40 |
|
Составить математическую модель транспортной задачи.
Решение
Т.к. условие (2.3) не выполнено, то задача несбалансированная. Приведем ее к сбалансированному виду. Поскольку запасы топлива в хранилищах () превышают спрос потребителей (), введем фиктивного потребителя, спрос которого равен. Все тарифы фиктивного потребителя будут равны нулю, т.е.. Распределительная таблица примет вид:
Таблица 2.3
|
Потребители |
Запас топлива, т | |||||||||
Хранилища |
|
|
|
|
| ||||||
|
|
5 |
|
4 |
|
3 |
|
6 |
|
0 |
70 |
|
|
|
|
|
|
|
|
|
| ||
|
|
4 |
|
3 |
|
5 |
|
1 |
|
0 |
90 |
|
|
|
|
|
|
|
|
|
| ||
|
|
2 |
|
4 |
|
1 |
|
5 |
|
0 |
50 |
|
|
|
|
|
|
|
|
|
| ||
Потребность в топливе, т |
50 |
70 |
40 |
40 |
10 |
210 |
Составим математическую модель сбалансированной транспортной задачи.
Обозначим – объемы перевозок топлива от-го хранилища-му потребителю.
;