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

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

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

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

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

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

                            x11 + x12 + x13 = 320

                            x21 + x22 + x23 = 280

                            x31 + x32 + x33 = 270

                            x41 + x42 + x43 = 350

                            x11 + x21 + x31 + x41 = 450

                            x12 + x22 + x32 + x42 = 370

x13 + x23 + x33 + x43 = 400

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

              F = 2x11 + 3x12 + 4x13 + 1x21 + 5x22 + 3x23 + 6x31 + 4x32 + 2x33 + 7x41 + 8x42 + 5x43

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