50354 (Решение задач линейного программирования симплекс-методом), страница 2

2016-07-30СтудИзба

Описание файла

Документ из архива "Решение задач линейного программирования симплекс-методом", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "50354"

Текст 2 страницы из документа "50354"

x3, x4, x5 – базисные переменные; x1, x2 – свободные переменные.

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

Таблица 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; Fmax=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<<“Введите количество строк и столбцов”<

cin>>a>>b;

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

for (i=0;i

{

for (j=0;j

{cout<<”Введите [”<

cin>>tab[i][j];

}}

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

for (i=0;i

{

for (j=0;j

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

k:

l=0;

for (i=0;i

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

if (l==0){

for (j=1;j

int kol=0,nol=0,ind;

for (i=0;i

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

else nol++;

}

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

cout<<”x=”<

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

for (i=0;i

{ for (j=0;j

{cout<

cout<<”F(x)=”<

return 0;}

x=1000;

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

for (i=1;i

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

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

stl=i;

}}

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

for (j=0;j

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

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

else

c[j]=1000;}

cout<

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

for (j=0;j

cout<

}

cout<

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

if (c[i]

min=c[i];

str=i;

}

cout<

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

cout<

cout<

cout<<“Ключевой элемент:”<

cout<

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

for (i=0;i

{ for (j=0;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

{ for (j=0;j

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

}}

goto k;

return 0;

}

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

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

4

6

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

150

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

5

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

3

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

1

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

0

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

0

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

20

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

1

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

0

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

0

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

1

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

0

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

25

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

0

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

1

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

0

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

0

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

1

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

0

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

-7

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

-8

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

0

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

0

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

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


Заключение

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4098
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее