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

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 10Следующая ⇒

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

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

¦=c₁x₁+c₂x₂+... +c_nx_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.

Схема перевозок таблица 4.1

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

x _{i j} = C _{i j} ^. X _{i j}

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

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США