Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 57


Добавим, что современные ЭВМ, как правило, снабжены подпрограммами для решения задач линейного программирования, так что лицу, желающему их решать, нет даже особой надобности обучаться решению таких задач «вручную» — труд крайне неприятный и изнурительный.

§ 10. Транспортная задача линейного программирования

В предыдущем параграфе мы описали некоторые общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые, в силу особой своей структуры, допускают решение более простыми методами. Из них мы остановимся только на одной — так называемой «транспортной задаче» (ТЗ). Она ставится следующим образом: имеются т

пунктов отправления (ПО) A1, А2., ..., An, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно a1, a2, ..., am единиц. Имеются п пунктов назначения (ПН) В1, В2,..., Вn, подавших заявки соответственно на b1, b2, ..., bn единиц груза. Сумма всех заявок равна сумме всех запасов:

            (10.1)

Известны стоимости cij перевозки единицы груза от каждого пункта отправления Ai до каждого пункта назначения Вj (i=l, 2,..., т; j=1,

2,..., n). Все числа су, образующие прямоугольную таблицу (матрицу), заданы:

             (10.2)

Коротко матрицу (10.2) будем обозначать (cij).

Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.

Требуется составить такой план перевозок (откуда, куда и сколько единиц везти), чтобы все заявки были выполнены, а общая стоимость всех перевозок минимальна.

Поставим эту задачу как задачу линейного программирования. Обозначим xij, — количество единиц груза, отправляемого из i-го ПО Ai в j-и ПН Bj. Неотрицательные переменные xij тоже можно записать в виде матрицы

               (10.3)

которую мы будем коротко обозначать (хij). Совокупность чисел (хij) (10.3) мы будем называть «планом перевозок», а сами величины хij — «перевозками». Эти неотрицательные переменные должны удовлетворять следующим условиям.




Содержание  Назад  Вперед