Конспект лекций по предмету "Модели и методы"

Course-Work.ru Решения задач линейного программирования , Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения...
Узнать цену дипломной по вашей теме


Конспект лекций Решения задач линейного программирования

Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный недостаток состоит в том, что в отличие от графических методов, они недостаточно наглядны. Графические методы очень наглядны, но они пригодны лишь для решения задач на плоскости, т.е. когда размерность пространства К=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;

î6x=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). Многоугольник ОДР обладает весьма важным свойством: он является выпуклым.









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



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


Не сдавайте скачаную работу преподавателю!
Данную дипломную работу Вы можете использовать как базу для самостоятельного написания выпускного проекта.

Доработать Узнать цену работы по вашей теме

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

 
Пишем работу самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.