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

Содержание

Введение

1. Теоретический материал

1.1 Математическая формулировка задачи линейного программирования

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

2. Постановка задачи

3. Решение поставленной задачи

4. Алгоритм программы

5. Программа для общего случая

6. Результаты работы программы

Заключение

Список использованных источников

Введение

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

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

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

Общее в моделях то, что во всех случаях модель в определённом смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования.

Модель – это материальный или идеальный объект, который строится для изучения исходного объекта (оригинала) и который отражает наиболее важные качества и параметры оригинала.

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

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

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

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

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

В моделировании существует два пути:

Модель может быть похожей копией объекта, выполненной из другого материала и в другом масштабе, с отсутствием ряда деталей;

Модель может отражать реальность более абстрактно-словесным описанием, формализованным по каким-то правилам, соотношениям.

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

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

1. Теоретический материал

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

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

1.1 Математическая формулировка задачи линейного программирования

Нужно определить максимум линейной целевой функции (линейной формы):

F(x)=∑c_>j>x_>j>=c_>1>x_>1>+c_>2>x_>2>+…+c_>n>x_>n>_>,> j=(1,n), (1)

при условиях:

∑ a_>ij>x_>j>≤b_>i>, i=1,2,…,m (2)

Иногда на x_>i> также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).Такую задачу называют «основной» или «стандартной» в линейном программировании.

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

Задача ЛП в общем виде может быть записана так:

(c, x) − max

Ax = b,

где c =(c_>1>,c_>2>,...,c_>n>)^T – мерный вектор-столбец коэффициентов; x =(x_>1>,x2,...,xn)^T – мерный вектор-столбец неизвестных; A =(a_>ij>),m × n – матрица коэффициентов; B =(b_>1>,b_>2>,...,b_>m>) – вектор-столбец коэффициентов.

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

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

F(x)=c_>1>x_>1>+c_>2>x_>2>+...+c_>n>x_>n> ->max(min)

a_>11>x_>1>+a_>12>x_>2>+...+a_>1n>x_>n>+х_{>
n +1}>= b_>1>

a_>21>x_>1>+a_>22>x_>2>+...+a_>2n>x_>n>+х_{>
n +2}>= b_>2> (3)

_>.>......................

a_>m1>x_>1>+a_>m2>x_>2>+...+a_>mn>x_>n>+х_{>
n +т}>= b_>m>

x_>i>≥0 (i=1..n),

где F(x) – целевая функция; х_>1>,_>>х_>2>,…,_>>х_>n>_>>– базисные переменные; остальные переменные называются свободными.

Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам.

Таблица 1 – Система ограничений и целевая функция

Базисные переменные	Свободные члены	X _>1>	X _>2>	…	X _>n>	X _>n+1>	X _>n+2>	…	X_>n+m>
X _>n+1>	b_>1>	a_> 11>	a_> 12>	…	a_> 1n>	1	0	…	0
X _>n+2>	b_>2>	a_> 21>	a_> 22>	…	a_> 2n>	0	1	…	0
…	…	…	…	…	…	…	…	…	…
X _>n+m>	b_> m>	a_> m1>	a_> m2>	…	a_> mn>	0	0	…	1
F(x)	0	-c_>1>	-c_>2>	…	-c_>n>	0	0	…	0

Рассмотрим алгоритм перехода к следующим симплекс-таблицам:

1. Выбираем ключевой столбец. Это столбец соответствующий минимально отрицательному (максимально положительному) элементу последней (индексной) строке:

Если отрицательных элементов в индексной строке нет, то план оптимальный.

2. В ключевом столбце выбираются положительные коэффициенты, если таких нет, то задача не имеет решений;

3. Выбираем ключевую строку:

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

Ключевой элемент – это элемент, стоящий на пересечении ключевого столбца и ключевой строки;

4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;

5. В новой таблице:

5.1 Все элементы ключевой строки делятся на ключевой элемент.

5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.

5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.

5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.

5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.

6. Переход к шагу 1.

Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.

2. Постановка задачи

Для изготовления изделий двух видов склад может отпустить металла не более 150 кг, причем на изделие первого вида расходуется пять килограмм, а на изделие второго вида три килограмма. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий первого вида требуется изготовить не более 20 штук, а изделий второго вида не более 25 штук, причем одно изделие первого вида стоит 7 руб., а изделие второго вида стоит 8 руб.

3. Решение поставленной задачи

x_>1> – количество изделий первого вида.

x_>2> – количество изделий второго вида.

F(x) – целевая функция.

5x_>1>+ 3x_>2>=150

x_>1>20

x_>2>25

x1, x2≥0

F(x) = 7x_>1>+8x_>2> max

Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:

5x_>1>+ 3x_>2>+x_>3>=150

x_>1>+x_>4>=20

x_>2>+x_>5>=25

x1, x2, x3, x4, x5≥0

F(x)= 7x_>1>+8x_>2>+x_>3>+x_>4>+x_>5>

x_>3,> x_>4,> x_>5>– базисные переменные; x_>1,> x_>2>– свободные переменные.

Составим симплекс – таблицу, соответствующую каноническому виду:

Таблица 2 – Итерация 1

Базис	Свободные чл.	X _>1>	X _>2>	X _>3>	X _>4>	X _>5>
X _>3>	150	5	3	1	0	0
X _>4>	20	1	0	0	1	0
X _>5>	25	0	1	0	0	1
F(x)	0	-7	-8	0	0	0

Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае – это -8. Из этого следует, что столбец х2 становится ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из полученных делений выбираем минимальное, у нас это будет 25. То есть строка, в которой получилось минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.

Строим новую таблицу, следуя алгоритму, приведенному выше.

Таблица 3 – Итерация 2

Базис	Свободные	X _>1>	X _>2>	X _>3>	X _>4>	X _>5>
X _>3>	75	5	0	1	0	-3
X _>4>	20	1	0	0	1	0
X _>2>	25	0	1	0	0	1
F(x)	200	-7	0	0	0	8

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

Таблица 4 – Итерация 3

Базис	Свободные	X _>1>	X _>2>	X _>3>	X _>4>	X _>5>
X _>1>	15	1	0	0,2	0	-0,6
X _>4>	5	0	0	-0,2	1	0,6
X _>2>	25	0	1	0	0	1
F(x)	305	0	0	1,4	0	3,8

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

X _>1>=15; X _>2>=25; F_>max>=305.

Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день.

4. Алгоритм программы

Блок-схема симплекс-метода

Вычислительная процедура симплекс-метода является итерационным процессом. Если задача содержит несколько переменных и ограничений, то этот процесс очень громоздок. Во многие практические задачи входят десятки переменных и ограничений (иногда намного больше), и ясно, что неразумно решать эти задачи вручную. Симплекс-метод – это метод для электронно-вычислительных машин. Не случайно развитие теории линейного программирования совпало по времени с развитием электронно-вычислительных машин. Без них теория имела бы весьма узкую область приложений.

5. Программа для общего случая

#include ”stdafx.h”

#include ”iostream”

