Транспортная задача

Одним из наиболее важных частных случаев общей задачи линейного программирования является так называемая транспортная задача. Содержательно она формулируется следующим образом.

Пусть в пунктах А ₁, А ₂, …, А_m производится некоторый однородный продукт, причем объем производства этого продукта в пункте A_i составляет a_i единиц, i = 1, …, m. Произведенный в пунктах производства продукт должен быть доставлен в пункты потребления В ₁, В ₂, …, В_n, причем объем потребления в пункте B_j составляет b_j единиц продукта. Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта А_i в пункт В_j, составляют c_ij денежных единиц. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.

План перевозки груза в данной транспортной сети представляет собой массив элементов размерности m ´ n:

x = (x _{1, 1}, …, x _{1, n} , x _{2, 1}, …, x _{2, n} , …, x_{m , 1}, …, x_{m, n}).

Если реальная перевозка между пунктами i и j отсутствует, то полагают x_{i, j} = 0.

Ограничения на возможные значения x Î R ^{m n} имеют вид:

1. Ограничения на удовлетворение потребностей во всех пунктах потребления:

(3.28)

2. Ограничения на возможности вывоза запасов из всех пунктов производства:

(3.29)

3. Условия неотрицательности компонент плана:

x_{i, j} ³ 0, i = 1, …, m, j = 1, …, n. (3.30)

Математически транспортная задача ставится следующим образом: определить точку минимума функции суммарных транспортных издержек

при ограничениях (3.28)-(3.30).

Существенной характеристикой описываемой задачи является соотношение параметров a_i и b_j. Если суммарный объем производства равен суммарному объему потребления, а именно, выполняется условие баланса

(3.31)

то система называется сбалансированной. При выполнении условия баланса разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т. е. условия (3.28), (3.29) приобретают форму равенства. При таких ограничениях выполнение равенства (3.31) становится необходимым и достаточным условием для разрешимости транспортной задачи.

Специфическими для транспортной задачи являются следующие два обстоятельства: а) каждая из переменных x_{i, j} входит в два уравнения системы (3.28), (3.29); б) все коэффициенты при переменных x_{i, j} принимают лишь два значения 0 и 1. Эти особенности позволили разработать для решения транспортной задачи алгоритмы, существенно более простые, чем симплекс-метод.

Наиболее известным из таких алгоритмов является метод потенциалов. Этот метод может трактоваться как разновидность симплексных процедур. Он представляет собой итерационный процесс, на каждом шаге которого рассматривается некоторая текущая опорная точка, проверяется ее оптимальность с помощью теорем двойственности, а именно, утверждения 7) теоремы 3.6, и при необходимости определяется переход к “лучшей” опорной точке. Подробное описание метода потенциалов приведено в книгах [3, 6].

Контрольные вопросы и задания

3.1. Сформулируйте общую задачу линейного программирования?

3.2. Чем отличается основная задача ЛП от общей?

3.3. Чем отличается общая задача ЛП от канонической?

3.4. Всегда ли общую задачу ЛП можно привести к канонической форме? Опишите метод приведения общей задачи к каноническому виду.

3.5. Какие ограничения называют жесткими (нежесткими)?

3.6. Приведите пример существенных и несущественных ограничений?

3.7. Чем отличается выпуклый многогранник от выпуклого многогранного множества?

3.8. Дайте определение угловой точки выпуклого многогранного множества?

3.9. Сформулируйте основную теорему линейного программирования.

3.10. В чем заключается первая геометрическая интерпретация задачи ЛП?

3.11. В чем состоит идея геометрического метода решения задачи ЛП? Для каких задач он применим?

3.12. В чем заключается вторая геометрическая интерпретация задачи ЛП?

3.13. Дайте определения следующих понятий: опорная точка (опорный план) допустимого множества, базис опорной точки, базисные переменные.

3.14. Какая допустимая точка называется вырожденной? Какая задача ЛП называется вырожденной (невырожденной)? Какие проблемы могут возникать при решении вырожденных задач?

3.15. В чем состоит различие между симплекс-методом и методом полного пребора опорных точек допустимого множества?

3.16. Сформулируйте основные этапы стандартной итерации симплекс-метода.

3.17. Для чего применяется преобразование Жордана- Гаусса?

