Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Решения задач линейного программирования





Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный недостаток состоит в том, что в отличие от графических методов, они недостаточно наглядны. Графические методы очень наглядны, но они пригодны лишь для решения задач на плоскости, т.е. когда размерность пространства К=2. Однако, учитывая большую наглядность графических методов, с их помощью рассмотрим идею решения задачи ЛП на примере задачи распределения ресурсов.

Однако прежде чем заняться решением, сделаем некоторые замечания. Пусть мы имеем систему m уравнения с n неизвестными (I).

 

Возможны следующие варианты:

 Число неизвестных меньше, чем число уравнений n < m.

например: ì2x1=4, в этом случае n =1;

x1=5, тогда m =2 (число линейно независимых уравнений). (4.4)

Очевидно, что система (4.4) решения не имеет, и она несовместна;

 Число неизвестных равно числу уравнений n=m.

В этом случае система имеет единственное решение или не имеет ни одного. Заметим, что m равно числу линейно независимых уравнений.

Для системы: ì2x=10, n =1, m =1;

 x=30.

 Если число неизвестных больше числа уравнений, то система имеет бесчисленное множество решений. Пусть n > m. Например:

2x1+x2=2 (4.5)

 

Очевидно, что это уравнение прямой, и все значения x1 и x2, лежащие на этой прямой, являются решением уравнения (4.2). Значит уравнение (4.5) имеет бесчисленное множество решений.

 

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

 

a1x1+a2x2=b (4.6)

 

Преобразуем его к виду:

(4.7)

Запись (4.7) называют уравнением прямой в отрезках, что изображено на Рис. 4.1. Рассмотрим еще одну форму представления уравнения (4.6). Запишем это уравнение в виде:

 

a2x2=b-a1x1

или

 

или

x2=F-kx1 (4.8)

 

Уравнение (4.8) изображено на рис. 4.2.

 

 

Вспомним неравенства. Если линейное уравнение с двумя переменными может быть представлено в виде прямой на плоскости, то неравенство вида:

a1x1+a2x2£ b (4.9)

изображается как полуплоскость, показанная на рис. 4.1. На этом рисунке часть плоскости, удовлетворяющая неравенству, заштрихована. Координаты всех точек, принадлежащих заштрихованному участку, имеют такие значения x1 и x2, которые удовлетворяют заданному неравенству. Значит, эти значения составляют область допустимых решений (ОДР). Саму прямую считаем принадлежащей каждой из двух указанных полуплоскостей. Предположим теперь, что задано не одно неравенство, а система:

 

а11x1+а12x2 £ b1

 а21x1+а22x2 £ b2

(4.10) í............

 аm1x1+аm2x2 £ bm,

где первое неравенство определяет некоторую полуплоскость П1, второе - полуплоскость П2 и т.д.

 

если какая-либо пара чисел (x1, x2) удовлетворяет всем неравенствам (4.10), то, соответствующая точка Р(x1, x2), принадлежит всем полуплоскостям П1, П2,... Пm одновременно. Другими словами, точка Р принадлежит пересечению (общей части) полуплоскостей П1, П2,... Пm, т.е. некоторой многоугольной области М (Рис. 4.3), которая является ОДР. Вдоль контура области изображены штрихи, идущие внутрь области. Они одновременно указывают, с какой стороны от данной прямой лежит соответствующая полуплоскость, то же самое указано и с помощью стрелок на каждой линии. Сразу же отметим, что ОДР не всегда бывает, ограничена: в результате пересечения нескольких полуплоскостей может возникнуть и неограниченная область (Рис. 4.4). Возможен и случай, когда область допустимых решений (ОДР) пуста. Это означает, что система (5.7) противоречива (Рис. 4.5). Многоугольник ОДР обладает весьма важным свойством: он является выпуклым.

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

В случае трех неизвестных, каждое уравнение представляет собой плоскость в пространстве. Каждая плоскость разбивает все пространство на два полупространства. Система неравенств определяет в пространстве выпуклый объемный многогранник, который представляет ОДР.

Date: 2015-06-11; view: 417; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию