Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 5 из 14)

Считая Z₀ параметром, получим семейство параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). Нас интересуют те точки области допустимых решений, которые принадлежат линии уровня с наибольшим значением Z₀ по сравнению с его значениями для всех других линий уровня, пересекающихся с областью допустимых решений.

Возникает вопрос: как установить направление возрастания (убывания) целевой функции по x₁ и х₂ :

(2.9)

(2.10)

Частная производная (2.9) и (2.10) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, с₁ и с₂ - скорости возрастания вдоль осей Oх₁ и Oх_2. Вектор

называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор - указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор перпендикулярен к прямым Z = const семейства

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

1, С учетом системы ограничений строим область допустимых решений.

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

наискорейшего возрастания целевой функции.

3. Проводим произвольную линию уровня Z=Z_0, перпендикулярную к вектору

так, чтобы она пересеклась с областью допустимых решений.

4. При решении задач на max перемещаем линю уровня Z=Z₀ в направлении вектора

так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точки) (на рис.2.2 точка С). В случае решения задачи на min линию уровня Z=Z₀ перемещают в направлении вектора - (на рис .2.2 - точка Е).

Определяем оптимальный план

и экстремальное значение целевой функции .

Пример 2.1.

Предприятию необходимо изготовить два вида продукции А и В,

с использованием трех видов ресурсов R_1, R₂, R₃ количество которых ограничено. Исходные данные задачи представлены в таблице:

Вид ресурсов	Количество ресурсов, идущих на изготовление единицы продукции		Запасы ресурсов
А	В
R1	6	6	36
R2	4	2	20
R3	4	8	40
Доходы от реализации продукции	12	15

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции видов А и В, планируемых к выпуску.

Известно, что доход от реализации единицы продукции А составляет 12 усл. ед. и количество этой продукции - х₁. Следовательно, доход от реализации всей продукции А составит 12х₁ усл. ед. Аналогично, доход от реализации всей продукции В составит 15х₂ усл. ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид:

Известно также, что имеющиеся на предприятии ресурсы ограничены. Это обстоятельство в свою очередь необходимо отразить в модели. Предприятие производит продукцию, используя три вида ресурсов. Естественно, что фактический расход никакого вида ресурса не должен превышать запасов соответствующего вида ресурсов на предприятии. Поскольку расход каждого вида ресурсов на единицу каждого вида продукции и запасы ресурсов известны, это обстоятельство отражается в следующих ограничениях:

Смысл первого ограничения состоит в том, что фактический расход ресурса R₁ на производство продукции А и В, равный 6х₁+6х₂ (здесь 6х₁ - количество единиц ресурса R₁, идущего на изготовление х₁ единиц продукции A; 6х₂ - количество единиц ресурса R_1, идущее на изготовление х₂ единиц продукции В) не должен превышать запаса этого ресурса на предприятии, равного 36 ед. Аналогичный смысл имеют 2-е и 3-е ограничения только для ресурсов R₂ и R₃ соответственно.

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

Таким образом, построена математическая модель нашей задачи как задачи линейного программирования:

Начнем решение задачи с построения области допустимых решений (рис.2.3)

В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х₁=0 и х₂=0 совпадают с осями координат. Полуплоскости x₁>0,x₂>0 лежат соответственно справа от оси Oх₂ и выше оси Oх₁. Множество точек, удовлетворяющих одновременно неравенствам

представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти.

Теперь рассмотрим ограничения задачи. Построим по порядку прямые:

` 6x₁+6x₂=36 или х₁+х₂=6 (а)

4х₁+2х₂=20 или 2х₂+х₂=10 (б)

4х₁+8х₂=40 или х₁+2х₂=10 (в)

и определяем, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам:

6x₁+6x₂<36

4x₁+2x₂<20

4x₁+8x₂<40

Для определения полуплоскости решений первого неравенства возьмем произвольную точку плоскости, не лежащую на прямой 6х₁+6х₂=36, например (0;0), и подставим ее координаты в неравенство

.

В результате подстановки получили верное числовое неравенство 0< 36, и это означает, что начало координат лежит в полуплоскости решений первого неравенства. Сторона, в которой располагается полуплоскость от прямой, указывается штриховой.

Аналогично строим полуплоскость решений остальных неравенств.

X₂

б)

a) N₂

в) M

*6

в