К главной странице 2 части

  1. Основная задача линейного программирования
  2. Задача об использовании сырья
  3. Задача об использовании мощностей оборудования
  4. Транспортная задача
  5. Задача о питании
  6. Основная задача линейного программирования с ограничениями-неравенствами
  7. Применение MAPLE к решению задач линейного программирования

Основная задача линейного программирования

 Задана система
a11x1 + … + a1nxn = b1
a21x1 + … + a2nxn = b2
…
am1x1 + … + amnxn = bm
(1)
m линейных алгебраических уравнений с n неизвестными x1, …, xn и линейная форма
F = c1 x1 + … + cn xn + с0   (2)
относительно этих же неизвестных.
 Требуется среди всех неотрицательных решений заданной системы (1) выбрать такое, при котором форма F принимает наименьшее значение (минимизируется).
 О п р е д е л е н и е 1. Система (1) называется системой ограничений данной задачи.
 З а м е ч а н и е 1. В ряде задач неизвестные x1, …,хn должны удовлетворять не только равенствам, но и неравенствам. Эти неравенства также называются ограничениями задачи.
 З а м е ч а н и е 2. Ограничения равенства (1) не исчерпывают всех ограничений основной задачи, потому что переменные x1, …, xn обязаны удовлетворять условиям неотрицательности

x1 ≥ 0, …, xn ≥ 0.

 О п р е д е л е н и е 2. Всякое неотрицательное решение x01, …, x0n (x0i ≥ 0, i = 1, … , n) системы (1) назовем допустимым.
 О п р е д е л е н и е 3. Допустимое решение системы (1), минимизирующее форму F, назовем оптимальным.
 З а м е ч а н и е 3. Как правило, оптимальное решение единственно. Однако, возможны случаи, когда оптимальных решений оказывается бесчисленное множество.
 Обратимся теперь к изучению системы ограничений (1). Задача имеет смысл лишь в том случае, когда система (1) совместна, т. е. когда (согласно теореме Кронекера – Капелли) ранги основной и расширенной матриц системы совпадают. Как известно из линейной алгебры, этот общий ранг r не может превосходить числа n неизвестных. При r = n решение x01, …, x0n системы (1) единственно находится, например, по теореме Крамера. Если это решение допустимо (x0i ≥ 0, i = 1, … , n), то оно, очевидно, и является оптимальным (так как никаких других решений вообще нет). Если же среди чисел x0i имеется хотя бы одно отрицательное, то задача не имеет решения. В самом деле, оптимального решения не существует потому, что оно по самому определению должно быть неотрицательным, а единственное имеющееся решение таковым не является.
 Таким образом, интерес представляет лишь случай r < n, и только он будет нами рассматриваться в дальнейшем.
 Для сведения задач к основной задаче линейного программирования нужно уметь сводить вопрос о максимизации формы к вопросу о минимизации и переходить от ограничений, заданных в виде неравенств, к некоторым им эквивалентным ограничениям - равенствам.
 Покажем, как это сделать.
 1) Очевидно, что форма F достигает наибольшей величины при тех же самых значениях неизвестных x1, …, xn, при которых форма F1 = − F достигает наименьшей величины. Следовательно, максимизация формы F равносильна минимизации формы F1 = − F . Тем самым задача максимизации сводится к задаче минимизации.
 З а м е ч а н и е 4. Наибольшее значение формы F равно наименьшему значению формы F1, взятому с обратным знаком.
 2) Допустим что среди ограничений задачи имеется некоторое неравенство. Его всегда можно записать в виде

α1 x1 + α2 x2 + … + αn xn + β ≥ 0.   (3)

Введем новую, так называемую добавочную, неизвестную, связанную с неизвестными x1, …, xn уравнением

xn+1 = α1 x1 + α2 x2 + … + αn xn + β.   (4)

Очевидно, что условие неотрицательности величины xn+1 эквивалентно выполнимости неравенства (3). Иными словами, если система x01, …, x0n, x0(n+1) неотрицательных значений переменных x1, …, xn, xn+1 удовлетворяет уравнению (4), то система x01, …, x0n удовлетворяет неравенству (3). И обратно, если величины x01, …, x0n неотрицательны и удовлетворяют неравенству (3), то величина

x0(n+1) = α1 x01 + α2 x02 + … + αn x0n + β,

найденная из уравнения (4), окажется неотрицательной.
 Итак, ограничение-неравенство xn+1 ≥ 0 эквивалентно ограничению-неравенству (3). Ценою введения в задачу добавочных неизвестных удается все ограничения-неравенства заменить ограничениями-равенствами. При этом число добавочных неизвестных равно числу ограничений-неравенств в исходной задаче.
 Приемы 1) и 2) указывают конкретные пути перехода от различных частных задач к основной задаче линейного программирования.

Задача об использовании сырья

 Предположим, что изготовление продукции двух видов П1 и П2 требует использования четырех видов сырья S1, S2, S3, S4. Запасы сырья каждого вида ограничены и составляют соответственно b1, b2, b3, b4 условных единиц. Количество единиц сырья, необходимое для изготовления единицы каждого из видов продукции, известно и задается таблицей 1.

 

Т а б л и ц а 1
Виды сырья Запасы сырья Виды продукции
П1 П2
S1 b1 a11 a12
S2 b2 a21 a22
S3 b3 a31 a32
S4 b4 a41 a42
Доход c1 c2
Т а б л и ц а 2
Виды сырья Запасы сырья Виды продукции
П1 П2
S1 19 2 3
S2 13 2 1
S3 15 0 3
S4 18 3 0
Доход 7 5
 Здесь aij,(i = l, …, 4; j = 1, 2) означает количество единиц сырья вида Si необходимое для изготовления продукции вида Пj. В последней строке таблицы указан доход, получаемый предприятием от реализации одной единицы каждого вида продукции.
 Требуется составить такой план выпуска продукции видов П1 и П2 , при котором доход предприятия от реализации всей продукции оказался бы максимальным.
 Математическую форму поставленной задачи изучим на следующем числовом примере (см. таблицу 2). Допустим, что предприятие выпускает х1 единиц продукции вида П1, и x2 единиц продукции вида П2. Для этого потребуется 2 х1 + 3 x2 единиц сырья S1 (см. таблицу 2). Так как в наличии имеется всего 19 единиц сырья S1 то должно выполняться неравенство
2 х1 + 3 x2 ≤ 19.
 Неравенство (а не точное равенство) появляется в связи с тем, что максимальный доход может быть достигнут предприятием и в том случае, когда запасы сырья вида S1 используются не полностью.
 Аналогичные рассуждения, проведенные для остальных видов сырья, позволяют записать следующие неравенства:
2 х1 + 3 x2 ≤ 19( сырьё S1)
2 х1 + x2 ≤ 13 ( сырьё S2)
3 x2 ≤ 15 ( сырьё S3)
3 x1 ≤ 18 ( сырьё S4)
 При этих условиях доход F, получаемый предприятием, составит
F = 7 х1 + 5 x2.
 Таким образом, математически задачу можно сформулировать так.
 Дана система
2 х1 + 3 x2 ≤ 19
2 х1 + x2 ≤ 13
3 x2 ≤ 15
3 x1 ≤ 18
(5)
четырех линейных неравенств и линейная форма
F = 7 х1 + 5 x2. (6)
Требуется среди неотрицательных решений системы (5) выбрать такое, при котором форма F принимает наибольшее значение (максимизируется).
 Если все члены неравенств системы (5) ограничений этой задачи перенести в правую часть, то они примут следующий вид:
0 ≤ 19 − 2x1 − 3x2,
0 ≤ 13 − 2x1 − x2,
0 ≤ 15 − 3x2,
0 ≤ 18 − 3x1.
(7)
Введем четыре добавочные неизвестные x3, x4, x5, x6 и перейдем к новой системе ограничений-равенств:
x3 = 19 − 2x1 − 3x2,
x4 = 13 − 2x1 − x2,
x5 = 15 − 3x2,
x6 = 18 − 3x1
(8)
Согласно приему 1) вместо максимизации формы F = 7 х1 + 5 x2 будем минимизировать форму F1 = −F = −7 х1 − 5 x2. А это и есть основная задача линейного программирования.
 Выпишем матрицу I системы (8):
Ранг ее r = 4, так как минор, составленный из четырех последних столбцов, не равен нулю. Ранг r рассмотренной матрицы I не может быть больше 4 (матрица I имеет лишь четыре строки). Таким образом, r = 4 , n = 6, a k = n - r =2.
 Согласно общей схеме теперь следует выразить четыре неизвестные через оставшиеся две. Из системы (8) видно, что четыре последние неизвестные х3, х4, х5, х6 уже выражены через первые неизвестные х1, х2. Отметим, что форма F1 также выражена через х1 и х2. Потребовав неотрицательности всех неизвестных, мы приходим к системе неравенств
x1 ≥ 0,
x2 ≥ 0,
19 − 2x1 − 3x2 ≥ 0,
13 − 2x1 − x2 ≥ 0,
15 − 3x2 ≥ 0,
18 − 3x1 ≥ 0.
(9)
Тем самым задача 1 приобрела математическую форму задачи (А).
 Следует, оставив вначале в стороне ограничения-неравенства, преобразовать отдельно ограничения-равенства, а именно: выбрать в них те неизвестные, которые можно принять за свободные, и выразить через них остальные (несвободные). Далее, в исходные ограничения-неравенства и форму вместо несвободных неизвестных следует подставить их выражения через свободные. Теперь остается лишь систему полученных неравенств пополнить неравенствами, выражающими неотрицательность всех неизвестных (как свободных, так и несвободных), В итоге мы придем к задаче (А).
 Для наглядности применим геометрический метод решения
x1 ≥ 0,
x2 ≥ 0,
19 − 2x1 − 3x2 ≥ 0,
13 − 2x1 − x2 ≥ 0,
15 − 3x2 ≥ 0,
18 − 3x1 ≥ 0,
(10)

Fl = - 7хl - 5х2.

 Введем на плоскости прямоугольную декартову систему координат х1Оx2. Геометрическое место точек на плоскости, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многоугольник. Этот многоугольник называется многоугольником решений данной системы неравенств. Стороны этого многоугольника располагаются на прямых, уравнения которых получаются, если в неравенствах системы знаки неравенств заменить на точные равенства. А сам этот многоугольник есть пересечение полуплоскостей, на которые делит плоскость каждая из указанных прямых. В нашем случае такими прямыми являются
x1 = 0,  (I)
x2 = 0,  (II)
19 − 2x1 − 3x2 = 0,  (III)
13 − 2x1 − x2 = 0,  (IV)
15 − 3x2 = 0,  (V)
18 − 3x1 = 0,  (VI)
 Вычертим эти прямые (рис. 1);

Рис. 1.
стрелки указывают, какие полуплоскости в пересечении дают многоугольник решений. Наряду с этим рассмотрим форму Fl = - 7хl - 5х2. Она является линейной функцией координат (x1, x2) точки на плоскости. Как располагаются на плоскости те точки, в которых форма Fl принимает одно и то же значение С ? Приравняем форму Fl константе С и рассмотрим полученное уравнение

- 7хl - 5х2 = C  (11)

Это уравнение определяет на плоскости некоторую прямую. Она является искомым геометрическим местом точек, в которых Fl принимает данное значение С. Меняя значение С, получаем различные прямые. Все они параллельны между собой, т. е. образуют семейство параллельных прямых. Через каждую точку плоскости проходит одна прямая этого семейства. Каждую из прямых семейства (11) принято называть линией уровня (линией равных значений) формы Fl. При переходе от одной прямой к другой значение формы Fl изменяется. На рисунке 2 показаны прямые, отвечающие значениям С = - 17,5; - 35; - 52,5.

Рис. 2.
Вектор g указывает направление, двигаясь в котором мы переходим от больших значений формы к меньшим.
 Из курса аналитической геометрии известно, что коэффициенты при переменных в уравнении прямой являются проекциями вектора n, перпендикулярного к прямой. В нашем случае n = (- 7; - 5). Мы наблюдаем, что направление убывания формы F1 противоположно направлению вектора n.
 Обратимся вновь к рис. 1. Рассмотрим любую точку P0 ( x01, x02) многоугольника решений. Через эту точку проходит прямая семейства (23). Вдоль всей этой прямой форма F1 принимает такое же значение, как и в точке P0 , т. е. C0 = - 7 x01 - 5 x02.
 На рис. 1 пунктиром показана прямая, отвечающая значению С = - 35. Очевидно, что точка Р0 не соответствует оптимальному решению задачи. Действительно, внутри многоугольника решений можно найти точки, отвечающие значениям формы меньшим, чем C0. Для этого достаточно перейти в направлении вектора g от прямой C0 к другой, ей параллельной прямой семейства (11), все еще пересекающей многоугольник решений. Теперь должно быть ясным, что оптимальное решение определится точкой Q (5, 3), а наименьшее значение формы F1 равно

F1 min = - 7·5 - 5·3 = - 50 .

Итак, оптимальное решение задачи 1 найдено:

х1 = 5, х2 = 3.

 Если вспомнить условие этой задачи, то для наиболее рационального плана использования сырья, гарантирующего предприятию наибольший доход, следует выпускать 5 единиц продукции вида П1 и 3 единицы вида П2, причем максимальный доход составит Fmax = 50. Отметим, что при этом сырье видов S1 и S2 используется полностью, а S3 и S4 – не полностью. (В этом можно убедиться, подсчитав расход сырья при найденном плане выпуска продукции: х1 = 5 , х2 =3.)
  З а м е ч а н и е 5. Как известно, задача нахождения экстремальных точек функции рассматривается в курсе математического анализа. Там она решается методами дифференциального исчисления. Почему же, спрашивается, нельзя использовать эти методы для решения задач линейного программирования? Дело в том, что методы дифференциального исчисления позволяют определять только такие экстремальные точки, которые находятся строго внутри рассматриваемой области, а не на границе ее. В задачах же линейного программирования оптимальное значение формы достигается всегда на границе многоугольника решений, как, например, в задаче 1. Вот почему методы дифференциального исчисления неприменимы для решения таких задач.

Задача об использовании мощностей оборудования

 Предположим, что предприятию задан план производства по времени и номенклатуре: требуется за время Т выпустить Nl единиц продукции вида П1 и N2 вида П2. Каждый из видов продукции может производиться двумя машинами А и В с различными мощностями. Эти мощности заданы таблицей 3. Здесь а1 есть количество единиц продукции вида П1 произведенной машиной А в единицу времени. Аналогичный смысл имеют и остальные данные из этой таблицы.
Таблица 3
  П1 П2
A a1 a2
B b1 b2
Таблица 4
  П1 П2
A α1 α2
B β1 β2
Таблица 5
  П1 П2
A x1 x2
B x3 x4
 Расходы, вызванные изготовлением каждого из видов продукции на той или иной машине, различны и задаются таблицей 4. В этой таблице α1 выражает цену единицы рабочего времени машины А при изготовлении продукции вида П1. Смысл остальных величин α2, β1, β2 аналогичен.
 Требуется составить оптимальный (наиболее рациональный) план работы машин, а именно найти, сколько времени каждая из машин А и В должна быть занята изготовлением каждого из видов продукции П1 и П2 с тем, чтобы стоимость всей продукции предприятия оказалась минимальной и в то же время был бы выполнен заданный план как по времени, так и по номенклатуре.
 Найдем математическую формулировку поставленной задачи. Введем для неизвестных нам времен работы машин по изготовлению продукции следующие обозначения (таблица 5). Здесь, например, х1 означает время работы машины А по изготовлению продукции П1. Аналогичный смысл имеют величины х2, х3, х4.
 Поскольку машины А и В работают одновременно, то выполнение плана по времени будет обеспечиваться неравенствами
х1 + х2 ≤ T,
х3 + х4 ≤ T.
 Левые части этих неравенств означают общие времена работы соответственно машин А и В. Неравенства (а не точные равенства) возникают потому, что даже при обеспечении плана по номенклатуре машины не обязаны работать все отведенное им по плану время Т. (Здесь могут оказаться возможности для перевыполнения плана по времени.)
 Изготовлением продукции П1 машина А занята х1 единиц времени. При этом за единицу времени она производит a1 единиц продукции этого вида. Следовательно, всего машина А изготовит а1х1 единиц продукции П1. Аналогично машина В изготовит b1х3 единиц продукции вида П1 . Поэтому для обеспечения плана по номенклатуре должно выполняться равенство
а1х1 + b1х3 = N1.
 Точно так же для обеспечения плана выпуска продукции вида П2 необходимо удовлетворить равенство
а2х2 + b2х4 = N2.
 Далее, из условий задачи вытекает, что общая стоимость всей продукции составит
F = α1x1 + α2x2 + β1x3 + β2x4.
 В итоге мы приходим к следующей математической задаче.
 Задана система
х1 + х2 ≤ T
х3 + х4 ≤ T
а1х1 + b1х3 = N1
а2х2 + b2х4 = N2
(12)
двух линейных неравенств и двух линейных уравнений и задана линейная форма
F = α1x1 + α2x2 + β1x3 + β2x4. (13)
 Требуется среди всех неотрицательных решений системы (12) найти такое, при котором форма F принимает наименьшее значение (минимизируется).
 Отметим один из важных вариантов поставленной задачи. Потребуем, чтобы машины А и В работали все время Т, отведенное им по плану. Тогда неравенства
х1 + х2 ≤ T,
х3 + х4 ≤ T.
превратятся в равенства. В то же время два последних равенства из системы (3) превратятся, вообще говоря, в неравенства
а1х1 + b1х3 ≥ N1,
а2х2 + b2х4 ≥ N2 ,
так как, работая все время Т, машины могут не только выполнить, но и перевыполнить план по номенклатуре. При этом требование минимизации стоимости не будет противоречить выполнению или, быть может, перевыполнению плана по номенклатуре.
 Перепишем систему (12) ограничений этой задачи в виде
0 ≤ T − x1 − x2,
0 ≤ T − x3 − x4,
a1x1 + b1x2 = N1,
a2x2 + b2x4 = N2.
(14)
Введем добавочные неизвестные х5 , x6 и перейдем к системе ограничений-равенств
х5 = T − x1 − x2,
x6 = T − x3 − x4,
a1x1 + b1x2 = N1,
a2x2 + b2x4 = N2.
(15)
Среди неотрицательных решений системы (15) следует выбрать оптимальное для формы F = α1x1 + α2x2 + β1x3 + β2x4.
 Конкретизируем задачу, придав величинам из (12) и (13), которые должны быть известны по условию задачи, следующие числовые значения: а1 = 6, а2 = 24, b1 = 13, b2 = 13, N1 =30, N2 = 96, T = 6, α1 =4, α2 = 47, β1 = 13, β2 = 26.
 Тогда система ограничений и форма F примут вид
x1 + x2 ≤ 6   (16)
x3 + x4 ≤ 6
6 x1 + 13 x3 = 30
24 x2 + 13 x4 = 96
F = 4 x1 + 47 x2 + 13 x3 + 26 x4
Оставив пока в стороне первые два ограничения-неравенства, выразим из ограничений-равенств x3 и x4 через x1 и x2 (неизвестные x1 и x2 в нашей задаче мы выбираем в качестве свободных):
 (16)
Далее, подставим в левую часть исходных ограничений-неравенств и в форму F выражения несвободных неизвестных через свободные, в результате чего получим
,

F = 4 x1 + 47 x2 + 30 - 6 х1 + 2 (96 - 24 х2 )

или, после обычных алгебраических преобразований, имеем

x1 + 4 x2 ≥ 8,
F = 222 - 2 x1 - x2.

Требование неотрицательности х3 и х4 эквивалентно неравенствам

30 - 6 x1 ≥ 0,
96 - 24 x2 ≥ 0.

которые после элементарных преобразований дают

x1 ≤ 5, x2 ≤ 4.

Учитывая теперь исходное неравенство x1 + x2 ≤ 6 и неотрицательность всех величин, получим следующую систему ограничений - неравенств:
х1 ≥ 0,
х2 ≥ 0,
х1 ≤ 5,
х2 ≤ 4,
х1 + х2 ≤ 6,
х1 + 4 х2 ≥ 8.
(17)
При этом минимизируемая форма имеет вид

F = 222 - 2 x1 - x2. (18)

Тем самым задача 2 оказалась сведенной к задаче (А).
 Дадим геометрическое истолкование и найдем решение задачи 2. После приведения ее к задаче (А) получили следующие ограничения и форму
х1 ≥ 0, (I)
х2 ≥ 0, (II)
х1 ≤ 5, (III)
х2 ≤ 4, (IV)
х1 + х2 ≤ 6, (V)
х1 + 4 х2 ≥ 8. (VI)
(19)
При этом минимизируемая форма имеет вид

F = 222 - 2 x1 - x2. (20)

 Введем на плоскости систему координат x1Ox2 и вычертим многоугольник решений системы (19) подобно тому, как это сделано в задаче 1. Для этого заменим все неравенства из (19) равенствами и построим соответствующие прямые (рис. 3).

Рис. 3.
 На этом же рисунке построена одна из линий уровня формы (20), отвечающая значению F = 219. Вектор g указывает направление убывания F.
 Из чертежа видно, что наименьшее значение F на многоугольнике решений достигается в точке М(5, 1) пересечения прямых (III) и (V). Минимальное значение формы при х1 = 5, х2 = 1 находится из (20):

F = 222 - 2·5 - 1 = 211.

 Каков же экономический смысл полученного решения? Напомним, что величины xi(i = 1, 2,3,4) означают времена работы машин А и В по изготовлению продукции П1 и П2. Величины х1 = 5 и х2 = 1 нами уже найдены, а величины х3 и x4 находим из уравнений (16):
 Таким образом, задача решена полностью.


