Исследование задачи линейного программирования. Общий случай

 

 

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального  образования

Петрозаводский  государственный университет

Кольский  филиал

 

 

 

 

Кафедра Автоматизированные системы обработки информации и управления

 

 

 

 

Исследование задачи линейного программирования. Общий случай.

 

 

 

Курсовая  работа

 

студента 4 курса (гр. 2)

очного  отделения

факультета  ИПМ

специальность 230102 - Автоматизированные системы обработки информации и управления

 

Пашникова Владимира Вячеславовича  

 

 

Научный руководитель:

к.т.н., доцент Степенщиков Д.Г. 

 

 

 

 

Оценка публичной  защиты работы:

 

 

 

 

 

 

Апатиты

2013

 

 

Оглавление

 

ВВЕДЕНИЕ 3

1. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5

1.1 Метод Монте-Карло 5

1.2 Симплекс  метод 7

1.3 Алгоритм  поиска возможности решения задачи  линейного программирования 9

2. ВЫЧИСЛЕНИЕ ВЕРОЯТНИСТИ НАЛИЧИЯ РЕШЕНИЯ 11

2.1 Блок схема  будущей программы 11

2.2. Обоснование  выбора языка программирования 13

2.3 Реализация  программы на c++ builder 2006 15

2.4 Проверка  работы  программы 16

2.5 Поиск зависимости от количества условий и переменных 20

Заключение 21

Список использованной литературы 21

Приложение 1. 22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

Что же такое  линейное программирование? Это один из первых и наиболее подробно изученных  разделов математического программирования. Именно линейное программирование явилось  тем разделом, с которого начала развиваться сама дисциплина «математическое  программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения.

Кратко  ознакомимся с основными понятиями  линейного программирования.

