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

Задача линейного программирования (ЛП) состоит в определении максимального (минимального) значения целевой функции:
(1.1)
При условиях :
(1.2)
(1.3)
где aij , bi , cj – заданные постоянные числа. Функция F(1) называется целевой функцией, выражения (2), (3) – ограничениями. Значения xj , удовлетворяющие ограничениям (2), (3) образуют область допустимых решений (ОДР) и называются допустимыми. Допустимое решение xj * , при которых целевая функция (1) принимает экстремальное значение, называется оптимальным. В зависимости от структуры выражений (1), (2), (3) для решения задачи ЛП могут применяться различные методы, которые рассмотрены ниже.
1.1. Графический метод решения задач ЛП.
Постановка задачи. Метод применяется в том случае, если количество переменных задачи ЛП (1), (2), (3) равно двум, т.е.:
(1.4)
(1.5)
(1.6)
Методика решения . Процесс решения задачи ЛП графическим методом включает следующие этапы:
1) На плоскости Х1 ОХ2 строятся граничные прямые, уравнения которых получают путем замены неравенств (5), (6) на строгие равенства
2) Находятся полуплоскости, определяемые каждым из ограничений (5), (6).
3) Определяется область допустимых решений ОДР задачи на плоскости Х1 ОХ2 . Если система ограничений (5), (6) несовместна, то задача ЛП не имеет решения.
4) Строится вектор
5) Строится прямая с1 х1 +с2 х2 = 0, перпендикулярная вектору и передвигается в направлении вектора (при поиске максимума целевой функции); в результате определяется точка А, принадлежащая ОДР, в которой целевая функция F принимает максимальное значение. Если ОДР не ограничена сверху, то задача ЛП не имеет решений.
6) Определяют координаты точки А – (х1 * ,х2 * ) и максимальное значение функции F* =с1 х1 * + с2 х2 * .
Пример. Решить задачу ЛП:
1. На плоскости Х1 ОХ2 строим уравнения прямых: х1 –х2 = 3; х1 + 2х2 = 4; х2 = 4; х1 =0; х2 =0
2. Для каждого из ограничений определяем допустимую полуплоскость и отмечаем ее стрелками. Например, условие при х1 =0; х2 =0 выполняется. Значит точка (0,0) лежит в допустимой полуплоскости.
3. Определяем допустимую область для всех ограничений задачи (ОДР). Это многоугольник ABCD.
4. Строим вектор .
5. Строим прямую F=2x1 +x2 = 0. Передвигая ее в направлении вектора , определяем крайнюю точку А, принадлежащую ОДР – это т. А. В т. А функция имеет максимальное значение. Минимальное значение целевая функция принимает в т.С.
6. Координаты т. А находятся путем решения системы
Аналогично определяются координаты точки минимума С:
Индивидуальные задания. Решить графическим методом.

