Примеры сетевых задач, сводящихся к задачам линейного программирования

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

Таким макаром, задачки линейного программирования (ЗЛП) относятся к задачкам на условный экстремум. Но для исследования линейной функции многих переменных на условный экстремум нельзя использовать отлично разработанные способы математического анализа.

Вправду, пусть

при линейных ограничениях

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

Но эти личные производные от линейной функции равны константам

,

Отсюда

Потому что все коэффициенты линейной функции не могут быть равны нулю, то снутри области, образованной системой ограничений, экстремальные точки не есть. Они могут быть лишь на границе области.

Потому для схожих задач разработаны особые способы Примеры сетевых задач, сводящихся к задачам линейного программирования линейного программирования.

Разглядим сначала формы записи задач линейного программирования.

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


1. Общая либо случайная форма записи

при ограничениях

– произвольные .

2. Симметричная либо стандартная форма записи

а)

б)

3. Каноническая либо основная форма записи

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

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

Так, по мере надобности задачку минимизации можно поменять задачей максимизацией и напротив:

.

Неравенство типа методом умножения левых и правых частей на -1 можно перевоплотить в неравенство типа и напротив.

Ограничения-неравенства типа

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

Если Примеры сетевых задач, сводящихся к задачам линейного программирования в ЗЛП какая-либо переменная не подчинена условию неотрицательности, ее подменяют разностью 2-ух других неотрицательных переменных и :

.

Дальше разглядим геометрическую интерпретацию задачки линейного программирования применительно к двум переменным.

Отыскать лучший план , доставляющий

(1)

при ограничениях

(2)

(3)

Начнем с геометрической интерпретации области допустимых решений.

Каждые из неравенств (2) определяет на координатной плоскости некую полуплоскость, а Примеры сетевых задач, сводящихся к задачам линейного программирования система неравенств (2), (3) в случае ее совместности – их скрещение.

Это огромное количество будет выпуклым. Оно может представлять собой последующие геометрические конструкции (Набросок 28).

Перейдем дальше к геометрической интерпретации мотивированной функции (1).

Уравнение при фиксированном значении определяет на плоскости прямую линию

.

При изменении выходит семейство параллельных линий, называемое линиями уровня.


а) выпуклый многоугольник (число Примеры сетевых задач, сводящихся к задачам линейного программирования вершин равно m);
б) неограниченная выпуклая многоугольная область;
в) отрезок прямой;
г) луч;
д) точка;
е) пустое огромное количество.

Набросок 28 – Геометрическая интерпретация ЗЛП


Вектор с компонентами из коэффициентов при и перпендикулярен к каждой из линий уровня.

Вектор указывает направление возрастания (убывания) мотивированной функции.


primernaya-programma-disciplini-kulturologiya-rekomenduetsya-dlya-specialnosti-podgotovki.html
primernaya-programma-disciplini-metallicheskie-konstrukcii-vklyuchaya-svarku-obshij-kurs-rekomenduetsya-dlya-specialnosti-podgotovki.html
primernaya-programma-disciplini-op-08-osnovi-patologii-specialnost-060101-lechebnoe-delo.html