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