Вариант 1.
F = x1 + x2 max
-3x1 + 2x2 ≤ 1
x1 + 2x2 ≤ 14
2x1 + x2 ≤ 13
3x1 – x2 ≤ 12
x1 , x2 ≥ 0
Вариант 2.
F = 3x1 + x2 min
3x1 + 5x2 ≥ 15
5x1 + 3x2 ≥ 15
x1 ≥ 1
x2 ≥ 1
x1 , x2 ≥ 0
Вариант 3.
F = 3x1 + 3x2 min
x1 + 4x2 ≥ 4
4x1 + x2 ≥ 4
x1 , x2 ≥ 0
Вариант 4.
F = 6x1 – 5x2 max
2x1 + 5x2 ≤ 10
5x1 + 2x2 ≤ 10
x1 , x2 ≥ 0
Вариант 5.
F = 8x1 + 2x2 max
x1 – 4x2 ≤ 4
–4x1 + x2 ≤ 4
x1 + x2 ≤ 6
x 1 , x 2 ≥ 0
Вариант 6.
F = 2x1 + 3x2 min
x1 + 5x2 ≥ 10
3x1 + 2x2 ≥ 12
2x1 + 4x2 ≥ 10
x1 ≥ 1
x1 , x2 ≥ 0
Вариант 7.
F = 5x1 + 4x2 + 6x3 max
x1 + x2 + x3 ≤ 6
2x1 + x2 + x3 ≥ 9
3x1 + x2 +2x3 ≥ 11
x1 , x2 , x3 ≥ 0
Вариант 8.
F = –7x1 + 2x2 min
x1 + x2 ≥ 1
5x1 + x2 ≥ 3
–3x1 + x2 ≤ 3
2x1 + x2 ≤ 4
x1 , x2 ≥ 0
Вариант 9.
F = 6x1 + 4x2 min
2x1 + x2 ≥ 3
x1 – 2x2 ≤ 2
x1 , x2 ≥ 0
Вариант 10.
F = – x1 – 2x2 min
5x1 – 2x2 ≤ 4
– x1 + 2x2 ≤ 4
x1 + x2 ≥ 4
x1 , x2 ≥ 0
Вариант 11.
F = 3x1 + 3x2 max
x1 + x2 ≤ 4
3x1 + x2 ≥ 4
x1 + 5x2 ≥ 4
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 3
Вариант 12.
F = 7x1 – 2x2 max
x1 + x2 ≤ 5
2x1 – 3x2 ≤ 6
3x1 + x2 ≥ 3
x1 + x2 ≥ 2
x1 – x2 ≥ –3
x1 , x2 ≥ 0
Вариант 13.
F = 6x1 – x2 min
x1 + x2 ≥ 3
4x1 – x2 ≥ –4
3x1 – 2x2 ≤ 24
x2 ≤ 6
x1 , x2 ≥ 0
Вариант 14.
F = –3x1 – 2x2 max
x1 – 2x2 ≤ –3
2x1 + x2 ≤ 10
3x1 – x2 ≥ –5
–x1 + x2 ≥ 3
x1 , x2 ≥ 0
Вариант 15.
F = x1 + 2x2 max
2x1 + 3x2 ≤ 8
2x1 + x2 ≤ 6
x1 + x2 ≥ 1
x1 , x2 ≥ 0
Вариант 16.
F = –2x1 + x2 min
2x1 + x2 ≤ 8
x1 + 3x2 ≥ 6
3x1 + x2 ≥ 3
x1 , x2 ≥ 0
Вариант 17.
F = 6x1 + 4x2 min
2x1 + x2 ≥ 3
x1 – 2x2 ≤ 1
–x1 + 2x2 ≥ 1
x1 , x2 ≥ 0
Вариант 18.
F = 4x1 + 3x2 max
5x1 + 2x2 ≥ 20
x1 + 3x2 ≤ 15
x1 , x2 ≥ 0
Вариант 19.
F = x1 + 3x2 max
x1 + x2 ≥ 3
6x1 + x2 ≤ 42
2x1 – 3x2 ≥ 6
x1 , x2 ≥ 0
Вариант 20.
F = x1 – 2x2 max
5x1 – 2x2 ≤ 3
x1 + x2 ≥ 1
–3x1 + x2 ≤ 3
x1 , x2 ≥ 0
Вариант 21.
F = 8x1 + 2x2 max
x1 – 4x2 ≤ 4
–4x1 + x2 ≤ 4
x1 + x2 ≤ 6
x1 , x2 ≥ 0
Вариант 22.
F = 2x1 + 3x2 min
x1 + 5x2 ≥ 16
3x1 + 2x2 ≥ 12
2x1 + 4x2 ≥ 16
x1 ≥ 1
x1 , x2 ≥ 0
Вариант 23.
F = 3x1 + 3x2 max
x1 + x2 ≤ 4
3x1 + x2 ≥ 4
x1 + 5x2 ≥ 4
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 3
Вариант 24.
F = 7x1 – 2x2 max
x1 + x2 ≤ 5
2x1 – 3x2 ≤ 6
3x1 + x2 ≥ –3
x1 , x2 ≥ 0
Вариант 25.
F = –7x1 + 2x2 min
x1 + x2 ≥ 1
5x1 + x2 ≥ 3
–3x1 + x2 ≤ 3
2x1 + x2 ≤ 4
x1 , x2 ≥ 0
Вариант 26.
F = 2x1 – x2 max
3x1 + x2 ≥ 16
x1 + 2x2 ≤ 12
x1 , x2 ≥ 0
Вариант 27.
F = 6x1 + 4x2 min
2x1 + x2 ≥ 3
x1 – 2x2 ≤ 2
3x1 + 2x2 ≥ 1
x1 , x2 ≥ 0
Вариант 28.
F = –x1 – 2x2 min
5x1 – 2x2 ≤ 4
–x1 + 2x2 ≤ 4
x1 + x2 ≥ 4
x1 , x2 ≥ 0
Вариант 29.
F = x1 + 2x2 min
5x1 – 2x2 ≤ 20
x1 – 2x2 ≥ –20
x1 + x2 ≥ 16
x1 , x2 ≥ 0
Вариант 30.
F = x1 + x2 max
2x1 + x2 ≤ 18
x1 + 2x2 ≤ 16
x1 , x2 ≥ 0
1.2. Симплексный метод решения задач ЛП.
Прежде чем решать задачу ЛП симплекс-методом ее необходимо привести к каноническому виду :
(1.7)
(1.8)
(1.9)
Для этого в случае необходимости задача (1.1) поиска минимума сводится к задаче на поиск максимума (1.7) путем изменения знаков коэффициентов Сj
;
Неравенства (1.2) преобразуются в строгие равенства путем введения дополнительных неотрицательных переменных; условия неотрицательности (1.3) распространяются на все переменные путем введения подстановок.
Пример . Дана задача ЛП в общем виде:
Приведем ее к каноническому виду. Условие неотрицательности не распространяется на переменную х2 . Поэтому введем подстановку: х2 = х5 – х4 , где .
Тогда
Изменим вид экстремума на максимум:
Изменим неравенства на строгие равенства путем введения дополнительных неотрицательных переменных. Тогда
Основные понятия и определения . Исходная задача (1.7), (1.8), (1.9) может быть представлена в векторной форме:
x1 Р1 +x2 Р2 +…+xn Pn =P0
С=(c1 , c2 … cn ); X=(x1 ,x2 … xn ); P1 ,P2 …Pn , P0 – m-мерные вектор-столбцы.
Вектор X=(x1 ,x2 … xn ) называется опорным планом задачи ЛП, если он удовлетворяет ограничениям (1.8); (1.9) и содержит m отличных от нуля положительных компонент. Остальные (n-m) элементов опорного плана равны нулю. Алгоритм симплекс-метода предполагает переход от одного опорного плана к другому с увеличением при этом значения целевой функции.
В некоторых случаях исходный опорный план можно легко определить. Это происходит тогда, когда среди векторов Pj имеется m единичных. В этом случае соответствующие единичным векторам переменные в опорном плане будут отличны от нуля. Они называются базисными. Остальные переменные равны нулю; они называются свободными.
Симплекс-преобразования продолжаются до тех пор, пока среди чисел не будет отрицательных.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию