Математика Экономико-математические методы Векслер В.А., к.п.н

Лекция «Решение задач линейного программирования»

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

Алгоритм симплекс-метода 1. Записываем данную задачу в исходную симплекс-таблицу. 2. Если все элементы оценочной строки симплексной таблицы неотрицательны, то исходный план является оптимальным. 3. Если в оценочной строке содержится отрицательный элемент, над которым в таблице нет положительных элементов, то целевая функция не ограничена сверху и задача не имеет решения.

Правило нахождения оценок Оценка для х j равна сумме произведений элементов данного столбца на соответствующие элементы первого столбца (С j - базисные) минус С j данного столбца (коэффициент над х j ).

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

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

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

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи а число ограничений в системе двойственной задачи – числу переменных в исходной задаче. 4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.

Пример 3. Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице (следующий слайд). Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продукции. Оценки, приписываемые каждому из видов сырья, должны быть такими, чтобы оценка всего используемого сырья была минимальной.