Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп

План лекции:

1. Геометрическая интерпретация решения ЗЛП

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

3. Возможные случаи области допустимых решений при решении ЗЛП

графическим методом

4. Основные свойства решения ЗЛП

5. Классификация решений ЗЛП

6. Решение ЗЛП с точки зрения линейной алгебры

1. Геометрическая интерпретация решения злп

Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически, а с большим количеством – только при условии, что , где n – количество переменных, m – количество ограничений канонической записи ЗЛП.

Пусть дана задача:

.

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений задает на плоскости некоторую полуплоскость (выпуклое множество). Пересечение любого числа выпуклых множеств является выпуклым множеством, следовательно, ОДР – выпуклое множество.

Примеры ОДР при решении ЗЛП графическим методом:

1) выпуклый многоугольник (рис. 2.1)

Рис. 2.1

2) неограниченная многоугольная область (рис.2.2)

Рис. 2.2

Перейдем к геометрической интерпретации целевой функции. Пусть ОДР ЗЛП – непустое множество А₁А₂А₃А₄А₅ (рис. 2.1). Выберем произвольное значение целевой функции F(x)=c, c=const. Следовательно, (2.1) – прямая линия.

Считая в равенстве (2.1) с параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции.

Как установить направление возрастания (убывания) целевой функции по и ? Частные производные и показывают скорости изменения вдоль осей и соответственно. Вектор – градиент целевой функции, показывает направление наискорейшего возрастания функции . Вектор указывает направление наискорейшего убывания функции и называется антиградиентом. Градиент перпендикулярен к линиям уровня .

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

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

1) С учетом системы ограничений строится ОДР: записывают уравнения прямых, соответствующих ограничениям ЗЛП, и строят их на плоскости ; выбирают полуплоскости для каждого ограничения; определяют ОДР как область пересечения m полуплоскостей, соответствующих m ограничениям задачи.

2) Строится градиент с точкой приложения в начале координат.

3) Проводится линия уровня перпендикулярно градиенту (проще всего провести линию = 0).

4) Опускаются перпендикуляры из всех вершин выпуклого множества на линию уровня, и определяется точка искомого экстремума целевой функции с учетом направления градиента. Решаются совместно уравнения, задающие прямые, на пересечении которых находится эта точка.

5) Определяется оптимальное решение и экстремальные значения целевой функции .

Задача. Фирма получила заказ на изготовление курток и пальто по моделям из материала заказчика. Расчет показал, что на изготовление куртки потребуется 3 усл. ед. материала, на пальто – 4 усл. ед., при ограничении имеющегося материала 170 усл. ед. Причем при пошиве куртки фирма располагает 2 станко-часами, пальто – 5 станко-часами, при ограничении 160 станко-часов. За пошив куртки заказчик платит 2 ден. ед., пальто – 4 ден. ед. Ассортимент заказчик не указывает. Найти число курток и пальто, которое фирма может предложить заказчику для получения максимальной прибыли.

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

Ресурсы	Нормы расхода на единицу продукции		Объем ресурса
	Куртка	Пальто
Сырье, усл. ед.	3	4	170
Оборудование, станко-час	2	5	160
Прибыль от реализации ед. продукции, ден. ед.	2	4

Решение задачи:

Введем обозначения: х₁ - количество курток, х₂ - количество пальто. Тогда математическая модель задачи примет вид:

.

Для построения ОДР ЗЛП строим на плоскости соответствующие данным ограничениям-неравенствам граничные прямые:

;

x1	–10	50		x1	0	80
x2	50	5		x2	32	0

Находим полуплоскости, в которых выполняются данные неравенства. Для этого вследствие выпуклости любой полуплоскости достаточно взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить, удовлетворяет ли эта пробная точка ограничению-неравенству. Если удовлетворяет, то данное неравенство выполняется в полуплоскости, содержащей пробную точку. В противном случае берется полуплоскость, не содержащая пробной точки. В качестве пробной точки часто удобно брать начало координат. Для нашей задачи ОДР – множество точек четырехугольника АВСО с учетом неотрицательности переменных (рис. 2.3)

Рис. 2.3

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

Проведем линию уровня = 0, то есть

x1	0	–20
x2	0	10

Опустим перпендикуляры из угловых точек на линию уровня. С учетом направления градиента целевая функция достигает максимума в точке В, координаты которой можно найти, решив систему уравнений:

Решение системы x₁ = 30, х₂ = 20.

Так как x^* = (30;20), то .

Ответ: x^* = (30;20), .

Таким образом, для получения фирмой максимальной прибыли в размере 140 ден. ед. надо предложить заказчику пошить 30 курток и 20 пальто.