Курсовая работа: Решение задач линейного программирования в среде Maple

а₁₁ Х₁ +а₁₂ +...+а_1n X_n <= b₁

Аналогично для остальных ресурсов:

а₂₁ Х₁ +а₂₂ +...+а_2n X_n <=b₂

а₃₁ Х₁ +а₃₂ +...+а_3n X_n <=b₃

.........................................

а_m1 Х₁ +а_m2 +...+a_mn X_n <=b_m

Кроме того, количество выпущенной продукции не может быть отрицательной, следовательно, Х₁ >= 0, X₂ >=0, ...,X_n >=0.

§3. Постановка Транспортной задачи (ТЗ) для n переменных

Пусть имеется несколько поставщиков однородной продукции (каждый с определенным запасом) и несколько потребителей этой продукции (с известными потребностями у каждого). Задана также сеть коммуникаций (дорог, рек, воздушных линий и т.д.) связывающая каждого поставщика с каждым потребителем. На каждой коммуникации задана цена перевозки – стоимость перевозки единицы продукции. Если какая – либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+∞). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.

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

Транспортные задачи бывают:

1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)

2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)

Метод потенциалов «работает» только для закрытых ТЗ, причем, закрытая ТЗ всегда разрешима.

Открытую ТЗ сводят к закрытой ТЗ путем прибавления к суммарному запасу продукции или суммарной потребности продукции недостающих единиц до равенства суммарного запаса продукции и суммарной потребности продукции.

Закрытая транспортная задача формулируется как Задача Линейного Программирования (ЗЛП) следующего вида:

, где

- запас i – го поставщика

- потребность j – го потребителя

- цена перевозки единицы продукции по коммуникациям (i,j)

(от i – го поставщика к j – му потребителю)

- объем перевозки продукции (неизвестный) по коммуникациям (i,j).

Для вывода критерии оптимальности транспортной задачи построим двойственную задачу.

Структура матрицы ограничений транспортной задачи такова, что столбец, соответствующей переменной содержит ровно два ненулевых элемента: единицу в строке с номером i и единицу в строке m + i.

Вектор двойственных переменных Y = (,…,,,…,) имеет m + n компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные ,,…, - потенциалы поставщиков; переменные ,…,- потенциалы потребителей.

Используя схему для построения двойственной задачи к ЗЛП в стандартной форме, имеем: