Общая постановка задачи оптимизации металлургических процессов, страница 8

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

С использованием условий оптимальности и допустимости определяются включаемая и исключаемая переменные и методом Гаусса-Жордана осуществляется поиск нового базисного решения.

Сетевые модели

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

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

Из-за большого числа переменных и ограничений непосредственное применение симплекс-метода затруднительно. Поэтому разработаны более эффективные алгоритмы, которые в большинстве случаев основываются на теории линейного программирования.

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

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

Общая постановка транспортной задачи:

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

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

x = (x₁₁, …, x_1n, x₂₁, …, x_2n, …, x_m1, …, x_mn).

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

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

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

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

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

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

при ограничениях (1)-(3).

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