16. Решение двойственных задач симплекс-методом.

17. Постановка и модель «транспортной задачи». Условие разрешимости модели. Постановка задачи

Пусть имеем m пунктов, в которых находится известное количество однородных грузов (поставщики), порядковый номер поставщика – i, т.е. . Наличие грузов у поставщиков - .

Имеется n пунктов, испытывающих потребность в этих грузах (потребители), порядковый номер потребителя – j, т.е. - потребность в грузах каждого потребителя. Известна «цена» перевозки единицы груза от каждого поставщика к каждому потребителю - .

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

-общие затраты на перевозку грузов должны быть минимальными

- все грузы от поставщиков должны быть вывезены

-потребности потребителей в грузах должны быть удовлетворены.

Модель задачи

Целевая функция описывает затраты на перевозку грузов

Система ограничений описывает 2 и 3 условие

Условие неотрицательности переменных величин

Структурная форма записи модели

Условие разрешимости задачи

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

- условие разрешимости задачи

Если оно выполняется, то задача является задачей закрытого типа, если нет, то открытого типа.

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

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

18. Понятие ациклического плана решения задачи. Случай вырожденности.

Вариант решения задачи, полученный в любой рабочей таблице обязательно должен быть ациклическим, то есть нельзя, чтобы по занятым клеткам можно было построить замкнутый контур с прямыми углами. Вариант всегда будет ациклическим, когда количество заполненных клеток N не будет превышать количество поставщиков+потребителей без единицы, то есть N m+n-1.

При этом, если N=m+n-1, тогда вариант не вырожденный, а если N<m+n-1, то вариант вырожденный. Если вариант окажется вырожденным, то для дальнейшего решения задачи необходимо из числа свободных клеток взять недостающее количество клеток, ставим туда 0 и условно считаем занятыми. Нули проставляются в такие клетки, чтобы вариант остался ациклическим. В каждой рабочей таблице все занятые клетки объединены между собой единой цепью. В этой цепи могут быть несколько ответвлений. От 1 занятой клетки до другой в цепи можно переходить или по строке или по столбцу, поворачивая под прямым углом. Если вариант вырожденный, то единая цепь разрывается, и 0 ставится в такую клетку, чтобы разрыв ликвидировать.