<<
>>

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

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

п

f(X) = 2 С ;Xj max(min); (7.2) y=i

І ayxj^bi, і el, 7cM = {l,2,...m}; (7.3) y=1

n

S aijxj -ty, ІЄМ; (7.4) y=i

Xj > 0, у є /,/сЛГ={1, 2, ..., л}. (7.5)

При этом система линейных уравнений (7.3) и неравенств (7.4), (7.5), определяющая допустимое множество решений задачи W, на-зывается системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией, или критерием оптимальности.

В частном случае, если / = 0, то система (7.3) — (7.4) состоит только из линейных неравенств, а если / = Л/, то — из линейных уравнений.

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

f(X)=%Cj-Xj^> min; (7.6)

y=i

п

ZauxJ=bi,i = l,m; (7.7)

у=1

6/ > 0;

Xj>0,j = T^i, (7.8)

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

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме.

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

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на —1;

если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

если некоторая переменная хк не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: хк = х?к — хь где ? — свободный индекс, х/к > 0, х? > 0.

Пример 7.1. Приведение к канонической форме задачи ли-нейного программирования:

min L = 2х{ + х2 — х3;

2х2 - х3 < 5; х\ + *2-х3>-1; 2хх — х2 < -3; хх < 0, х2 > 0, х3 > 0.

Решение

Введем в каждое уравнение системы ограничений выравнивающие переменные х4, х5, х6.

Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные х4, *б вводятся в левую часть со знаком «+», а во второе уравнение вводится х5 со знаком «—».

Итак:

2х2 — Х3 + х4 = 5;

Х\ "Ь х2 — х3 — х$ — — 1;

2Xj - х2 + х6 = - 3;

х4 >0, х5 > 0, х6 > 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на — 1:

2х2 — х3 Х4 = 5;

—Xj — Х2 Х3 Х5 = 1 \

—2xj + х2 — х^ = 3;

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

Xj = Х?1 - х7, где Xу! > 0, х7 > 0.

Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

2х2

-X7! -Х2

— х3 + х4 =5 + х3 + х5 + х7 = 1

—2х/1 + х2 — х6 + 2х7 =3; Lmm = 2х/1 + х2 - х3 - 2х7; x'j > 0; xf > 0, / = 2J.

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 7.1. Задачи линейного программирования:

  1. 2.1 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  2. 2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. 1.Метод линейного программирования.
  4. 7.1. Задачи линейного программирования
  5. 7.2. Построение экономико- математических моделей задач линейного программирования
  6. 7.3. Графическое решение задачи линейного программирования
  7. 7.6. Методы нахождения опорного решения задачи линейного программирования
  8. 7.7. Экономическая интерпретация решения задачи линейного программирования
  9. 7.8. Двойственные задачи линейного программирования
  10. Транспортные задачи линейного программирования
  11. 10.1. Геометрическая интерпретация задач нелинейного программирования
  12. 10.4. Многоцелевые задачи линейного программирования