Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математический факультет
Кафедра математического обеспечения информационных систем
Отчет
по лабораторной работе № 3
по дисциплине «Методы оптимизации»
Решение задач линейного программирования симплекс – методом
| Руководитель:______Луговскова Ю.П. «___»_______________________2010 г. Исполнитель: студент гр. 08МОС(у) ___________________Ледовского А.С. «___»_______________________2010 г.
|
Оренбург 2010
Постановка задачи:
Найти максимум функции
При ограничениях
Дана функция:
Графический метод:
Точка максимума является (0;7)
Значение функции в данной точке = (0*(-1)+1*7) = 7
Симплекс – метод
Приведём данную функцию к каноническому виду
Матрица A =
Б={ }
0 x3 2 1.00 -1.00 1.00 0.00 2.00
0 x4 7 2.00 1.00 0.00 1.00 2.00
--------------------------------------------
-1.00 1.00 0.00 0.00
-2.00 -1.00 1.00 -1.00 -0.00
--------------------------------------------
-1 x1 -2 -1.00 1.00 -1.00 -0.00 -2.00
0 x4 9 3.00 0.00 1.00 1.00 -2.00
--------------------------------------------
-2.00 2.00 -1.00 0.00
-2.00 -1.00 1.00 -1.00 -0.00
--------------------------------------------
1 x2 -2 -1.00 1.00 -1.00 -0.00 9.00
0 x4 9 3.00 0.00 1.00 1.00 9.00
--------------------------------------------
0.00 0.00 1.00 0.00
9.00 3.00 0.00 1.00 1.00
--------------------------------------------
1 x2 7 2.00 1.00 0.00 1.00
0 x3 9 3.00 0.00 1.00 1.00
-3.00 0.00 0.00 -1.00
б.п. {0 7 9 0 }
(.)max = (0;7)
function(.)max = 7
Код программы:
// lab3.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int n=4;
const int nn=2;
double A[2][n];
double A1[2][n];
int bp[2];
double Y0[2];
double mini;
double delta[n];
double e[n+1];
double C[4];
int bp_[n];
int maxi(double mas[n])
{
double mm=-1000;
int no;
for (int i=0;i<n;i++)
{
if (mas[i]>mm) {mm=mas[i];no=i;}
}
return no;
}
bool exitt(double mas[n])
{
for (int i=0;i<n;i++)
{
if (mas[i]>0.001) {return 0;}
}
return 1;
}
bool neogr(double mas[nn][n])
{
int k=0;
for (int i=0;i<nn;i++)
{
k=0;
for (int j=0;j<n;j++)
{
if (mas[i][j]<1) {k++;}
}
if (k==n) return true;
}
return false;
}
int bp_free()
{
for (int i=0;i<n;i++)
{
if (bp_[i]==0) return i;
}
cout << "konec!!!"<<endl;
for (int i=0;i<n;i++)
{bp_[i]=0;}
return 0;
}
void update(double mas[nn][n],double mas1[nn][n])
{
for (int i=0;i<nn;i++)
for (int j=0;j<n;j++)
{mas[i][j]=mas1[i][j];}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin >> C[0];
cin >> C[1];
C[2]=0;
C[3]=0;
// считали матрицу А
for (int i=0;i<nn;i++)
{
for (int j=0;j<n;j++)
{cin >> A[i][j];bp_[j]=0;}
cin >> Y0[i];
}
bp[0]=3;
bp_[2]=0; // помечаем что в 3 были
bp[1]=4;
bp_[3]=0; // помечаем что в 4 были
int nomer=0;
// находим минимум
if (((Y0[0]/A[0][0])>0)&&((Y0[0]/A[0][0])<(Y0[1]/A[1][0]))) {mini=(Y0[0]/A[0][0]);}
else {mini=(Y0[1]/A[1][0]);nomer=1;}
// находим дельта
for (int i=0;i<n;i++)
{delta[i]=C[i]-(C[bp[0]-1]*A[0][i]+C[bp[1]-1]*A[1][i]);}
int s=maxi(delta); // номер ведущего столбца
double v_e=A[nomer][s];
// вычмсление строки ебсилон
e[0]=Y0[nomer]/v_e;
for (int i=0;i<n;i++)
{
e[i+1]=A[nomer][i]/v_e;
}
// вывод
for (int i=0;i<nn;i++)
{
printf("%2.0f",C[bp[i]-1]);
cout<<" "<<"x";
printf("%1i",bp[i]);
cout<<" ";
printf("%2.0f",Y0[i]);
cout<<" ";
for (int j=0;j<n;j++)
printf("%7.2f",A[i][j]);
printf("%7.2f",mini);
cout << endl;
}
cout<<"--------------------"<<endl;
cout << " ";
for (int j=0;j<n;j++)
printf("%7.2f",delta[j]);
cout << endl<< " ";
for (int j=0;j<n+1;j++)
printf("%7.2f",e[j]);
cout<<endl<<"---------------"<<endl;
while (exitt(delta)==false) // смотрим всё ли элементы в е отрицательны
{
if (neogr(A)==true) {cout<<"no ogran";return 0;} // проверяем есть ли столбцы со всеми отрицательными элементами
if (((bp[nomer])!=(bp_free()+1))&&((bp[1-nomer])!=(bp_free()+1)))
{
bp[nomer]=bp_free()+1;
bp_[bp_free()]=1;
}
else {bp[nomer]=bp_free()+2;bp_[bp_free()+1]=1;}
//пересчитываем матрицу А
Y0[nomer]=e[0];
Y0[1-nomer]=Y0[1-nomer]-e[0]*A[1-nomer][s];
for (int i=0;i<n;i++)
{
A1[nomer][i]=e[i+1];
A1[1-nomer][i]=A[1-nomer][i]-e[i+1]*A[1-nomer][s];
}
for (int i=0;i<n;i++)
{delta[i]=C[i]-(C[bp[0]-1]*A1[0][i]+C[bp[1]-1]*A1[1][i]);}
if (exitt(delta)==true)
{
cout << endl<<endl;
for (int i=0;i<nn;i++)
{
printf("%2.0f",C[bp[i]-1]);
cout<<" "<<"x";
printf("%1i",bp[i]);
cout<<" ";
printf("%2.0f",Y0[i]);
cout<<" ";
for (int j=0;j<n;j++)
{printf("%7.2f",A1[i][j]);}
cout << endl;
}
cout << " ";
for (int j=0;j<n;j++)
printf("%7.2f",delta[j]);
cout << endl<< " "<<endl<<endl;
double aa[n];
for (int i=0;i<n;i++) aa[i]=0;
aa[bp[0]-1]=Y0[0];
aa[bp[1]-1]=Y0[1];
cout<<"б.п. {";
for (int i=0;i<n;i++) cout <<aa[i]<<" ";
cout <<"}"<<endl;
if (aa[0]<0.0001) C[0]=0;
cout<<"(.)max = ("<<C[0]*aa[0]<<";"<<C[1]*aa[1]<<")"<<endl;
cout<<"function(.)max = " <<C[0]*aa[0]+C[1]*aa[1];
return 0;
}
s=maxi(delta); // ведущий столбец
// находим минимум
nomer=0;
if (((Y0[1]/A1[1][s])<0)||(A1[1][s])==0)
{mini=(Y0[0]/A1[0][s]);nomer=0;}
else {mini=(Y0[1]/A1[1][s]);nomer=1;}
if ((A1[0][s])==0)
{mini=(Y0[1]/A1[1][s]);nomer=1;}
v_e=A1[nomer][s];
e[0]=Y0[nomer]/v_e;
for (int i=0;i<n;i++)
{
e[i+1]=A1[nomer][i]/v_e;
}
// вывод
for (int i=0;i<nn;i++)
{
printf("%2.0f",C[bp[i]-1]);
cout<<" "<<"x";
printf("%1i",bp[i]);
cout<<" ";
printf("%2.0f",Y0[i]);
cout<<" ";
for (int j=0;j<n;j++)
printf("%7.2f",A1[i][j]);
cout <<" ";
printf("%5.2f",mini);
cout <<endl;
}
cout<<"-------------------"<<endl;
cout << " ";
for (int j=0;j<n;j++)
printf("%7.2f",delta[j]);
cout << endl<< " ";
for (int j=0;j<n+1;j++)
{printf("%7.2f",e[j]);}
cout<<endl<<"--------------"<<endl;
update(A,A1);
}
return 0 }
Другие работы по теме:
Риск в задачах линейного программирования
Лабораторная работа №3 Риск в задачах линейного программирования. Задание Предприятие выпускает 2 вида продукции в объмах Н1 и Н2. Известен случайный вектор ограничений -
Метод ветвей и границ (контрольная)
Министерство образования Р.Ф. Тюменский государственный нефтегазовый университет Институт нефти и газа Кафедра менеджмента В отраслях ТЭК Контрольная работа по
Симплекс метод 2
Симплекс-метод Симплекс-метод Текущая версия (не проверялась) Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида
Риск в задачах линейного программирования
Лабораторная работа №3 Риск в задачах линейного программирования. Задание: Предприятие выпускает 2 вида продукции в объмах Н1 и Н2. Известен случайный вектор ограничений -
Метод ветвей и границ контрольная
Министерство образования Р.Ф. Тюменский государственный нефтегазовый университет Институт нефти и газа Кафедра менеджмента В отраслях ТЭК Контрольная работа по
Решение задачи линейного программирования
Рассмотрим задачу линейного программирования Теорема . Если множество планов задачи (1) не пусто и целевая функция сверху ограничена на этом множестве, то задача (1) имеет решение.
Задачи по Математике 3
Задача 1 Решить графическим методом задачу линейного программирования А) найти область допустимых значений многоугольник решений Б) найти оптимумы целевой функции F=2x1 + x2 max min 2X1 + X2 ≥ 4 2X1 - X2 ≤ 0 0 ≤ X1 < 2 0 ≤ X2 < 8 Решение:
Симплекс-метод
Материал инструмента и заготовки, вертикально-сверлильный станок. Ограничения по стойкости, мощности привода станка, кинематике и стойкости. Расчет целевой функции производительности, оптимальной точки режима резания. Оптимальное решение симплекс-методом.
Симплекс метод в форме презентации
Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
Математические методы методы
Общая задача линейного программирования Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения функции
Симплекс метод решения задачи линейного программирования
Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
Математическое программирование
Решение задачи линейного программирования симплекс-методом. Нахождение оптимального плана по критерию максимума прибыли. Транспорт - определение плана перевозок грузов на предприятие, которое обеспечивает минимальные совокупные транспортные издержки.
Исследование операций
Математическая модель задачи. Система ограничений. Составление симплекс-таблиц. Разрешающий элемент. Линейное программирование. Коэффициенты при свободных членах. Целевая функция. Метод потенциалов, северо-западного угла. Выпуклость, вогнутость функции.
Решение задач линейного программирования симплекс-методом
Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
Решение задачи оптимального управления
Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
Решение задач нелинейного программирования
Решение задачи нелинейного программирования с определением экстремумов функции. Этапы процесса нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации. Определение гиперповерхности уровней функции.
Решение задач линейного программирования
Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
Графический метод решения задач линейного программирования
Расчет производства необходимого количества продукции для получения максимальной прибыли предприятия. Математическая модель для решения задач линейного программирования. Построение ограничений и целевых функций. Исследование чувствительности модели.
Применение симплекс-метода
Сущность и описание симплекс-метода и улучшенного симплекс-метода (метода обратной матрицы), преимущества и недостатки их применения в линейном прогаммировании. Листинг и блок-схема программы на языке Turbo Pascal для решения математической задачи.
Задач линейного программирования
Цель работы: изучить теорию и методы решения задач линейного программирования; пробрести навыки построения моделей линейного программирования и решения задач линейного программирования на ЭВМ.
Линейное программирование 2 3
Задача 1 (16.88) Минимизировать функцию f(x) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства
Задачи линейного программирования 2
Лабораторная работа. Тема Задачи линейного программирования Цель: преобретение практических навыков применения методов линейного программирования
Применение симплекс-метода
Содержание: Введение ………………………………………………….. Постановка задачи Описание метода Математическая постановка задачи ……………………. Листинг программы………………………………………..
Исследование операций 4
Министерство общего и профессионального образования РФ Южно-Уральский Государственный Университет Кафедра «Системы управления» КУРСОВАЯ РАБОТА
Построение и анализ на чувствительность моделей задач линейного программирования
Лабораторная работа №1 ПОСТРОЕНИЕ И АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы: научиться определять оптимальный план производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида; освоить методику и технологию поиска оптимального решения задач линейного программирования (ЗЛП) с помощью ЭВМ; приобрести практический опыт проведения анализа оптимального решения ЗЛП на чувствительность.