Сущность, виды и задачи управления

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения или опорного плана. Решение ТЗ всегда существует. Из чисто физических соображений ясно, что хоть какой-то допустимый план существовать должен. Среди допустимых планов непременно имеется оптимальный, потому что линейная целевая функция - стоимость перевозок заведомо неотрицательна (ограничена снизу нулем). Рассмотрим построение опорного плана «способом северо-западного угла». Поясним его на конкретном примере.

Условия ТЗ заданы следующей транспортной таблицей.

ПО / ПН						Запасы
Заявки

Будем заполнять таблицу перевозками постепенно, начиная с левой верхней ячейки (1,1) («северо-западного угла» таблицы). Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте , и запишем перевозку 18 в клетке (1,1). После этого заявка пункта удовлетворена, а в пункте осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта назначим пункту . В составе заявки пункта остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта , чем его запас будет исчерпан, и еще 9 возьмем из пункта . Из оставшихся 18 единиц груза пункта 12 выделим пункту ; оставшиеся 6 единиц назначим пункту , что вместе со всеми 20 единицами пункта покроет его заявку.

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

ПО / ПН						Запасы
	18 10	27 8	3 5
			30 8
			9 10	12 8	6 7
					20 8
Заявки

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию = 8. Остальные клетки – свободные (пустые), в них стоят нулевые перевозки, их число равно = 12. Значит, полученный план – опорный и поставленная задача построения опорного плана решена.

Является ли этот план оптимальным по стоимости? Нет, ведь при его построении не учитывались стоимости перевозок. Поэтому план не получился оптимальным. Стоимость этого плана найдется, если умножить каждую перевозку на соответствующую стоимость и сложить. Имеем 18 10+27 8 +3 5+30 8+9 10+12 8+6 7+20 8=1039.

Попробуем улучшить этот план, перенеся, например, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушить баланса, перенесем те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план

ПО / ПН						Запасы
		27 8	21 5
	18 6		12 8
			9 10	12 8	6 7
					20 8
Заявки

Можно убедиться, что стоимость нового плана равна

27 8+21 5 +18 6+12 8+9 10+12 8+6 7+20 8=913, т.е. на 126 единиц стоимости меньше стоимости полученного ранее плана.

Итак, за счет циклической перестановки 18 единиц груза из одних клеток в другие удалось понизить стоимость плана. На этом основан алгоритм оптимизации плана перевозок.

Среди разных разделов математического программирования наиболее развитым и законченным является линейное программирование (ЛП).

Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи и т.д.

Рассмотрим один пример: определения оптимального ассортимента.

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

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

максимизировать при ограничениях , .

Общая постановка задачи линейного программирования. Имеется ряд неотрицательных переменных . Требуется так выбрать значения этих переменных, чтобы: 1) выполнялись некоторые ограничения, имеющие вид линейных неравенств или равенств относительно переменных ; 2) некоторая линейная функция тех же переменных обращалась в максимум (минимум). Математический аппарат линейного программирования предназначен специально для решения таких задач. Может возникнуть вопрос: а нужен ли такой специальный аппарат? Нельзя ли просто продифференцировать целевую функцию по аргументам , приравнять производные нулю и решить полученную систему уравнений? Нет, оказывается, сделать этого нельзя. Так как функция линейна, производные от нее по всем аргументам постоянны и нигде в нуль не обращаются. Максимум (или минимум) функции , если он существует, достигается всегда где-то на границе области возможных значений , т.е. там, где начинают действовать ограничения. Математический аппарат линейного программирования позволяет нам последовательно, в кратчайшие сроки, обследовать границы области возможных значений и найти на этих границах то решение, которое является оптимальным, т.е. такую совокупность значений , при которой линейная функция обращается в максимум или минимум.

Сущность, виды и задачи управления