Линейное программирование

Материал из Циклопедии
Перейти к: навигация, поиск
Лекция 1. Линейное программирование. Максим Бабенко // Лекториум [1:35:34]

Линейное программирование — это математический численный метод для оптимизации моделей, в которых целевые функции и ограничения строго являются уравнениями линейной алгебры.[1]:33 Модель линейного программирования включает целевую функцию, ограничения в виде линейных уравнений или неравенств и требование неотрицательности переменных.[2] Термин был предложен Дж. Данцигу Т. Купмансом в 1951 году[3]:13 Метод применим в военной и экономической логистике для оптимизации доставки грузов и технологических процессов. Был расширен и далее исследован в пору Второй Мировой войны и после.[3]:19-37

Содержание

[править] Целевая функция

[math]f(x)= c_1x_1 + c_2x_2 + ... + c_nx_n → min;[/math]

Если функцию требуется обратить не в минимум, а в максимум, достаточно изменить знак коэффициентов [math]c_i[/math] на противоположный[4]:329

[править] Ограничения

[math] \begin{cases} a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1, \\ a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b2, \\ ... \\ a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n = b_m; \end{cases} [/math]

Здесь a и b — постоянные числа, заданные условиями задачи.[2] Если по условиям задачи вместо равенств предполагаются неравенства, то для неравенства вида «≤» для преобразования его в равенство надо добавить дополнительную переменную [math]x_{n+1}[/math] или несколько таких переменных ([math]x_{n+2}[/math] и т.д. по числу неравенств). Аналогично, для неравенств вида «≥» дополнительную неотрицательную переменную [math]x_{n+i}[/math] следует вычесть (или, что то же самое, прибавить с коэффициентом –1).[5] [6]:34

[править] Требования неотрицательности переменных

Переменные x принимают неотрицательные значения: [math]x_j \ge 0[/math], [math]j = 1, …, n[/math].[2] Постоянные a, b и c, заданные условиями задачи, требований к неотрицательности не имеют (могут быть как положительными, так и отрицательными).

[править] Запись в табличной форме

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

Вид сырья Продукт 1 Продукт 2 Продукт 3 Продукт 4 Запасы сырья
Сырье 1 a11 = 4 кг a12 = 2 кг a13 = 1 кг a14 = 8 кг b1 ≤ 1200 кг
Сырье 2 a21 = 2 кг a22 = 10 кг a23 = 6 кг a24 = 0 кг b2 ≤ 600 кг
Сырье 3 a31 = 3 кг a32 = 0 кг a33 = 6 кг a34 = 1 кг b3 ≤ 1500 кг
Прибыль (руб.) c1 = 15 c2 = 6 c3 = 12 c4 = 24 max

Коэффициенты aij указывают, сколько сырья i уходит на изготовление одной единицы j-го продукта.

На выходе алгоритма расчета будут найдены переменные xj, которые соответствуют оптимальному выпуску продукции при указанных ограничениях.[7]:57

Другим типом задач является задача на минимизацию издержек при составлении диеты или откорме животных. Коэффициенты a показывают содержание вещества в фунтах на фунт ингредиента. [1]:174

Вид корма Известняк Зерно Соевая мука Ограничение
Кальций a11 = 0,380 a12 = 0,001 a13 = 0,002 b1 ≥ 8 и b1 ≤ 12%
Белок a21 = 0,00 a22 = 0,09 a23 = 0,50 b2 ≥ 22%
Клетчатка a31 = 0,00 a32 = 0,02 a33 = 0,08 b3 ≤ 5%
Стоимость (долл./фунт) c1 = 0,12 c2 = 0,45 c3 = 1,60 min

[править] Симплекс-метод

Является основным методом для решения задачи линейного программирования. Основан на том, что область точек пространства, удовлетворяющих линейным ограничениям, является многогранником, и максимум линейной функции должен достигаться в одной из вершин этого многогранника. На каждом шаге симплекс-метода происходит переход в соседнюю вершину с не худшим значением целевой функции. При компьютерной реализации алгоритма на вход нужно подать одномерный массив коэффициентов целевой функции c (его размерность совпадает с числом столбцов), двумерный массив коэффициентов системы ограничений a (размерность m×n), одномерный массив свободных членов (размерность совпадает с числом строк) и знак ограничений (=, >=, <=), а также способ оптимизации (на минимум или на максимум). На выходе программа найдет значения переменных x (одномерный массив с размерностью, равной числу столбцов).

[править] Смотрите также

[править] Источники

  1. 1,0 1,1 Таха Х. Введение в исследование операций 7-е изд. Вильямс, 2005, 903 стр.
  2. 2,0 2,1 2,2 http://emm.ostu.ru/lect/lect2.html
  3. 3,0 3,1 Данциг Д. Линейное программирование, его применения и обобщения (1966).
  4. Вентцель Е. С. Исследование операций. М:Советское радио, 1964
  5. http://www.mathelp.spb.ru/book1/lprog3.htm
  6. Барсов А. С. Что такое линейное программирование. М:1959
  7. Лунгу К. Н. Линейное программирование. Руководство к решению задач. — М.: Физматлит, 2005. — 128 с. — ISBN 5-9221-0631-7.
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты