Венгерский метод решения задач линейного программирования о назначении

2. Практическая  часть

    2.1 Постановка задачи

      Мясокомбинат имеет в своем  составе четыре завода, на каждом из которых могут изготавливаться три вида колбасных изделий. Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 т/сут. Ежедневные потребности в колбасных изделиях каждого вида также известны и соответвено равны 450,370 и 400 т. Зная себестоимость 1 т каждого вида колбасных изделий на каждом заводе, которая определяется матрицей

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

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

  x₁₁ + x₁₂ + x₁₃ = 320

            x₂₁ + x₂₂ + x₂₃ = 280

            x₃₁ + x₃₂ + x₃₃ = 270

            x₄₁ + x₄₂ + x₄₃ = 350

            x₁₁ + x₂₁ + x₃₁ + x₄₁ = 450

            x₁₂ + x₂₂ + x₃₂ + x₄₂ = 370

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 400

      При данном плане X = (x_ij) (i=1,4 ; j=1,3) перевозок общая стоимость перевозок составит

      F = 2x₁₁ + 3x₁₂ + 4x₁₃ + 1x₂₁ + 5x₂₂ + 3x₂₃ + 6x₃₁ + 4x₃₂ + 2x₃₃ + 7x₄₁ + 8x₄₂ + 5x₄₃

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