Значения линейной формы на выпуклом множестве
Предположим, что задана некоторая система из m-линейных неравенств (или уравнений) с n переменными х1, х2, ..., х n. Система неравенств в случае совместности определяет некоторое выпуклое множество в n-мерном пространстве, ограниченное или бесконечное (многогранник решений).
Допустим далее, что нам задана некоторая линейная форма от этих переменных, определяющая функцию цели:
= c 1 x 1 + c 2 x 2 + ... + cnxn
В каждой точке выпуклого множества, т.е. для каждого решения нашей системы, линейная форма ¦ принимает определенное значение. Возникает вопрос: в каких точках выпуклого множества линейная форма ¦ достигает своего наибольшего и наименьшего значения, если, конечно, такие существуют? Решение общей задачи линейного программирования сводится, таким образом, к нахождению точек выпуклого множества, в которых заданная линейная форма достигает оптимального значения, и мы ищем такие точки (х1, х2, ..., х n ), координаты которых неотрицательны. Сформулируем одно важное утверждение, облегчающее решение задачи.
В тех случаях, когда множество решений задачи линейного программирования образует выпуклый многогранник, линейная форма достигает оптимального значения в одной из его вершин, в связи с чем последние и называются экстремальными точками.
В общем случае, линейная форма ¦ = c 1 x 1 + c 2 x 2 + ... + cnxn задает гиперплоскость в n-мерном пространстве. При ¦ =0 эта гиперплоскость проходит через начало координат. Затем передвигаем эту плоскость параллельно самой себе в направлении вектора P перпендикулярно к этой плоскости. Первая из вершин, в которой линейная форма (гиперплоскость) встретит выпуклый многогранник, будет точкой, в которой линейная форма достигает наименьшего значения, а последняя из вершин - точкой, в которой линейная форма достигает наибольшего значения.
|
|
|
Может случиться, что гиперплоскость окажется параллельной одной из граней или ребер выпуклого многогранника, и тогда линейная форма ¦ достигает своего наименьшего или наибольшего значения в любой точке, лежащей на этом ребре. Но и тогда она достигает эти значения в вершине, лежащей на этом ребре.
Существуют различные методы решения задач линейного программирования. Одним из наиболее простых и наглядных методов решения является графический метод. Этот метод позволяет решать задачи, которые приводят к системам уравнений с двумя или тремя переменными. Большинство задач линейного программирования приводит к системам линейных неравенств с большим числом переменных. Эти задачи решаются симплексным методом.
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
|
|
|
Транспортная задача
уголь, добываемый в нескольких месторождениях, отправляется ряду потребителей. нам известно, сколько угля добывается в каждом из месторождений, скажем за месяц и сколько его требуется на тот же срок каждому из потребителей. Известны расстояния между месторождениями и потребителями, а также условия сообщения между ними. Учитывая эти данные. Можно подсчитать, во что обходится перевозка каждой тонны угля из любого месторождения в любой пункт потребления. Требуется при этих условиях спланировать перевозки угля таким образом, чтобы затраты на них были минимальными.
Пусть для простоты заданы всего 4 месторождения М1, М2, М3, М4, причем их ежемесячная добыча составляет a 1 , а2, а3, а4 тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b 1 , b 2 , b 3 , b 4 , b 5, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a 1 , а2, а3, а4 = b 1 , b 2 , b 3 , b 4 , b 5. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x 11 количество угля (в тоннах), предназначенное к отправлению из M 1 в П1; вообще через xij обозначим количество угля, отправляемого из месторождения Mi в пункт потребления П j. Схема перевозок примет вид, изображенный в таблице 4.1.
|
|
|
Схема перевозок таблица 4.1
| ПН | в П1 | в П2 | в П3 | в П4 | в П5 | Всего | |
| ПО | отправлено | ||||||
| из Ì1 | х11 | х12 | х13 | х14 | х15 | a 1 | |
| из Ì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 |
Общее количество угля, привозимое в пункт П1 из всех месторождений, будет х11+х12+х13+х14+х15 = b 1; в другие пункты - П2, П3 и т.д. и примет вид уравнений 4.1. общее количество угля, вывозимое из М1, будет: х11+х12+х13+х14+х15 = a 1, примет вид 4.2.предполагаем, что стоимость перевозки прямо пропорциональна количеству перевозимого угля, т.е. стоимость перевозки xij тонн угля равна:
x i j = C i j . X i j
Общая стоимость S всех перевозок будет равна: (4.3)
|
|
|
S = c 11 х11+ c 12 х12+ c 13 х13+ c 14 х14+ c 15 х15+ ... + c 41 х41+ c 42 х42+ c 43 х43+ c 44 х44+ c 45 х45.
Дата добавления: 2018-10-26; просмотров: 180; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!