1 Линейное программирование
1.1 Постановка задачи линейного программирования.
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом, были заложены основы линейного программирования. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
(1)
при условиях
(2)
(3)
(4)
Функция (1) называется целевой функцией (или линейной формой) задачи (1) – (4), а условия (2) – (4) – ограничениями данной задачи.
2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции (1) при выполнении условий (2) и (4), где k = m, s = n.
3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (1) при выполнении условий (3) и (4), где k = 0, s = n.
1.2. Формы записи задачи линейного программирования
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа:
Стандартная задача линейного программирования
max(
(5)
…,
или, в матричной записи,
max <c, x>
Ax ≤ b, x ≥ 0, (6)
где 
—матрица
коэффициентов. Вектор c называется
вектором коэффициентов линейной
формы, b —
вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач линейного программирования.
Каноническая задача линейного программирования
max(
(7)
…,
или, в матричной записи,
max <c, x>
Ax = b, x ≥ 0, (8)
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.