IV. Методические указания

Тема 1. Общее линейное программирование (ЛП).

Основные понятия и определения.

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

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

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

В общем виде математическая модель задачи линейного программирования записывается как

при условиях-ограничениях

a _ij, b _i, c _j – заданные постоянные величины.

Определение. Стандартной (или симметрической) задачей ЛП называется задача, имеющая вид

или

Определение. Канонической (или основной) задачей ЛП называется задача, имеющая вид

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

Определение. Совокупность чисел при котором целевая функция принимает максимальное (минимальное) значение называется оптимальным решением задачи ЛП.

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