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

 

 

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

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

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

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

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

 

 

 

 

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

 

 

 

 

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

 

 

 

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

 

студента 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

Таблица 1. –Пример симплекс-таблицы 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Для практической реализации я выбрал программную  среду С++ builder, так как в ней довольно не сложно реализовать нашу задачу, он гибок в использовании и в дальнейшем, если будет интерес, возможно будет реализовать графический интерфейс.

Borland  C++  Builder  6 – очередная версия системы объектно – ориентированного  программирования  для 32-разрядных операционных  систем  Microsoft Windows. Интегрированная среда системы (Integrated  Development  Environment, IDE)  обеспечивает  продуктивность  многократного использования визуальных  компонентов в сочетании с усовершенствованными  инструментами и разномасштабными  средствами  доступа к базам данных.  Основное  предназначение  IDE – радикально  ускорит производительный  цикл  разработки  сложнейших  программных проектов  для различных областей  применения.

Стандарты пользовательских  интерфейсов  меняются  и  развиваются  также  быстро,  как  и  операционные  системы.  Открытость  среды  IDE  позволяет настраивать ее  с учетом  наиболее   модных  тенденций в области графических интерфейсов.  Разработчик имеет перед глазами хороший образец того,  что можно сделать в смысле  построения  пользовательского интерфейса.  На  самом деле  среда IDE  создана с помощью C++  Builder,  поэтому все,  что вы  видите  на  экране,  вы  сможете сделать сами.  Визуальный  интерфейс сочетает  в себе  простоту  использования для новичка и богатство возможности для профессионала. 

Среди  множества  нововведений  следует  особо  отметить  эффективность  средства  для  поддержки  web – служб и разработки  переносимых проектов.  Технологии  DataSnap,  WebServices  и WebSnap дают  возможность быстро  и легко создать и интегрировать сетевые приложения  (как персональные,  так и коллективные).  Клиентские  и серверный  модули  распределенного приложения 

обмениваются  XML – илиWSDL – документами в рамках  транспортных  протоколов  TCP/IP,  HTTP, SOAP. Библиотека  компонентов CLX  обеспечивает  переносимость исполняемого  кода  между платформами Windows  и Linux.  CLX – приложения  совместимы  на  уровне  языка С++  с программными  продуктами,  которые корпорация  Borland  планирует выпускать для операционной  системы Linux.

Система C++  Builder  может быть  использованы  везде,  где требуется дополнить существующие  приложения  (как прикладные,  так и системные)  расширенным стандартом  языка С++,  повысить  быстродействие  и надежность  программ,  придать пользовательскому интерфейсу  качество  профессионального уровня.

 

Для  установки  системы  необходим  персональный  компьютер  в  следующей  конфигурации:

• Процессор  Intel  Pentium  с тактовой  частотой  не  ниже  166  МГц;
• Операционная  система  Microsoft  Windows  98/  Millennium  (Me)/  NT/  2000/  XP;
• Оперативная  память  не  менее  128 Мбайт, рекомендуется  256 Мбайт;
• До  750  Мбайт  свободного  пространства  на  жестком  доске,  в  зависимости  от  выбранных  параметров  установки;
• Дисковод  для  компакт – дисков;
• Видеоадаптер  с  разрешением  не  хуже,  чем  в  стандарте  SVGA;
• Сетевой  адаптер;
• Мышь  или  другой  координатный  манипулятор.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Для начала нам надо ввести размерность нашей симплекс таблицы, за N мы возьмем количество переменных, за M количество условий. Так же добавим строчку для целевой функции.

Далее мы определяем для условий какой  знак будет(больше или меньше).

Создаем цикл в котором мы будем  производить  количество тестов( k=500 ).

В цикле  заполняем нашу будущую симплекс таблицу случайными числами от (60;-60).

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

Если  это условие выполняется то мы плюсуем переменную z.

По окончанию  всех тестов (k), мы выводим ответ в процентах (z*100/k) . Этот процент и будет нашей вероятностью существования решения задачи линейного программирования.

Листинг программы с комментариями предоставлен  в Приложении 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

Все это  видно на рисунке 1.

 

Рисунок 1 – скриншоты работы программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

В конце  выдается процент вероятности существования  решения при заданных нами условиями.

 

 

 

 

 

 

 

 

 

Рисунок 2 – скриншот работы программы.

 

 

На рис. 2 , мы видим созданную симплекс таблицу.

Первые 3 строки это условия, последняя строка это целевая функция.

Первый  столбец это свободные члены  наших условий и целевой функции.

Последняя надпись это есть наша вероятность  существования решения задачи линейного  программирования в процентах.

 

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

Возьмем условия и целевую функцию  из нашего скриншота программы.

F = -35x₁+9x₂ → min, при системе ограничений (11):

                                    2x₁+x₂ <= 21

                                     57x₁+52x₂=>14                                                                               (11)

                                     55x₁+ 59x₂=>42

 

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

 

 

 

   График 1. – 1 пример

 

По графику  мы видим, что задача не имеет допустимых решений. ОДР представляет собой пустое множество.

 

Для проверки условия когда у нас все же есть решение, мы опять же возьмем симплекс таблицу из нашего 2ого скриншота программы.

 

F = -35x₁+9x₂ → min, при системе ограничений (12):

 

                                    38x₁+35x₂ <= 57

                                    26x₁-3x₂ => 20                                                                                  (12)

                                    18x₁+57x₂ => 22

 

 

 

 

 

График 2.- 2 пример.

 

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

 

 

 

 

 

 

 

 

 

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

 

Для того чтобы найти зависимость, я провел несколько тестов, с разными размерностями симплекс таблиц.

Результаты  этих тестов отображаются в таблицах.

В первой строке это размеренность симплекс таблицы.( количество переменных на количество условий).

Во второй строке результаты, процент вероятности  существование решения ЗЛП.

 

Таблица 2.1

2х1	2х2	2х3	2х4	2х5
82.2 %	75.2 %	68.2 %	66 %	65.8 %

 

Таблица 2.2

3х1	3х2	3х3	3х4	3х5
78.6 %	64.4 %	57.6 %	54.6 %	52.6 %

 

Таблица 2.3

4х1	4х2	4х3	4х4	4х5
69.9 %	60.4 %	50.2 %	45 %	40.2 %

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Листинг программы с комментариями

 

#include <iostream.h>

#include <math.h>

#include <windows.h>

#include <conio.h>

#include <stdlib.h>

 

char* Rus(const char* text);

char bufRus[256];

 

char* Rus(const char* text)

{

      CharToOem(text, bufRus);

      return bufRus;

}

 

main()

{

start: double A[100][100];

int i, j, q, s, N, M, I, J, x, yslovie, target,k=50,o=0,r=0,l,h;   // k - колличество раз прогона цикла

float t=0,z=0;

 

 

cout<<Rus("Введите количество переменных: ");

cin>>N;

cout<<Rus("Теперь введите количество условий: ");

cin>>M;

J=N+M+2; // основные переменные + добав. переменн. + свободный член + оценочные соотношения

I=M+1; // добаляем еще одну строку для целевой функции

 

 

 

 

         x=N;//переменная чтобы выставлять коэффиценты (по диагонали) 1 или -1 для добавочных переменных

for (i=0; i<I-1; i++)

{

x++;

cout<<i+1<<Rus("-е условие больше или меньше? (1/0) ");

cin>>yslovie;

//если  знак "больше", то кооф. доб. переменной поменять знак на добавочной переменной

for (j=x;j<=x; j++)

{

if (yslovie==1)

A[i][j]=-1;

else

A[i][j]=1;

}

}

 

 

 

  for (t = 1; t <= k ; t++)        // Цикл

 

  {

 

 

 

for (i=0; i<I; i++)                                // генерация случайных чисел для свободных членов

 {A[i][0]=random(90)-30;

 

  }

 

 

 

        for (i=0; i<I; i++)                                  // генерация случайных чисел для коэфициентов

{for (j=1;j<=N;j++)

   A[i][j]=random(90)-30;

}

 

for (j=1; j<=N;j++)

A[I-1][j]=-1*A[I-1][j];//меняем знак для целевой функции

 

 

 

//проверка  на возможность решения    при выборе минимума

 

l=0;                              // счетчик

for (i=0; i<I-1; i++)

{if (A[i][0]<0) {l=1; break;}}

if (l==0) {z=z+1; cout<<Rus("Решение есть"); goto end;}  // если   столбец положительный

 

 

r=0;

h=0;

for (i=0; i<I; i++)

{

   if (A[i][0]<0) {o=i; h=h+1;

 

   for (j=1;j<=N;j++)

   if (A[o][j]<0) {(r=r+1);break;}

                           }

 

                         }

  if (r==h) cout<<Rus("Решение есть"); else {cout<<Rus("Нет решениея");