Линейное  программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множестве n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Общей(стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции(линейной формы) вида (1): 

                                                                      (1)

 

Задача в которой фигурируют ограничения в форме неравенств, называется – основной задачей линейного программирования(ОЗЛП).

 

                                                                                              (2)

                                       

 

Задача  линейного программирования будет  иметь канонический вид, если в общей  задаче вместо первой системы неравенств имеет место система уравнений  с ограничениями в форме равенства (3):

 

                                                                                           (3)

 

Основную  задачу можно свести к канонической путем введения дополнительных переменных.

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

Легко заметить, что задачу нахождения максимума  можно заменить задачей нахождения минимума, взяв коэффициенты   с обратным знаком.

Целью моей курсовой является поиск зависимости  от набора условий и количества переменных  существования  решения задачи линейного  программирования.

В работе мы будем исследовать вероятность  наличия решения в общем случае.

Для поиска этой зависимости я воспользовался численным Методом Монте-Карло.

Методы  Монте-Карло – это численные  методы решения математических задач (систем  алгебраических, дифференциальных, интегральных уравнений)  и  прямое статистическое моделирование (физических, химических, биологических, экономических, социальных процессов) при помощи получения и преобразования случайных чисел.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1 Метод Монте-Карло

 

Исследование  существования решения ЗЛП будет заключаться в следующем.

Нам необходимо будет выяснить, как зависит вероятность  наличия решения от количества переменных и условий. Элементы переменных и коэффициентов будут случайными вещественными числами. Нужно узнать какова будет эта вероятность для 2х2, 3х3,4х4 при некотором количестве тестов. Для решения необходима программная реализация, т.е. надо написать программу, которая при заданном количестве переменных и условий будет считать вероятность наличия решения в ЗЛП. Ниже опишем более подробное решение нашей задачи.

Возьмем некоторое количество условий и  переменных целевой функции. Элементы переменных и коэффициентов –  случайные вещественные числа. Чтобы  найти зависимость наличия решения  ЗЛП, именно от количества переменных и условий, а не от ее элементов  мы воспользуемся методом Монте-Карло  – численным методом решения  математических задач при помощи моделирования случайных величин. В самом общем виде схема метода Монте-Карло выглядит так.

 

Пусть нам  требуется вычислить некоторую  величину I. Предполагается, что можно построить случайную величину Ω с математическим ожиданием EΩ, равным I, и с конечной дисперсией DΩ, причем выборочные значения Ω_j случайной величины Ω достаточно просто реализуются на компьютере. Построив большое количество n выборочных значений Ω₁,…,Ω_n, на основе закона больших чисел получаем приближение искомой величины (4):

 

                                                                                                              (4)                                             

                                                                                                                        

Рассмотрим, как метод Монте-Карло реализуется  в нашей задаче.

Матрицу получившуюся при генерации количества переменных и условий, элементы которой случайные вещественные числа, сгенерируем t количество раз. Т.е. получаем t матриц, сгенерированных случайным образом. Если каждую сгенерированную матрицу проверить на наличие решения ЗЛП, то получим некоторое количество матриц, имеющих ее. Обозначим их буквой z. Далее, мы считаем, какой процент p занимают матрицы z, имеющие решение ЗЛП, от общего числа матриц (5):

 

                                                                                                                             (5)

 

Этот  процент и будет вероятностью наличия решения ЗЛП в  нашей матрице. Метод Монте-Карло в нашей задаче реализуется в множественном генерировании матриц случайным образом, и благодаря этому мы получаем вероятность t наличия решения ЗЛП, имея в качестве исходных данных лишь количество условий и переменных. Однако, точность этого метода зависит от числа сгенерированных матриц. Чем больше число сгенерированных матриц – тем точнее результаты. Понятно, что генерация матриц вручную – весьма трудоемкий процесс. Поэтому нам и необходимо написать программу, которая будет генерировать эти матрицы в достаточно большом количестве, проверять их на наличие решения ЗЛП, и считать вероятности наличия возможности решения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2 Симплекс метод

 

Для решения  нашей задачи воспользуемся симплекс-методом.

Симплексный метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором  значение целевой функции возрастает (при условии, что данная задача имеет  оптимальный план, и каждый ее опорный  план является невырожденным). Указанный  переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно  непосредственно записать.

Пусть дана функция (6), для которой необходимо найти наибольшее или наименьшее значение, если значения всех неизвестных неотрицательные.

 

                                 ƒ = C₀ + C₁x₁ + C₂x₂ +...+ C_nx_n                                                                   (6)

 

и система m линейных уравнений с n неизвестными. Это называется системой ограничений:

                                       a₁₁x₁ + a₁₂x₂ +...+ a_1nx_n = b₁

                                       a₂₁x₁ + a₁₂x₂ +...+ a_2nx_n = b₂                                                               (7)

                                         ...

                                        a_m1x₁ +a_m2x₁₂ +...+ a_mnx_n = b_m

 

 

Целевую функцию представим в виде (8):

 

                                ƒ - C₁x₁-C₂x₂ -...-C_nx_n = C₀                                                                            (8)

 

Составим  симплекс-таблицу.В дальнейшем будем считать, что ранг матрицы системы ограничений равен r.В системе ограничений выбран базис(основные неизвестные)x₁,x₂,...x_n и коэффициенты в правой части не отрицательны.

В этом случае система ограничений будет иметь  вид (9):

                                            x₁ +...+ a_1,r+1x_r+1 +...+ a_1nx_n = b₁

                                           x₂+ a_2,r+1x_r+1 +...+ a_2nx_n = b₂                                                                                (9)

                                                               …

                                            x_r+ a_r,r+1x_r+1 +...+ a_rnx_n = b_r

 

Тогда целевая  функция имеет вид (10):

 

 

                                 ƒ + C_r+1x_r+1 + C_r+2x_r+2 -...- C_nx_n = C₀                                                         (10)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.3 Алгоритм поиска возможности решения задачи линейного программирования  

 

Симплекс-метод  подразумевает последовательный перебор  всех вершин области допустимых значений с целью нахождения той вершины, где функция принимает экстремальное  значение. На первом этапе находится  какое-нибудь решение, которое улучшается на каждом последующем шаге. Такое  решение называется базисным. 
 
    Первый шаг. В составленной таблице сначала необходимо просмотреть столбец со свободными членами. Если в нем имеются отрицательные элементы, то необходимо осуществить переход ко второму шагу. 
   
    Второй шаг. На втором шаге необходимо определиться, какую переменную исключить из базиса, а какую включить, для того, что бы произвести перерасчет симплекс-таблицы. Для этого просматриваем столбец со свободными членами и находим в нем отрицательный элемент. Строка с отрицательным элементом будет называться ведущей. В ней находим максимальный по модулю отрицательный элемент, соответствующий ему - 
столбец - ведомый. Если же среди свободных членов есть отрицательные значения, а в соответствующей строке нет, то такая таблица не будет иметь решений. Переменная в ведущей строке, находящаяся в столбце свободных членов исключается из базиса, а переменная, соответствующая ведущему столбцу включается в базис. В Таблице 1 приведен пример симплекс-таблицы. 

 

 

 

 

 

 

 

 

 

 

Базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x1	x2	xl	xn
xn+1	b1	a11	a12	a1l	a1n
xn+2	b2	a21	a22	a2l	a2n
…	…	…	…	…	…
…	…	…	…	…	…
xn+r	b2	ar1	ar2	arl	arn
…	…	…	…	…	…
…	…	…	…	…	…
xn+m	bm	am1	am2	aml	amn
F(x)max	F0	-c1	-c2	c1	-cn