3.18. Как с помощью симплекс-метода определить, что задача ЛП не имеет решения?

3.19. Что такое разрешающий элемент и разрешающее уравнение? Для чего они используются?

3.20. Дайте определение двойственной задачи ЛП.

3.21. Каким свойством обладает отношение двойственности?

3.22. Перечислите основные свойства пары двойственных задач (теоремы двойственности)?

3.23. Каково практическое значение теорем двойственности?

3.24. Какая из теорем двойственности является критерием оптимальности для задач ЛП и в чем ее суть?

3.25. Дайте содержательную формулировку и математическую постановку трнспортной задачи?

3.26. Что такое условие баланса и какова его роль в транспортных задачах?

3.27. Определите, какие из ограничений многогранных множеств являются нежесткими, какие несущественными.

а) - х ₁ + х ₂ - 2 х ₃ ³ -1, б) - х ₁ + 2 х ₂ ³ -1,

- х ₁ - 3 х ₂ + х ₃ ³ 0, - х ₁ + х ₂ ³ -3,

- х ₁ - 3 х ₂ - 2 х ₃ ³ -5, - х ₁ - 2 х ₂ ³ -5,

2 х ₁ + 2 х ₂ + х ₃ = 6. х ₁ + 2 х ₂ = 4.

3.29. Приведите следующую задачу ЛП к канонической форме:

f (x) = -3 x ₁ + 4 x ₂ - 2 x ₃ + 5 x ₄ ® min,

X: 4 x ₁ - x ₂ + 2 x ₃ - x ₄ = -2,

x ₁ + x ₂ + 3 x ₃ - x ₄ £ 14,

-2 x ₁ + 3 x ₂ - x ₃ + 2 x ₄ ³ 2,

x ₁ ³ 0, x ₂ ³ 0.

Укажите какую-нибудь начальную опорную точку допустимого множества полученной канонической задачи и базисные переменные этой опорной точки.

3.30. Решите следующую задачу с помощью симплекс-метода:

f (x) = - x ₁ - 3 x ₂ ® min,

X: x ₁ £ 5, x ₂ £ 4,

x ₁ - 2 x ₂ ³ 2,

x ₁ ³ 0, x ₂ ³ 0.

Изобразите допустимое множество в координатах (х ₁, х ₂). Проследите за движением от одной опорной точки к другой на графике в соответствии с последовательностью шагов симплекс-метода.

3.31. Постройте двойственные задачи к общим задачам ЛП и соответствующим им каноническим задачам из упражнений 3.29 - 3.31.

3.32. В сплав может входить не менее 4% никеля и не более 80% железа. Для составления сплава используются три вида сырья, содержащего никель, железо и прочие вещества. Стоимость различных видов сырья составляет 6, 4 и 5 руб за 1 кг cырья I, II и III вида соответственно. Процентное содержание в нем соответствующих компонентов сплава представлены в табл. 3.1. Сформулируйте задачу ЛП определения состава шихты, при котором стоимость 1 кг сплава будет минимальной.

Таблица 3.1

3.33. Металлургический цех выпускает три вида продукции: А, Б и В. Цех располагает необходимым оборудованием, каждый тип которого имеет свой фонд рабочего времени и производительность (табл. 3.2)

Таблица 3.2

Прибыль от тонны произведенной продукции каждого вида составляет соответственно 35, 25 и 40 руб. Сформулируйте задачу ЛП определения плана выпуска продукции, обеспечивающего максимум прибыли.

Глава 4. МЕТОДЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

При решении многих оптимизационных задач на искомые переменные по их физическому смыслу необходимо наложить дополнительные ограничения дискретности. Иными словами, некоторые (возможно все) переменные должны принимать только определенный набор дискретных значений. Это имеет место, например, когда искомыми величинами являются неделимые объекты (машины, комплекты оборудования, предприятия и т. д.). Такие задачи называют задачами дискретной оптимизации. Они могут быть как линейными, так и нелинейными. Чаще всего в задачах дискретной оптимизации требуется, чтобы искомые переменные принимали только целые значения, т. е. удовлетворяли условию целочисленности. Если все переменные задачи целочисленны, то ее называют задачей целочисленного программирования. Данная глава посвящена линейным задачам целочисленного программирования.