Двухиндексные задачи линейного программирования

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

мы должны найти матрицу значений Хij. размерность этой матрицы будет пропорциональна числу поставщиков и потребителей (3 поставщика 4 потребителя - размер матрицы 3× 4). также должны найти транспортные расходы на перевозку всей продукции (они должны быть минимальными, но все участники должны быть удовлетворены).

этапы построения модели:

1) определение переменных (обозначаются с помощью двух индексов: 1 индекс - отправитель, 2 индекс - получатель (Х11 - от первого отправителя к первому получателю, Х12 - от первого отправителя ко второму получателю).

2) проверка сбалансированности задачи

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

3) построение сбалансированной транспортной матрицы

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

4) задание ЦФ

вводятся в общем виде все переменные (Х11 * стоимость перевозки до первого поставщика Х12 + Х13 * соответствующую стоимость). если 12 переменных, то ЦФ будет содержать 12 слагаемых.

мы должны найти такую конфигурацию перевозок, чтобы транспортные издержки стали минимальными. Cij - стоимость перевозки от i поставщика к j потребителю. Хij - это обьем перевозок. т.е. все это - сумма произведений стоимости перевозок на обьем перевозки.

5) задание ограничений

1 условие: обьем перевозок в нашей системе должен быть равен обьему запаса. а- запас у поставщика, в- потребность.

2 условие - сумма всех перевозок дб равна сумме всех потребностей. n - число поставщиков, m - число потребителей.

и обязательно условие неотрицательности.

общий вид транспортной матрицы:

тарифы на перевозку (С21 - тариф на перевозку от 2 поставщика к 1 потребителю).

обязательно указывается условие балансировки, что сумма всех запасов Аi равна сумме всех потребностей. если модель несбалансирована, то мы вводим 2 формулы

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

определение переменных

проверка сбалансированности задачи

есть заводы есть потребители. обьем производства автомобилей 3500 шт/кв. и обьем потребления 3700 (задача несбалансированна). вводим фиктивного производителя, чтобы добавить 200 фиктивных машин.

рисуем транспортную матрицу.

сумма совпадает, значит модель сбалансировали.

пишем ЦФ.

затем задаем ограничения: обьем перевозок Х11 + Х12 перевозка от первого поставщика до 1 и2 потребителя. сначала рассматриваем все по горизонтали, затем по вертикали.

Методы нахождения опорных планов

Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. " Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

Метод северо-западного угла

На каждом шаге метода с еверо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов.

Для того, чтобы заполнить клетку (i, j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце .

Если существующий запас позволяет перевезти всю потребность, то

 в клетку (i, j) в качестве перевозки вписывается значение потребности ;

 j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

 от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. .

Если существующий запас не позволяет перевезти всю потребность, то

 в клетку (i, j) в качестве перевозки вписывается значение запаса ;

 i-я строка вычеркивается, поскольку ее запас уже исчерпан;

 от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. .

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.