Решение транспортной задачи распределения методом потенциалов — страница 2

  • Просмотров 242
  • Скачиваний 7
  • Размер файла 43
    Кб

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

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

решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F-> max, уменьшение — при отыскании минимума F-> min). Формулировка проблемы в практической области Отимизация выбора распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям с целью, определения наиболее экономичного плана перевозки продукции

одного вида из нескольких пунктов отправления в пункты их назначения. Цель работы – определение метода расчета плана перевозки продукции со склада по предприятиям-потребителям, при котором обеспечивается минимальные транспортные расходы на перевозку всей продукции. Формальная (математическая постановка задач) Задача о размещении (транспортная задача) Это задача, в которой работы и ресурсы измеряются в одних и тех же

единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям. Дана система из m линейных уравнений и неравенств с n переменными: a11x1+a12x2+…+a1nxn ≤ b1 a21x1+a22x2+…+a2nxn ≤ b2 ak1x1+ak2x2+…+aknxn ≤ bk am1x1+am2x2+…+amnxn ≤

bm1 и линейная функция F=c1x1+c2x2+…+cnxn (2) Необходимо найти такое решение (план) системы X=(x1,x2….,xj….,xn) (3) где xj <0(j=1,2,…,l, l ≤ n) (4) при котором линейная функция F (2) принимает оптимальное), есть максимальное или минимальное в зависимости от задачи) значение. При этом система (1) - система ограничений, а функция F (2) - целевая функция (функция цели). Анализ постановки задач и обоснования метода решения Анализируя исходные условия задачи, следует