Значения линейной формы на выпуклом множестве

Предположим, что задана некоторая система из m -линейных неравенств (или уравнений) с n переменными х₁, х₂,..., х_n. Система неравенств в случае совместности определяет некоторое выпуклое множество в n -мерном пространстве, ограниченное или бесконечное (многогранник решений).

Допустим далее, что нам задана некоторая линейная форма от этих переменных, определяющая функцию цели:

В каждой точке выпуклого множества, т.е. для каждого решения нашей системы, линейная форма ¦ принимает определенное значение. Возникает вопрос: в каких точках выпуклого множества линейная форма ¦ достигает своего наибольшего и наименьшего значения, если, конечно, такие существуют? Решение общей задачи линейного программирования сводится, таким образом, к нахождению точек выпуклого множества, в которых заданная линейная форма достигает оптимального значения, и мы ищем такие точки (х₁, х₂,..., х_n), координаты которых неотрицательны. Сформулируем одно важное утверждение, облегчающее решение задачи.

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

В общем случае, линейная форма ¦=c₁x₁+c₂x₂+... +c_nx_n задает гиперплоскость в n -мерном пространстве. При ¦=0 эта гиперплоскость проходит через начало координат. Затем передвигаем эту плоскость параллельно самой себе в направлении вектора P перпендикулярно к этой плоскости. Первая из вершин, в которой линейная форма (гиперплоскость) встретит выпуклый многогранник, будет точкой, в которой линейная форма достигает наименьшего значения, а последняя из вершин - точкой, в которой линейная форма достигает наибольшего значения.

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

Существуют различные методы решения задач линейного программирования. Одним из наиболее простых и наглядных методов решения является графический метод. Этот метод позволяет решать задачи, которые приводят к системам уравнений с двумя или тремя переменными. Большинство задач линейного программирования приводит к системам линейных неравенств с большим числом переменных. Эти задачи решаются симплексным методом.

ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

уголь, добываемый в нескольких месторождениях, отправляется ряду потребителей. нам известно, сколько угля добывается в каждом из месторождений, скажем за месяц и сколько его требуется на тот же срок каждому из потребителей. Известны расстояния между месторождениями и потребителями, а также условия сообщения между ними. Учитывая эти данные. Можно подсчитать, во что обходится перевозка каждой тонны угля из любого месторождения в любой пункт потребления. Требуется при этих условиях спланировать перевозки угля таким образом, чтобы затраты на них были минимальными.

Пусть для простоты заданы всего 4 месторождения М₁, М₂, М₃, М₄, причем их ежемесячная добыча составляет a₁, а₂, а₃, а₄ тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b₁, b₂, b₃, b₄, b₅, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a₁, а₂, а₃, а₄ = b₁, b₂, b₃, b₄, b₅. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x₁₁ количество угля (в тоннах), предназначенное к отправлению из M₁ в П₁; вообще через x_ij обозначим количество угля, отправляемого из месторождения M_i в пункт потребления П_j. Схема перевозок примет вид, изображенный в таблице 4.1.

Общее количество угля, привозимое в пункт П₁ из всех месторождений, будет х₁₁₊х₁₂₊х₁₃₊х₁₄₊х_{15 =}b₁; в другие пункты - П₂, П₃ и т.д. и примет вид уравнений 4.1. общее количество угля, вывозимое из М₁, будет: х₁₁₊х₁₂₊х₁₃₊х₁₄₊х_{15 =}a₁, примет вид 4.2. предполагаем, что стоимость перевозки прямо пропорциональна количеству перевозимого угля, т.е. стоимость перевозки x_ij тонн угля равна:

Общая стоимость S всех перевозок будет равна: (4.3)

Общая формулировка задачи линейного программирования

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

À эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;

Á при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);

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

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

Требуется найти такие неотрицательные решения х₁ ³ 0, х₂ ³ 0... х_n ³ 0 (III) системы (I) при которых функция ¦ принимает наименьшее (наибольшее) значение.

Уравнения (I) называются ограничениями данной задачи, уравнение (II) называется линейной формой, а уравнение (III), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.

Казалось бы, т.к. задача линейного программирования ставится как задача минимизации некоторой функции ¦, то можно применить классический прием дифференциального исчисления. Однако частные производные ¦ равны коэффициентам при неизвестных, которые в «нуль» одновременно не обращаются.

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: