50354 (Решение задач линейного программирования симплекс-методом), страница 2
Описание файла
Документ из архива "Решение задач линейного программирования симплекс-методом", который расположен в категории "". Всё это находится в предмете "информатика" из 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 Целью курсового проекта было решение задач линейного программирования симплекс-методом, составление алгоритма, составление программы по алгоритму и вывод результата на экран. Для нахождения оптимального решения можно пойти наиболее простым способом с точки зрения лица, которое непосредственно производит решение задачи. Для более быстрого решения задачи можно воспользоваться языками программирования, что приведет к более быстрому решению задачи. Он основан на пересчёте коэффициентов в системе уравнений и целевой функции при перемене мест свободной и базисной переменных можно формализовать и свести к преобразованию симплекс-таблицы. Симплекс-метод является вычислительной процедурой представленной в алгебраической форме. Он непосредственно применяется к общей задаче линейного программирования в стандартной форме. В данном проекте был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль. Список использованных источников Ашихмин В.Н. «Введение в математическое моделирование». Москва: Логос, 2005. Банди Б. «Основы линейного программирования». Москва: Радио и связь, 1989. Большакова И.В. «Линейное программирование». Минск: БНТУ, 2004. Размещено на Allbest.ru
Заключение
