Геометрическая интерпретация задач линейного программирования

ЗАДАЧИ

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

2. Как полоску профильного проката длиной 5 м раскроить на детали двух сортов (по 6 и 7 см) так, чтобы максимально использовать полоску и получить при этом почти одинаковое количество деталей обоих видов?

3. Нужна спортплощадка площадью 6000 кв.м. прямоугольной формы, которую надо огородить с двух противоположных сторон деревянным забором, с двух других противоположных сторон - проволочным. Постройка одного метра деревянного забора стоит 5 руб., проволочного - 3 руб. При каких размерах спортплощадки затраты на забор будут минимальными?

4. Юноша, находится в точке А, девушка - в точке В на одном и том же берегу прямолинейного канала, усеянного цветами водной линии. Какой минимальный маршрут должен выбрать юноша, чтобы прийти на свидание с букетом? Точки А и В удалены от воды, скорость юноша постоянна.

Оптимизационные задачи.

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

 количество продукции - расход сырья

 количество продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

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

2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.

4. Учет ограничений.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.

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

Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении.

Линейное программирование характеризуется тем, что

а) функция

является линейной функциейпеременных ;

б) область G определяется системой линейных равенств или неравенств.

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

Первая стандартная форма задачи линейного программирования имеет вид

(1.7)

Введем вектора

;;,

a также вектора

,

и матрицу

.

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

(1.8)

Можно использовать и матричные обозначения. Тогда комбинация

есть произведение

и задача (1.7) примет вид

(1.9)

Вторая стандартная форма задачи линейного программирования имеет вид

(1.10)

В векторной форме эта задача имеет вид

(1.11)

и в матричной форме - вид

(1.12)

Канонической формой задачи линейного программирования называется задача вида

(1.13)

В векторной форме эта задача имеет вид

(1.14)

и в матричной форме - вид

(1.15)

Во всех этих задачах функцию называют целевой функцией. Вектор называют вектором коэффициентов линейной формы, вектор  вектором ограничений.

Матрицу

называют матрицей коэффициентов.

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

Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n =2 и n =3.

Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных и . Пусть нам задана задача линейного программирования в стандартной форме

(1.19)

Возьмём на плоскости декартову систему координат и каждой паре чисел поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения и . Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида . Сначала рассмотрим область, соответствующую равенству . Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.

Пусть . Если взять , то получится . Если взять , то получится . Таким образом, на прямой лежат две точки и . Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2).

Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение и вычислить

соответствующее ему значение .

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части , а в другой наоборот . Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).