Транспортная задача

 На двух станциях отправления A1 и A2 сосредоточено соответственно a1 и a2 единиц некоторого однородного груза. Этот груз следует доставить в три пункта назначения B1, B2, B3, причем в каждый из них должно быть завезено соответственно b1, b2, b3 единиц этого груза. Стоимость перевозки единицы груза из пункта Ai в пункт Bj (равную сij) считаем заданной. Все данные представляем в таблице 6.

Таблица 6

Пункты назначения

Пункты отправления

 Пункты назначения Запасы груза
B1 B2 B3
A1 с11 с12 с13 a1
A2 с21 с22 с33 a2
Потребность в грузе b1 b2 b3 Σai = Σbj
 Общий запас грузов на станциях отправления равен суммарной потребности в этом грузе всех станций назначения
a1 + a2 = b1 + b2 + b3. (21)
 Требуется составить такой план перевозок, при котором их общая стоимость была бы наименьшей.
 Обозначим через xij количество единиц груза, предназначенного к отправке из пункта Ai в пункт Bj. Тогда количество груза, который планируется к доставке в пункт B1 из пунктов А1 и А2, составит
x11 + x21.
Но так как потребность в грузе в пункте B1 равна b1, то должно выполняться равенство
x11 + x21 = b1.
Аналогичные рассуждения приводят к равенствам
x12 + x22 = b2,
x13 + x23 = b3.
 С другой стороны, общее количество груза, отправленного со станции А1, выражается суммой
x11 + x12 + x13,
которая, очевидно, обязана совпадать с запасом а1, груза, сосредоточенным на этой станции, т. е.
x11 + x12 + x13 = а1.
Подобно этому

x21 + x22 + x23 = а2.

 Полученные соотношения легче запомнить, если все величины свести в таблицу 7 (матрицу перевозок).

Таблица 7

Пункты назначения

Пункты отправления

 Пункты назначения Запасы груза
B1 B2 B3
A1 x11 x12 x13 a1
A2 x21 x22 x33 a2
Потребность в грузе b1 b2 b3  
Тогда легко проверить, что сумма всех xij, расположенных в i - й строке, равна запасу ai в пункте назначения Ai. Сумма же всех xij из столбца j равна потребности bj пункта назначения Bj.
 Из условий задачи с очевидностью вытекает, что общая стоимость F всех перевозок равна

F = c11 x11 + c12 x12 + c13 x13 + c21 x21 + c22 x22 + c23 x23 = Σ cij xij

 Таким образом, математическая формулировка транспортной задачи (по критерию стоимости перевозок) такова.
 Задана система
x11 + x21 = b1
x12 + x22 = b2
x13 + x23 = b3
x11 + x12 + x13 = а1
x21 + x22 + x23 = а2
(22)
пяти линейных алгебраических уравнений с шестью неизвестными и линейная форма

F = Σ cij xij (23)

 Требуется среди всех неотрицательных решений xij системы (6) выбрать такое, при котором форма F минимизируется (достигает наименьшего значения).
 Отметим, что при решении транспортной задачи следует учитывать важное соотношение