#include “locale”

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{ int a,b,d,stl,str,baz[10],f,g=0,i,j,l=0,q=0,z=0,y=0,xx,z1[10];

float m,tab[10][10],min=1000,c[10],tab1[10][10],x=1000;

setlocale(LC_ALL, ”russian”);

cout<<“Введите количество строк и столбцов”<<endl;

cin>>a>>b;

//заполнение начальной матрицы

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

{

for (j=0;j<b;j++)

{cout<<”Введите [”<<i<<”][”<<j<<“] элемент таблицы”<<endl;

cin>>tab[i][j];

}}

cout<<”первая итерация”<<endl;

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

{

for (j=0;j<b;j++){cout<<tab[i][j]<<" ";}cout<<endl;}

//проверка на оптимальность

l=0;

for (i=0;i<b;i++){

if (tab[a-1][i]<0) {l=l+1;}}

if (l==0){

for (j=1;j<b-a+1;j++){

int kol=0,nol=0,ind;

for (i=0;i<a-1;i++){

if (tab[i][j]==1) {kol++;ind=i;}

else nol++;

}

if ((kol==1) && (a-nol==2))

cout<<”x=”<<j<<”=”<<tab[ind][0]<<endl;

}cout<<”Решение оптимально”<<endl;

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

{ for (j=0;j<b;j++)

{cout<<tab[i][j]<< ” “;}cout<<endl;}

cout<<”F(x)=”<<tab[a-1][0];

return 0;}

x=1000;

//поиск ключевого столбца

for (i=1;i<b;i++)

{ if (tab[a-1][i]<=x)

{x=tab[a-1][i];

stl=i;

}}

//поиск ключевой строки

for (j=0;j<a-1;j++)

{ if (tab[j][stl]>0)

c[j]=tab[j][0]/tab[j][stl];

else

c[j]=1000;}

cout<<endl;

cout<<”Массив для нахождения ключевой строки”<<endl;

for (j=0;j<a-1;j++){

cout<<c[j]<< “ “;

}

cout<<endl;

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

if (c[i]<min){

min=c[i];

str=i;

}

cout<<endl;

cout<<”Kлючевой столбец и ключевая строка”<<endl;

cout<<stl<<” ”<<str<<” “<<endl;

cout<<endl;

cout<<“Ключевой элемент:”<<tab[str][stl]<<endl;

cout<<endl;

//пересчет новой таблицы

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

{ for (j=0;j<b;j++)

{tab1[i][j]=tab[i][j]-(tab[i][stl]*tab[str][j]/tab[str][stl]);

tab1[i][stl]=0;

tab1[str][stl]=1;

tab1[str][j]=tab[str][j]/tab[str][stl];

}}

//переприсвоенние матриц и вывод их на экран

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

{ for (j=0;j<b;j++)

{ tab[i][j]=tab1[i][j];

}}

goto k;

return 0;

}

6. Результаты работы программы

Введите количество строк и столбцов

Введите [0][0] элемент таблицы

150

Введите [0][1] элемент таблицы

Введите [0][2] элемент таблицы

Введите [0][3] элемент таблицы

Введите [0][4] элемент таблицы

Введите [0][5] элемент таблицы

Введите [1][0] элемент таблицы

-7

Введите [1][0] элемент таблицы

-8

Введите [1][0] элемент таблицы

Первая итерация

150 5 3 1 0 0

20 1 0 0 1 0

25 0 1 0 0 1

0 -7 -8 0 0 0

Массив для нахождения ключевой строки

50 1000 25

Ключевой столбец и ключевая строка

2 2

Ключевой элемент:1

Массив для нахождения ключевой строки

15 20 1000

Ключевой столбец и ключевая строка

1 0

Ключевой элемент:5

Решение оптимально!

х1=15

х2=25

F(x)=305

15 1 0 0.2 0 -0.6

5 0 0 -0.2 1 0.6

25 0 1 0 0 1

305 0 0 1.4 0 3.8

Заключение

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

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

Он основан на пересчёте коэффициентов в системе уравнений и целевой функции при перемене мест свободной и базисной переменных можно формализовать и свести к преобразованию симплекс-таблицы.

Симплекс-метод является вычислительной процедурой представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме.

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

Список использованных источников

Ашихмин В.Н. «Введение в математическое моделирование». Москва: Логос, 2005.

Банди Б. «Основы линейного программирования». Москва: Радио и связь, 1989.

Большакова И.В. «Линейное программирование». Минск: БНТУ, 2004.

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

1.1 Математическая формулировка задачи линейного программирования

Свободные чл.

Свободные

Свободные

Заключение