Математика Экономико-математические методы Векслер В.А., к.п.н

Лекция «Математическая постановка задач линейного программирования»

Определение. Функция называется линейной, если она представима в виде:, где произвольные константы.

Определение Задача называется задачей линейного программирования, если все функции, входящие в постановку задачи - являются линейными.

Задача линейного программирования Это развёрнутая форма записи Линейная целевая функция Линейные ограничения Условия неотрицательности переменных … … … … …

Задача линейного программирования Это каноническая форма записи Линейная целевая функция Линейные ограничения Условия неотрицательности переменных Любую ЗЛП можно записать в каноническом виде (ограничения – равенства, свободные члены неотрицательны, решается на максимум) … … …

Задача линейного программирования Это матричная форма записи – Она тождественна канонической форме Линейная целевая функция Линейные ограни-чения Условия неотрицательности переменных

– Задача линейного программирования может: не иметь ни одного оптимального решения – допустимой области не существует – система ограничений не совместна z = max(x 1 +x 2 |x 1 +5x 2 1, x 1 +x 2 5, x 1 0, x 2 0) – допустимая область существует, но не ограничивает целевую функцию z = max(2x 1 +x 2 |0.1x x 2 5, x 1 0, x 2 0) иметь одно оптимальное решение z = max(x 1 +x 2 |0.1x x 2 5, x 1 0, x 2 0) x 1 =50, x 2 =0; z = 50 иметь бесконечно много оптимальных решений z = max(x 1 +x 2 |0.1x x 2 5, x 1 0, x 2 0) x 1 =50, x 2 =0; z = 50 … x 1 =0, x 2 =50; z = 50 Компактная запись

Задача в основной форме Задача ЛП в основной форме с m ограничениями и n переменными имеет следующий вид: Z = c 1 x 1 + c 2 x c n x n max при ограничениях a 11 x 1 + a 12 x a 1n x n = b 1 ; a 21 x 1 + a 22 x a 2n x n = b 2 ;... a m1 x 1 + a m2 x a mn x n = b m ; x 1 0; x 2 0;...; x n 0 b 1 0; b 2 0;...; b m 0 Задача с стандартной форме выражается через неравенства Преобразование системы ограничений - Балансовая переменная

Пример задачи ЛП Оптимизация размещения побочного производства лесничества Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна тысяча новогодних елей принесет прибыль в 2,5 тыс. руб., один бычок - 5 тыс. руб.

Постановка задачи 1. В качестве показателя эффективности целесообразно взять прибыль за операцию (годовую прибыль с земли в рублях). 2. В качестве управляемых переменных задачи следует взять: x 1 - количество откармливаемых бычков в год; x 2 - количество выращиваемых партий быстрорастущих новогодних елей по 1000 шт. каждая в год. 3. Целевая функция: 5000 x x 2 max, где чистый доход от одного бычка, руб.; чистый доход от одной партии деревьев (1000 шт. по 2,5 руб.). 4. Ограничения: 4.1. По использованию земли, га:4 x 1 + 1,5 x По бюджету, руб.:1200 x x По трудовым ресурсам, ч:20 x x Обязательства по контракту, шт.:x Ограничения: x 2 0

Графическое решение задачи ЛП

Отображая на графике прямые, соответствующие следующим уравнениям, 4 x 1 + 1,5 x 2 = x x 2 = x x 2 = 200 x 1 = 2 x 2 = 0 заштриховываем область, в точках которой выполняются все ограничения. Каждая такая точка называется допустимым решением, а множество всех допустимых решений называется допустимой областью. Очевидно, что решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области, которое, в свою очередь, называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, максимизирующее функцию W=5000 x x 2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП.

Графическое решение задачи ЛП Перебор всех угловых точек области допустимых решений приводит к нахождению максимального дохода в размере 34 тыс. руб. (W=5000x x 2 ), которое лесничество может извлечь, выращивая 3,6 бычка и 6,4 партии новогодних елей. Целочисленные методы (например, перебор) дают x 1 =3 и x 2 =6, что приводит к доходу в 30 тыс. руб., x 1 =4 и x 2 =5 приводит к более оптимальному результату в 32,5 тыс. руб., точка x 1 =3 и x 2 =7 приводит к аналогичному результату. Графический метод ввиду большой размерности реальных практических задач ЛП достаточно редко применяется, однако он позволяет ясно уяснить одно из основных свойств ЛП - если в задаче ЛП существует оптимальное решение, то по крайней мере одна из вершин допустимой области представляет собой оптимальное решение. Несмотря на то, что допустимая область задачи ЛП состоит из бесконечного числа точек, оптимальное решение всегда можно найти путем целенаправленного перебора конечного числа ее вершин. Рассматриваемый далее симплекс-метод решения задачи ЛП основывается на этом фундаментальном свойстве.

Решить графически задачу ЛП

Основные понятия Система m –линейных уравнений с n – неизвестными Базисные неизвестные Свободные неизвестные Каноническая линейная система Базисное решение системы Опорное решение системы

МЕТОД ЖОРДАНА – ГАУССА Алгоритм решения на основе создания таблиц 1. каждая последовательная итерация начинается с выбора разрешающего элемента, отличного от нуля, в предыдущей таблице (удобно в качестве разрешающего элемента выбирать элемент, равный 1); 2. элементы разрешающей строки делим на разрешающий элемент; 3. элементы разрешающего столбца, не принадлежащие разрешающей строке, заполняем нулями;

МЕТОД ЖОРДАНА – ГАУССА

Решить систему методом Жордана - Гаусса