Σ ai = Σ bj, (22 ')

вытекающего из самого условия задачи.
 Впрочем, возможны и иные постановки транспортной задачи, когда условие (22 ') не выполнено. Однако мы их оставляем здесь без рассмотрения.
 Для определенности придадим известным по условию задачи величинам некоторые числовые значения и сведем их в таблицу 6.
Таблица 6
  B1 B2 B2 Запасы
A1 4 9 3 20
A2 4 8 1 30
Потребности 10 30 10 50
Тогда система ограничений (22) и форма F примут вид:
x11 + x21 = 10,
x12 + x22 = 30,
x13 + x23 = 10,
x11 + x12 + x13 = 20,
x21 + x22 + x23 = 30.
(23)

F = 4 x11 + 9 x12 + 3 x13 + 4 x21 + 8 x22 + x23 (24)

Выпишем матрицу системы:
(под xij выписаны коэффициенты, с которыми эти неизвестные входят в соответствующие уравнения). Подсчитаем ранг r этой матрицы. Для этого прибавим к первой строке вторую и третью и вычтем четвертую и пятую; получим строчку из одних нулей. Поэтому r < 5. Легко обнаружить, что минор этой матрицы, образованный первыми четырьмя строчками и столбцами, отличен от нуля. Следовательно, r =4. Подсчитаем теперь ранг r ' расширенной матрицы:
Если и в этой матрице к первой строке прибавить вторую и третью, затем вычесть четвертую и пятую, то вновь получим строчку из одних нулей. Поэтому r ' < 5, но так как ранг расширенной матрицы не меньше ранга основной, то r ' =4.
 З а м е ч а н и е 6. Если выполнено условие

Σai = Σbj, (25)

выражающее равенство суммарных запасов груза в пунктах отправления суммарным потребностям пунктов назначения, то система (23) всегда совместна. Действительно, если отвлечься от стоимости перевозок (т. е. не добиваться минимизации формы F), то совершенно очевидно, что существует бесчисленное множество способов организовать требуемые перевозки. Более того, если проследить, как только что определялся ранг расширенной матрицы, то можно убедиться, что появление нуля в первой строке и последнем столбце этой матрицы явилось следствием условия (25):

20 + 30 = 10 + 30 + 10.

 Итак, ранг системы r = 4, общее число неизвестных n = 6, значит, число свободных неизвестных k = n - r = 2.
 Примем в качестве свободных неизвестных x11 и x12. Выражая из (23) остальные неизвестные через свободные, получим
х12 = 20 - х11 - x12,
х21 = 10 - х11,
х22 = 30 - х12,
х23 = - 10 + х11 + x12.
(26)
Форма F при заданной выше матрице стоимости равна

F = 4 x11 + 9 x12 + 3 x13 + 4 x21 + 8 x22 + x23,

а после подстановки выражений несвободных неизвестных через свободные примет вид

F = 330 - 2 x11 - x12.

Наконец, для придания задаче 3 формы задачи (А) следует записать требование неотрицательности всех неизвестных xij:
20 - х11 - x12 ≥ 0,
10 - х11 ≥ 0,
30 - х12 ≥ 0,
- 10 + х11 + x12 ≥ 0,
x11 ≥ 0,
x12 ≥ 0
(27)

 Перейдем к геометрическому толкованию и заодно решим задачу 3. Ограничения и минимизируемая форма этой задачи таковы:
20 - х11 - x12 ≥ 0, (I)
10 - х11 ≥ 0, (II)
30 - х12 ≥ 0, (III)
- 10 + х11 + x12 ≥ 0, (IV)
x11 ≥ 0, (V)
x12 ≥ 0, (VI)
(28)

F = 330 - 2 x11 - x12.

 Введем систему координат на плоскости. На этот раз оси обозначим x11 и х12. Вычертим многоугольник решений и одну из линий уровня формы F.
 Оптимальное решение дается точкой N(10; 10). Итак, x11 = 10, x12 = 10, Fmin = 300.
 Остальные значения xij находятся из уравнений (26):

Задача о питании

 Для сохранения здоровья и работоспособности человек должен потреблять в сутки некоторое количество питательных веществ, например белков, жиров, углеводов, воды и витаминов. Запасы этих ингредиентов в различных видах πi ( i = 1, 2, … ) пищи различны. Ограничимся, простоты ради, двумя видами пищи и зададим таблицу 8, в которой, например, число а11 указывает на запасы жиров в пище вида π1. Смысл остальных чисел aij аналогичен.
Питательные вещества Норма Виды пищи
n1 n2
B1 –жиры b1 a11 a12
B2 –белки b2 a21 a12
B3 –углеводы b3 a31 a13
B4 –вода b4 a41 a14
B5 –витамины b5 a51 a15
Стоимость   c1 c2
 Предположим, далее, что стоимость некоторой единицы пищи вида πi составляет сi. Требуется так организовать питание, чтобы стоимость его была наименьшей, но организм получил бы не менее минимальной суточной нормы питательных веществ всех видов Bi (i = 1, 2, … , 5).
 Пусть x1 и х2 „ количество пищи видов π1 и π2, приобретаемых человеком (подразумевается, что вся приобретаемая пища потребляется). В этом случае общие запасы жиров в двух видах пищи составляют

a11 x1 + a12 x2

и не должны быть меньше минимальной нормы b1. Это требование приводит к неравенству

a11 x1 + a12 x2 ≥ b1.

 Знак неравенства (а не точного равенства) возникает потому, что при выбранной системе питания в приобретенной пище жиров может оказаться и больше минимальной нормы. Аналогичные рассуждения приводят еще к четырем неравенствам:

a21 x1 + a22 x2 ≥ b2,
a31 x1 + a32 x2 ≥ b3,
a41 x1 + a42 x2 ≥ b4,
a51 x1 + a52 x2 ≥ b5.

При этом общая стоимость F питания равна
F = c1 x1 + c2 x2
Итак, мы пришли к следующей математической задаче.
 Задана система

ai1 x1 + ai2 x2 ≥ bi (i = 1, …, 5)  (29)

пяти линейных неравенств с двумя неизвестными x1, x2 и линейная форма
F = c1 x1 + c2 x2 (30)
относительно этих же неизвестных.
 Требуется среди всех неотрицательных решений системы (8) найти такое, которое сообщает форме F наименьшее значение (минимизирует F).

Основная задача линейного программирования с ограничениями-неравенствами

 Рассмотрим систему (1) ограничений-равенств основной задачи. Как было отмечено ввыше , имеет смысл лишь случай r < n (r — ранг системы, n — число неизвестных). Из линейной алгебры известно, что в этом случае r неизвестных линейно выражаются через остальные n - r = k неизвестных (эти последние принято называть свободными). Всегда можно занумеровать неизвестные так, чтобы последние xk+1, … , xn выразились через первые x1, …, xk (поскольку n = k + r, то неизвестных xk+1, … , xn в точности r штук).
xk+1 = α11 x1 + α12 x2 + … + α1k xk + β1,
xk+2 = α21 x1 + α22 x2 + … + α2k xk + β2,
…
xn = αr1 x1 + αr2 x2 + … + αrk xk + βr.
(31)
Система (31) эквивалентна системе (1).
 Если теперь вместо величин xk+1, … , xn в выражении (31) для формы F подставить их значения из (17), то форма F примет другой вид:
F = γ1 x1 + … + γn xk + γ0   (32)
т. е. по-прежнему остается линейной, но выразится только через свободные неизвестные x1, …, xk.
 Решая основную задачу, ограничимся лишь неотрицательными (допустимыми) решениями системы (31). Поэтому с необходимостью должны выполняться неравенства

xi ≥ 0 (i = 1, 2, …, n). (33)

Если при этом учесть равенства (33), то получаем для i = k + 1, k + 2 , …, n неравенства
0 ≤ α11 x1 + α12 x2 + … + α1k xk + β1,
0 ≤ α21 x1 + α22 x2 + … + α2k xk + β2,
…
0 ≤ αr1 x1 + αr2 x2 + … + αrk xk + βr.
Для свободных неизвестных xi (i = 1, 2, …, k) неравенства (20). Приходим к системе
x1 ≥ 0,
…
xk ≥ 0,
α11 x1 + α12 x2 + … + α1k xk + β1 ≥ 0,
…
αr1 x1 + αr2 x2 + … + αrk xk + βr ≥ 0.
(34)
содержащей n линейных неравенств относительно k неизвестных. Каждому допустимому (неотрицательному) решению системы (31) отвечает решение системы неравенств (34). И обратно, взяв произвольное решение x01, …, x0k системы (1) и найдя по формулам (31) величины

x0 (k+i) = αi1 x01 + αr2 x2 + … + αrk xk + βr

получим, очевидно, неотрицательное (допустимое) решение системы (31), а значит, и системы (1). Тем самым вместо того, чтобы искать неотрицательные (допустимые) решения системы равенств (1), можно искать все решения системы неравенств (31).
 В результате мы пришли к следующей математической задаче. Дана система (31), содержащая n линейных неравенств относительно k неизвестных x1, …, xk и линейная форма
F = γ1 x1 + … + γn xk + γ0   (35)
относительно тех же неизвестных.
 Требуется среди всех решений системы (31) выбрать такое, при котором форма F достигает наименьшего значения. Решение системы неравенств (21), сообщающее форме F наименьшее значение, назовем, как и прежде, оптимальным.
 Из хода наших рассуждений очевидно, что основная задача линейного программирования эквивалентна только что сформулированной задаче. Эту задачу естественно называть основной задачей линейного программирования с ограничениями-неравенствами. Краткости ради, назовем ее основной задачей в форме (А) или просто задачей (А).

Применение MAPLE к решению задач линейного программирования

> with(simplex):
>A := linalg[matrix](4, 2, [2, 3, 2, 1, 0, 3, 0, 3]):
>B := [19, 13, 15, 18]:
>C := [-7, -5]:
>cond := {x1 >= 0, x2 >= 0, x1*A[1, 1]+x2*A[1, 2] <= B[1], x1*A[2, 1]+x2*A[2, 2] <= B[2], x1*A[3, 1]+x2*A[3, 2] <= B[3], x1*A[4, 1]+x2*A[4, 2] <= B[4]}:
>F := x1*C[1]+x2*C[2]:
>minimize(F, cond):

{x1=5,x2=3}