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

Лабораторная работа.

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

Цель: преобретение практических навыков применения методов линейного программирования

Задача линейного программирования (ЛП) состоит в определении максимального (минимального) значения целевой функции:

(1.1)

При условиях :

(1.2)

(1.3)

где a_ij , b_i , c_j – заданные постоянные числа. Функция F(1) называется целевой функцией, выражения (2), (3) – ограничениями. Значения x_j , удовлетворяющие ограничениям (2), (3) образуют область допустимых решений (ОДР) и называются допустимыми. Допустимое решение x_j ^* , при которых целевая функция (1) принимает экстремальное значение, называется оптимальным. В зависимости от структуры выражений (1), (2), (3) для решения задачи ЛП могут применяться различные методы, которые рассмотрены ниже.

1.1. Графический метод решения задач ЛП.

Постановка задачи. Метод применяется в том случае, если количество переменных задачи ЛП (1), (2), (3) равно двум, т.е.:

(1.4)

(1.5)

(1.6)

Методика решения Процесс решения задачи ЛП графическим методом включает следующие этапы:

1) На плоскости Х₁ ОХ₂ строятся граничные прямые, уравнения которых получают путем замены неравенств (5), (6) на строгие равенства

2) Находятся полуплоскости, определяемые каждым из ограничений (5), (6).

3) Определяется область допустимых решений ОДР задачи на плоскости Х₁ ОХ₂ . Если система ограничений (5), (6) несовместна, то задача ЛП не имеет решения.

4) Строится вектор

5) Строится прямая с₁ х₁ +с₂ х₂ = 0, перпендикулярная вектору и передвигается в направлении вектора (при поиске максимума целевой функции); в результате определяется точка А, принадлежащая ОДР, в которой целевая функция F принимает максимальное значение. Если ОДР не ограничена сверху, то задача ЛП не имеет решений.

6) Определяют координаты точки А – (х₁ ^* ,х₂ ^* ) и максимальное значение функции F^* =с₁ х₁ ^* + с₂ х₂ ^* .

Пример. Решить задачу ЛП:

1. На плоскости Х₁ ОХ₂ строим уравнения прямых: х₁ –х₂ = 3; х₁ + 2х₂ = 4; х₂ = 4; х₁ =0; х₂ =0

2. Для каждого из ограничений определяем допустимую полуплоскость и отмечаем ее стрелками. Например, условие при х₁ =0; х₂ =0 выполняется. Значит точка (0,0) лежит в допустимой полуплоскости.

3. Определяем допустимую область для всех ограничений задачи (ОДР). Это многоугольник ABCD.

4. Строим вектор .

5. Строим прямую F=2x₁ +x₂ = 0. Передвигая ее в направлении вектора , определяем крайнюю точку А, принадлежащую ОДР – это т. А. В т. А функция имеет максимальное значение. Минимальное значение целевая функция принимает в т.С.

6. Координаты т. А находятся путем решения системы

Аналогично определяются координаты точки минимума С:

Индивидуальные задания. Решить графическим методом.

Вариант 1.

F = x₁ + x₂ max

-3x₁ + 2x₂ ≤ 1

x₁ + 2x₂ ≤ 14

2x₁ + x₂ ≤ 13

3x₁ – x₂ ≤ 12

x₁ , x₂ ≥ 0

Вариант 2.

F = 3x₁ + x₂ min

3x₁ + 5x₂ ≥ 15

5x₁ + 3x₂ ≥ 15

x₁ ≥ 1

x₂ ≥ 1

x₁ , x₂ ≥ 0

Вариант 3.

F = 3x₁ + 3x₂ min

x₁ + 4x₂ ≥ 4

4x₁ + x₂ ≥ 4

x₁ , x₂ ≥ 0

Вариант 4.

F = 6x₁ – 5x₂ max

2x₁ + 5x₂ ≤ 10

5x₁ + 2x₂ ≤ 10

x₁ , x₂ ≥ 0

Вариант 5.

F = 8x₁ + 2x₂ max

x₁ – 4x₂ ≤ 4

–4x₁ + x₂ ≤ 4

x₁ + x₂ ≤ 6

x ₁ , x ₂ ≥ 0

Вариант 6.

F = 2x₁ + 3x₂ min

x₁ + 5x₂ ≥ 10

3x₁ + 2x₂ ≥ 12

2x₁ + 4x

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

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

Скачать