![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка задачи линейного программирования
Простейшим случаем задачи математического программирования является задача линейного программирования. Она соответствует случаю, когда левые части ограничений (3.1) и целевая функция (3.2) представляют собой линейные функции относительно Рассмотрим более подробно общую постановку задачи линейного программирования. Пусть дана система т линейных независимых уравнений с неизвестными
где, не уменьшая общности, можно считать Характерной особенностью данной задачи является то, что число уравнений меньше числа неизвестных, т.е.
называемую линейной формой. Более компактно в матричной форме задача линейного программирования может быть записана так:
где Любое решение системы (3.3) с неотрицательными значениями переменных будем называть допустимым решением. Таким образом суть задачи линейного программирования состоит в том, чтобы из множества допустимых решений выбрать одно, а именно такое, которое обращает в минимум или максимум линейную форму (3.4). Иногда в задаче линейного программирования все или некоторые из уравнений вида (3.3) имеют вид неравенств. Так, вместо уравнения
Однако такие неравенства легко превратить в уравнения, введя добавочную переменную
Такое изменение приводит просто к увеличению числа переменных, но не меняет существа задачи. Введем терминологию, широко используемую в задачах линейного программирования. Базисом называют любой набор Если положить все свободные переменные равными нулю и решить полученную систему Допустимым базисным решением является такое базисное решение, которое одновременно допустимо, т.е. которое дает неотрицательные значения базисных переменных.
|