Главная | Обратная связь

Решение, соответствующее начальной точке алгоритма, называется начальным (опорным) решением.

Задача. Фирма изготавливает два вида красок для внутренних (В) и наружных (Н) работ. Используется два расходных продукта А и С, суточные запасы которых ограничены (не более 6 т для продукта А и не более 8 т для С). Расходы продуктов А и С на 1 т красок .

	В	Н
А
С

Суточный спрос на В не превышает спроса на Н более чем на 1 т. Спрос на краску В не превышает 2 т. Производить нужно не менее 1 т в сутки. Оптовые цены: 3 тыс. $ за 1 т краски Н и 2 тыс. $ за 1 т краски В. Какое количество краски каждого вида должна производить фабрика, чтобы доход от продажи был максимальным?

Решение. и - суточный объем производства краски Н и В. Объем производства не может быть отрицательной величиной Целевая функция . Ограничения: на расход сырья , на величину спроса , на объем производства Построим многоугольник, координаты точек которого удовлетворяют всем ограничениям.

Найдем в какой точке целевая функция максимальна.

Максимум достигается в точке и равен .

Симплекс-метод решения задачи линейного программирования.

Постановка задачи.

Задача с ограничениями типа равенства

Функционал

Приведение ограничений к стандартной форме.

1. Неравенства сводятся к равенствам.

Вводим остаточную переменную .

Если ограничение интерпретируется как расход ресурса, то - это остаток, неиспользуемая часть.

Вводим избыточную переменную .

Правая часть ограничений должна быть положительной.

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

Решение, соответствующее начальной точке алгоритма, называется начальным (опорным) решением.

Частный случай:

Решение ¾

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

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