4. Понятие о линейном программировании.
Решение систем неравенств находит многочисленные практические приложения. Наиболее важные из них связаны с задачами экономики и планирования. Чаще всего эти задачи формулируются так: найти наилучший план производства при заданных ресурсах. Задание ресурсов имеет обычно вид неравенств. Поэтому приходится искать наибольшее или наименьшее значение, принимаемое некоторой функцией в области, заданной системой неравенств.
Приведем пример такой задачи:
Имеются два пункта производства А и В некоторого вида продукции и три пункта I, II, III его потребления. В пункте А производится 250 единиц продукции, а в пункте 
единиц. В пункте I
требуется 150 единиц, в пункте II — 240 единиц и в пункте III — 210 единиц. Стоимость перевозки одной единицы продукции из пункта производства в пункт потребления дается следующей таблицей.
Таблица 1
Требуется оставить план перевозки продукции, при котором сумма расходов на перевозку будет наименьшей.
Обозначим количество продукции, перевозимой из пункта А в пункт I, через х, а из пункта А в пункт II — через у. Так как полная потребность в пункте I равна 150 единиц, то из пункта В надо еще завезти 
единиц. Точно так же из пункта В в пункт II надо завезти 
единиц. Далее, производительность пункта А равна 250 единиц, а мы уже распределили 
единиц. Значит, в пункт III идет из пункта 
единиц. Чтобы полностью обеспечить потребность пункта III, осталось завезти 
единиц из пункта В.
Итак, план перевозок задается следующей таблицей.
Таблица 2
Чтобы найти полную стоимость перевозки, надо умножить каждое число этой единицы на соответствующее число таблицы 1 (там указана стоимость перевозки одной единицы продукции) и сложить полученные произведения. Мы получим выражение:
По условию задачи требуется найти минимум этого выражения. Но величины х и у не могут принимать произвольных значений.
(кликните для просмотра скана)
Итак, нам надо найти минимум функции 
в области, задаваемой системой неравенств (2). Эта область изображена на рис. 34 — она является многоугольником, ограниченным прямыми
Решая совместно уравнение этих прямых, находим координаты вершин многоугольника:
Функция 
принимает наименьшее значение в одной из вершин многоугольника 
В самом деле, выясним, где располагаются точки, в которых значения этой функции одинаковы (так называемые линии уровня функции 
). Если значение функции 
равно с, то 
. Но это уравнение прямой линии. Значит, для функции линиями уровня являются прямые линии 
Все эти прямые параллельны друг другу.
Если линия уровня пересекает многоугольник, то соответствующее значение с не является ни наименьшим, ни наибольшим. Ведь немного изменив с, мы получим прямую, которая также пересекает многоугольник. Если же линия уровня проходит через одну из вершин многоугольника, причем весь многоугольник остается на одну сторону от этой линии, то соответствующее значение с является наименьшим или наибольшим. Когда с меняется в одну сторону, то получается линия, пересекающая многоугольник, а когда меняется в противоположную сторону, получается линия, не имеющая с многоугольником общих точек.
Итак, функция 
принимает наименьшее значение на многоугольнике в одной из его вершин. Поскольку мы уже знаем эти вершины, то подставим соответствующие значения координат и найдем, что
Наименьшим из этих значений является 2300. Это значение функция принимает в точке 
. Значит, 
Подставляя эти значения в план перевозок (см. таблицу II), получаем:
Таким образом, из пункта А в пункт I надо перевезти 10 единиц продукции, из пункта А в пункт II — 240 единиц и т. д. Стоимость намеченного плана равна 2300.
Рассмотренная задача относится к большому классу задач, возникающих не только в экономике, но и в других областях человеческой деятельности. В этих задачах требуется найти наибольшее или наименьшее значение некоторой линейной функции от переменных 
При этом область изменения переменных задается системой линейных неравенств
и линейных уравнений
Задачи такого типа называются задачами линейного программирования.
Упражнения
(см. скан)
