Первая теорема двойственности

Если одна из задач двойственной пары имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т.е. .

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

Вторая теорема двойственности

План прямой задачи и план двойственной задачи являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство .

 

КЛАССИЧЕСКАЯ ТРАНСПОРТНАЯ ЗАДАЧА

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

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

В общем виде задача может быть сформулирована следующим образом.

Однородный продукт, сосредоточенный в пунктах производства (хранения) в количествах единиц, необходимо распределить между пунктами потребления, которым необходимо соответственно единиц. Стоимость перевозки единицы продукции из i-го пункта отправления в j-й пункт назначения равна c_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором:

1) запасы всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальными.

Если производство и потребление сбалансированы, т. е. суммарные запасы продукта у поставщиков равны суммарным запросам потребителей:

, (5.1)

то такая транспортная задача называется закрытой или замкнутой. Если же суммарные запасы продукта у поставщиков строго больше или строго меньше, чем суммарные запросы потребителей, то такая задача называется открытой.

Для сведения открытой задачи к закрытой вводятся фиктивные пункты производства или потребления. Если суммарные запасы продукта у поставщиков строго больше, чем суммарные запросы потребителей, вводится фиктивный потребитель, запросы которого равны . Если же суммарные запасы продукта у поставщиков строго больше, чем суммарные запросы потребителей, то вводится фиктивный поставщик, запас продукта у которого равен .

План перевозок, содержащий фиктивные поставки, называется вырожденным.

Пусть

– пункты производства некоторой однородной продукции, ;

– объем производства в пункте ;

– пункты потребления продукции, ;

– потребность в продукции пункта ;

– стоимость перевозки единицы продукции из пункта в любой пункт .

А1

А2

Аm

B1

B2

Bn

с11

с12

с2n

сmn

с22

сm1

а1

а2

аm

b1

b2

bn

с1n

Рис. 5.1. Транспортная задача

Математическая модель КТЗ

Пусть – количество продукции, планируемое к перевозке из пункта А_i в B_j. Тогда, при наличии баланса производства и потребления (5.1) математическая модель транспортной задачи будет выглядеть следующим образом:

найти план перевозок

, где ; ,

минимизирующий общую стоимость всех перевозок

(5.2)

при условии, что из любого пункта производства вывозиться весь продукт

, где (5.3)

и любому потребителю доставляется необходимое количества груза

, где (5.4)

причем, по смыслу задачи

. (5.5)

Здесь целевая функция (5.2) отражает суммарные транспортные расходы. Ограничения (5.3) требуют, чтобы вся продукция была вывезена, а ограничения (5.4) – чтобы потребности всех пунктов потребления были удовлетворены. Условие (5.5) вытекает из физического смысла введенных переменных.

Ограничения (5.3) – (5.5) задают планы перевозок X. Таким образом, математическая модель КТЗ относится к классу задач линейного программирования.

Для решения транспортной задачи чаще всего применяется метод потенциалов. На каждом шаге происходит переход по определенным правилам от одного базисного решения к другому путем заполнения транспортных таблиц. В данной таблице:

1) строки соответствуют поставщикам (в заголовках строк указываются запасы продукта у поставщиков a_i);

2) столбцы соответствуют потребителям (в заголовках столбцов указываются запросы потребителей b_j);

3) в клетки заносятся поставки продукта, перевозимого от соответствующего поставщика к соответствующему потребителю (x_ij);

4) в правом верхнем углу каждой клетки указывается стоимость перевозки единицы продукта от соответствующего поставщика к соответствующему потребителю (c_ij).

Таблица 5.1 – Транспортная таблица.

Потребление Производство	b1	b2	…	bn
а1		с11		с12	…		с1n
x11	x12	x1n
а2		с21		с22	…		с2n
x21	x22	x2n
. . .	. . .	. . .		. . .
аm		сm1		сm2	…		сmn
xm1	xm2	xmn

Так как в системе (5.3) – (5.5) ровно (m+n–1) линейно независимых уравнений, то в любой транспортной таблице должно быть m+n–1 занятых клеток.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. Авраам Линкольн, Первая инаугурационная речь, 4 марта 1861 г.
2. Виды зависимостей между атрибутами в отношениях. Первая нормальная форма. Вторая нормальная форма. Третья нормальная форма.
3. Волюнтаризм: первая классическая система.
4. Глава первая Хадис о проповеди у источника аль-Гъадирь.
5. Глава первая. Понятие о праве собственности и историческое происхождение права поземельной собственности
6. Гражданское право часть первая
7. Емлетясения. Поражающие факторы. Шкала МСК-78. Меры защиты населения, правила поведения людей во время землетрясений, первая помощь. Синдром длительного раздавливания
8. Закон больших чисел и центральная предельная теорема
9. Земское право (Landrecht) Книга первая
10. Земское право (Landrecht) Книга первая
11. История про Энни Часть первая
12. Какова первая причина потери бенефиция