Алгоритм графического метода решения ЗЛП.

Метод наглядный, используется для решения ЗЛП, представленных в стандартной форме с количеством переменных не более 3.

Если модель представлена в канонической форме, то ее нужно преобразовать в стандартную. Задача может быть решена, если п число переменных – т число ограничений = 2.

1) построить ОДЗ путем последовательного построения каждого из условий системы ограничений задачи

2) строится направляющий вектор по коэффициентам при переменных целевой функции

3) перпендикулярно направляющему вектору через начало координат проводится исходная изоцель

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

5) для определения координат оптимальной точки необходимо решить систему соответствующих линейных уравнений тех условий, на пересечении которых находится оптимальная точка

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

x_max (x₁; x₂)

Закрепление изученного материала.

Пример № 1.

Преобразовать ЗЛП в каноническую форму

z = х₁ – х₂ – х₃ + 5х₄ → max

2х₁ – х₂ + 3х₃ + х₄ ≥ 5

х₁ + х₂ + 6х₃ – 7х₄ = 2

х₁ + 3х₂ – 12х₃ + х₄ ≤ 10

х₁ ≥ 0, х₂ ≤ 0, х₄ ≤ 0

Решение.

1) Вводим новые переменные х′₂ = - х₂, х′₄ = - х₄, х′₂ ≥ 0, х′₄ ≥ 0, х₃ = х′₃ - х′′₃, х′₃ ≥ 0, х′′₃ ≥ 0 в целевую функцию z =х₁ + х′₂ + х′′₃ - х′₃ – 5х′₄

2) преобразуем целевую функцию на min:

z ′ = – z = – х₁ – х′₂ + х′₃ - х′′₃ + 5х′₄ → min

3) Вводим новые переменные в систему ограничений.

2х₁ + х′₂+ 3(х′₃ - х′′₃) + х′₄ – х₅ = 5

х₁– х′₂ + 6(х′₃ - х′′₃) + 7х′₄ = 2

х₁– 3х′₂– 12(х′₃ – х′′₃) – х′₄ + х₆ = 10

х₁ ≥ 0, х′₂ ≥ 0, х′₃ ≥ 0, х′′₃ ≥ 0, х′₄ ≥ 0, х₅ ≥ 0, х₆ ≥ 0

z ′ = – z = – х₁ – х′₂ + (х′₃ - х′′₃) + 5х′₄ + 0·х₅ + 0·х₆→ min

Пример № 2.

Преобразовать в каноническую форму

z = –х₁ – 3 х₃ → max

4х₁ + 3х₂ + 3х₃ = 6

– 4х₁ – 2х₂ + 3х₃ ≤ 8

х₁ + 2х₃ ≥ 8

х₂ ≥ 0, х₃ ≤ 0

Решение.

1) Вводим новые переменные

х′₃= - х₃, х₁ = х′₁ – х′′₁,

х′₃ ≥ 0, х′₁ ≥ 0, х′′ ₁ ≥ 0, х₄ ≥ 0, х₅ ≥ 0

в систему ограничений:

4(х′₁ – х′′₁) + 3х₂ – 3х′₃ = 6

– 4(х′₁ – х′′₁) – 2х₂ – 3х′₃ + х₄ = 8

(х′₁ – х′′₁) – 2х′₃ – х₅ = 8

в целевую функцию:

z ′ = – z = х₁ + 3х₃ → min

z ′ = – z = х′₁ – х′′₁ – 3х′₃ + 0·х₄ + 0·х₅→ min

Пример № 3 .

Решить графическим методом систему линейных неравенств и найти наибольшее и наименьшее значение целевой функции:

Решение.

Построим прямые по координатам двух точек

(0;10);	(6; 0)

(0; 6);	(10; 0)

(0; 3);	(6; 0)

(0; 6);	(3; 0)

Находим координаты точек А, В, С, D , Е

т. А Δ = 4 – 1 = 3; Δ₁ = 12 – 6 = 6;

Δ₂ = 12 – 6 = 6; х₁ = х₂ =

т. В х₁ = т. С х₁ = =

т. D Δ = 9 – 25 = – 16; Δ₁ = 90 – 150 = – 6 0;

Δ₂ = 90 – 150 = – 6 0; х₁ = х₂ =

т. Е Δ = 3 – 1 0 = – 7; Δ₁ = 1 8 – 6 0 = – 42;

Δ₂ = 30 – 30 = 0; х₁ = х₂ =

Находим значение целевой функции в этих точках и выбираем наибольшее и наименьшее

Z_A = Z (2;2) = 5 · 2 + 2 = 12

Z_B = Z = 5 · + 5 =

Z_C = Z = 5 · + 5 = + 5 = + 5 =

Z_D = Z = 5 · + =

Z_E = Z (6;0) = 5 · 6 + 0 = 30

М = Z_E (6;0) = 30 т = Z_B =

Ответ: М = Z_E (6;0) = 30; т = Z_B =

Задание:

1. Изучив опорный конспект, ответить на вопросы:

Ø Назвать, в каких формах существуют задачи линейного программирования (ЗЛП), в чем особенности каждой из форм;

Ø Алгоритм перехода от одной формы ЗЛП к другой;

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

2. Внимательно разобрать образцы решенных примеров, записать их в тетрадь.

Дата добавления: 2020-11-23; просмотров: 112; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!