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

 

Предположим, что задана некоторая система из 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

 

	ПН	в П1	в П2	в П3	в П4	в П5	Всего
ПО							отправлено
из М1	х11	х12	х13	х14	х15	a1
из М2	х21	х22	х23	х24	х25	а2
из М3	х31	х32	х33	х34	х35	а3
из М4	х41	х42	х43	х44	х45	а4
Всего привезено	b1	b2	b3	b4	b5

 

4.1

ìх11+х12+х13+х14+х15 = b1 ïх21+х22+х23+х24+х25 = b2 íх31+х32+х33+х34+х35 = b3 îх41+х42+х43+х44+х45 = b4

4.2

ìх11+х12+х13+х14+х15 = a1 ïх21+х22+х23+х24+х25 = a2 íх31+х32+х33+х34+х35 = a3 îх41+х42+х43+х44+х45 = a4

 

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

 

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

 

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

 

S=c₁₁х₁₁+c₁₂х₁₂+c₁₃х₁₃+c₁₄х₁₄+c₁₅х₁₅+... +c₄₁х₄₁+c₄₂х₄₂+c₄₃х₄₃+c₄₄х₄₄+c₄₅х₄₅.