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




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


1. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте. Это даст нам т условий-равенств:

          (10.4)

2. Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом. Это даст нам п условий-равенств:

          (10.5)

3. Суммарная стоимость всех перевозок, то есть сумма величин хij, умноженных на соответствующие стоимости cij, должна быть минимальной:

          (10.6)

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, т. е. но всем парам ПО — ПН.

Мы видим, что перед нами — задача линейного программирования с условиями-равенствами (10.4), (10.5) и минимизируемой линейной функцией (10.6). Особенностью этой задачи является то, что все коэффициенты в условиях (10.4), (10.5) равны единице — это позволяет решать задачу очень простыми способами. О них и пойдет речь.

Прежде всего, замечаем, что условия-равенства (10.4), (10.5) не являются линейно независимыми, так как их правые части связаны условием (10.1). Число линейно независимых среди уравнений (10.4), (10.5) равно не m + n (числу уравнений), а т + п — 1. Общее число переменных xij в нашей задаче равно т • п; как бы ни разрешать уравнения (10.4), (10.5), число базисных переменных будет равно т + п — 1, а число свободных переменных

k = тп – (т + п - 1) = (т - 1) (n - 1).

Мы знаем, что в задаче линейного программирования оптимальное решение достигается в одной из вершин ОДР, в опорной точке, где по крайней мере k переменных равны нулю. Значит, в пашем случае для оптимального плана по крайней мере (m - 1) (n - 1) перевозок должны быть равны нулю (из соответствующих ПО в соответствующие ПН ничего не перевозится).

Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (10.4), (10.5) (все заявки удовлетворены, все запасы исчерпаны). Допустимый план будем называть опорным, если в нем отличны от нуля не более т + п -




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