Задача линейного программирования

Задача линейного программирования: основные определения

Линейное программирование – метод решения задач оптимизации.

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

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

Функция цели в задаче линейного программирования обычно записывается так:

.

Или в сокращённом виде с сигмой:

.

Можно встретить обозначение целевой функции и через C, и через F.

Система ограничений в задаче линейного программирования в канонической форме записывается так:

.

Или в сокращённом виде: