Xreferat.com » Рефераты по экономико-математическому моделированию » Решения задачи планирования производства симплекс методом

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

670/3, 495/1}=min{600,295,187.5,223.3,495}=187.5 и xs=x8. Строка, которая соответствует переменной xs=x8 в симплекс-таблице, называется разрешающей. Элемент asr=a81=4 называется разрешающим элементом симплекс-таблицы.

Выбор разрешающего элемента завершает формирование нового базиса XБ1, отличающегося от прежнего базиса одной переменной xr=x1, то есть вместо переменной x8 в базис XБ1 будет включена переменная x1: XБ1=(x6, x7, x1, x9, x10)T.

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


3.3.6 Пересчет симплекс-таблицы

Правила пересчета:

Разрешающий элемент заменяется на 1.

Элементы разрешающего столбца за исключением asr переписываются без изменений.

Элементы разрешающей строки за исключением asr изменяют знак на противоположный.

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


Все элементы полученной таблицы необходимо разделить на разрешающий элемент asr:



Таблица 3. Итерация №1

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X6 825/2 0 15/4 5/4 3/4 5/2 1 0 -1/4 0 0
X7 215 0 3/2 -1/2 7/2 1 0 1 -1/2 0 0
X1 375/2 1 1/4 3/4 1/4 1/2 0 0 1/4 0 0
X9 215/2 0 5/4 7/4 5/4 -1/2 0 0 -3/4 1 0
X10 615/2 0 7/4 1/4 15/4 7/2 0 0 -1/4 0 1
Y 11250 0 -35 8 -30 -26 0 0 15 0 0

XБ1=(x6, x7, x1, x9, x10)T.

Базис XБ1=(x6, x7, x1, x9, x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a92=5/4 определяет необходимость перехода к базису XБ2=(x6, x7, x1, x2, x10)T. Приведем результат пересчета симплекс-таблицы для базиса XБ2.


Таблица 4. Итерация №2.

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X6 90 0 0 -4 -3 4 1 0 2 -3 0
X7 86 0 0 -13/5 2 8/5 0 1 2/5 -6/5 0
X1 166 1 0 2/5 0 3/5 0 0 2/5 -1/5 0
X2 86 0 1 7/5 1 -2/5 0 0 -3/5 4/5 0
X10 157 0 0 -11/5 2 21/5 0 0 4/5 -7/5 1
Y 14260 0 0 57 5 -40 0 0 -6 28 0

Базис XБ2=(x6, x7, x1, x2, x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a65=4 определяет необходимость перехода к базису XБ3=( x5, x7, x1, x2, x10)T. Приведем результат пересчета симплекс-таблицы для базиса XБ3.


Таблица 5. Итерация №3

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 45/2 0 0 -1 -3/4 1 1/4 0 1/2 -3/4 0
X7 50 0 0 -1 16/5 0 -2/5 1 -2/5 0 0
X1 305/2 1 0 1 9/20 0 -3/20 0 1/10 1/4 0
X2 95 0 1 1 7/10 0 1/10 0 -2/5 1/2 0
X10 125/2 0 0 2 103/20 0 -21/20 0 -13/10 7/4 1
Y 15160 0 0 17 -25 0 10 0 14 -2 0

Базис XБ3=(x5, x7, x1, x2, x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a104=103/20 определяет необходимость перехода к базису XБ4=(x5, x7, x1, x2, x4)T. Приведем результат пересчета симплекс-таблицы для базиса XБ4.


Таблица 6. Итерация №4

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 3255/103 0 0 -73/103 0 1 10/103 0 32/103 -51/103 15/103
X7 1150/103 0 0 -231/103 0 0 26/103 1 42/103 -112/103 -64/103
X1 15145/103 1 0 85/103 0 0 -6/103 0 22/103 10/103 -9/103
X2 8910/103 0 1 75/103 0 0 25/103 0 -23/103 27/103 -14/103
X4 1250/103 0 0 40/103 1 0 -21/103 0 -26/103 35/103 20/103
Y 15463,4 0 0 2751/103 0 0 505/103 0 792/103 669/103 500/103

Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T.

3.4 Результат решения задачи планирования производства


В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем наложенным ограничениям и обеспечивает максимальную стоимость данного набора (максимум целевой функции f(x)= 60x1+50x2+37x3+45x4+56x5=15463,4 рублей). Таким образом, можно оптимально спланировать объем производства продукции при наличии заданного количества ресурсов: продукции типа A нужно выпустить 147 единиц, продукции типа B – 86 единиц, продукции типа D – 12 единиц, продукции типа E – 31 единицу, а продукцию типа D – для достижения максимальной прибыли в данных условиях производить не выгодно.

При этом ресурсы типа 1, 3, 4, 5 будут использованы полностью, а 11 единиц ресурса типа 2 останутся неизрасходованными.


4. Программа для решения задач ЛП симплекс методом


4.1 Описание


В процессе выполнения дипломной работы был реализован и отлажен программный интерфейс под ОС Windows XP (также протестирован под Windows Vista), решающий задачи ЛП симплекс методом (в частности поставленную задачу планирования производства).

Программа осуществляет: решение задач ЛП симплекс методом; сохранение и загрузка исходных данных в файл/из файла; вывод решения по шагам; экспорт решения в документ MS word; системный код программы написан в среде объектно-ориентированного программирования С++.


4.2 Графическое представление программы


Главное окно программы «Исходные данные»:

Рис.5 Главное окно программы Simplex: 1 – Кнопки загрузка/сохранение исходных данных в файл. 2 – Число переменных, в нашем случае количество производимой продукции. 3 – Число ограничений, в нашем случае количество запасов ресурсов на складе. 4 – Целевая функция, в нашем случае максимизация. 5 – Система ограничений в форме Такера. 6 – Кнопка для решения задачи и перехода к окну «Решение».


Окно программы «Решение»:

Рис.6 Окно программы Simplex, для просмотра решения по шагам: 1 – Поле для вывода пошагового решения задачи. 2 – Кнопка для экспорта результатов работы программы в документ MS Word.


4.3 Работа с программой


1 – Определяем число переменных; 2 – Определяем максимизируем или минимизируем целевую функцию; (см. Рис.7)


Рис.7 Работа с программой


3 – Определяем число ограничений; 4 – Определяем знаки неравенств для системы ограничений; 5 – Указываем дополнительные ограничения неотрицательности; (см. Рис.8)

Рис.8 Работа с программой


Приступаем к вводу исходных данных: 6 – поля для ввода коэффициентов целевой функции (в нашем случае это цена единицы продукции типа A,…,E); 7 – поля для ввода запасов каждого ресурса; 8 – поля для ввода набора производимой продукции. Заполнив все поля, приступаем к решению задачи: 9 – нажимаем кнопку «Решить». (см. Рис.9)


Рис.9 Работа с программой


После нажатия кнопки «Решения» программа производит необходимые вычисления и автоматически переходит ко второму окну, в котором отображается пошаговое решение поставленной задачи в виде симплекс таблиц, с указанием необходимых дополнительных данных. А именно: 10 - исходные данные; 11 - система ограничений в форме Такера; 12 - целевая функция; 13 – исходная симплекс таблица; (см. Рис.10)


Рис.10 Работа с программой


14 - разрешающий элемент каждой таблицы, 15 - переход от старого базиса к новому, 16 - количество итераций, 17 - информация об оптимальности решения, 18 – Ответ, в нашем случае максимум целевой функции (максимальная прибыль), 19 – оптимальный набор производимой продукции (количество изделий A,…,E). (см. Рис.11)

Рис.11 Работа с программой


4.4 Схема программы


Логическая структура программы решающей задачи ЛП симплекс методом приведена на Рис.12, Рис.13, Рис.14.

Рис.12 Симплекс метод

Рис.13 Поиск r-столбца

Рис.14 Поиск s-строки


Заключение


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

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

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


Список литературы


  1. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т.2: Пер с англ. - М.: Мир, 1991. - 342с., ил. Раздел Целочисленное линейное программирование

  2. Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2002. - 208 с.: ил. - (Серия "Краткий курс"). Раздел 4.2 Метод Гомори

  3. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8

  4. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

  5. Ершов А.Т., Карандаев И.С., Шананин Н.А. Планирование производства и линейное программирование. МИУ, М., 1981.

  6. Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «Высшая школа» 1993г.

  7. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «Высшая школа» 1980г.

  8. Вентцель Е.С. Исследование операций: задачи, принципы, методологии. М.: Изд-во «Наука», 1980.

  9. Джерод Холлингворс, Дэн Баттерфилд, Боб Свот C++ Builder 5. Руководство разработчика = C++ Builder 5 Developer's Guide. — М.: «Диалектика», 2001. — С. 884. — ISBN 0-672-31972-1

  10. Джаррод Холингворт, Боб Сворт, Марк Кэшмэн, Поль Густавсон Borland C++ Builder 6. Руководство разработчика = Borland C++ Builder 6 Developer's Guide. — М.: «Вильямс», 2004. — С. 976. — ISBN 0-672-32480-6

  11. Леоненков А.В. Решение задач оптимизации в среде MS Excel BHV-Санкт-Петербург ISBN: 5941575033 2005 г.

Приложение 1

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


// Этот файл определяет класс симплекс метода

#include <vcl.h>

#include <list>

#include "CD.cpp"

#ifndef CSM2_H

#define CSM2_H


namespace SM

{


//----------------Симплекс метод------------------------------

class CSM

{

public:

CSM( int n, int m );

void SetBaz( int * baz );

int SetT( CD ** T );


void Show();

AnsiString GetWord();

AnsiString GetTacker();

AnsiString Get_Rap();


int operator<<=( CSM * csm );


CD get_CF();

CD** get_ogr(){ return T; }

int* get_baz(){ return baz; }

int get_rez(){ return rez; }

void get_nm( int* nIn, int* mIn ){ *nIn = n; *mIn = m; }

void get_ij( int* i, int* j ){ *i = a_i; *j = a_j; }


~CSM( );


private:

static int iter; // Число итераций


int optim(); // проверка решение (0 - оптимальное, 1 - не существует, 2 - не оптимальное)


int n; // Число переменных

int m; // Число ограничений


int a_i;

int a_j; // Координаты разрешающего элемента


int * baz; // Массив базисных переменных

CD ** T; // Симплекс таблица

int rez;

};


int CSM::iter = 0; // Число итераций


CSM::CSM( int nIn, int mIn )

{

n = nIn;

m = mIn;

baz = new int [m];

T = new CD * [m + 1]; // m + 1 т.к. еще строка целевой функции

for( int i = 0; i < m + 1; i++ )

T[i] = new CD [n + 1]; // n + 1 т.к. еще свободный член

iter += 1;

rez = 2;

}

CSM::~CSM( )

{

delete baz;

for( int i = 0; i < m + 1; i++ )

delete T[i];

delete T;

iter -= 1;

}

void CSM::SetBaz( int * bazIn )

{

for( int i = 0; i < m; i++ )

baz[i] = bazIn[i];

}

int CSM::SetT( CD ** TIn ) // Копирование входящей таблицы и проверка решения с поиском разрешающего элемента

{

for( int i = 0; i < m + 1; i++ )

for( int j = 0; j < n + 1; j++ )

T[i][j] = TIn[i][j];

return optim();

}

int CSM::optim()

{

a_i = a_j = 0; // Инициализация координат разрешающего элемента


// Проверка на отрицательность среди свободных членов

for( int i = 1; i < m; i++ ) // проверка свободного члена

if( T[i][0].get_d() < T[a_i][0].get_d() ) // Ищем минимальный

a_i = i;

if( T[a_i][0].get_d() < 0 ) // Если минимальный элемент отрицательный (двойственный СМ)

{

for( int j = 1; j < n + 1; j++ ) // проверка на наличие отрицательных эл-тов в строке

if( T[a_i][j].get_d() < 0 ) // есть отрицательные элементы

{

a_j = j; // Первый отрицательный элемент

break; // Выход из цикла поиска

}


if( a_j == 0 ) return rez = 1; // Нет оптимального решения // выход


for( int j = a_j + 1; j < n + 1; j++ ) // Проходим по строке еще раз для нахождения минимального отношения

if( T[a_i][j].get_d() < 0 ) // Отрицательный

if( fabs( (T[m][j]/T[a_i][j]).get_d() ) < fabs( (T[m][a_j]/T[a_i][a_j]).get_d() ) ) // Наименьшее отношение

a_j = j;


return rez = 2; // продолжение выполнений итераций // выход

}


// Проверка на отрицательность среди элементов целевой функции

a_j = 1;

a_i = m;


for( int j = 2; j < n + 1; j++ ) // Проходим по строке целевой функции

if( T[m][j].get_d() < T[m][a_j].get_d() ) // Ищем минимальный

a_j = j;


if( T[m][a_j].get_d() < 0 ) // Есть отрицательный элемент в целевой функции

{

for( int i = 0; i < m; i++ ) // Проходим по столбцу

if( T[i][a_j].get_d() > 0 )

{

a_i = i; // Первый положительный элемент

break; // Выход из цикла поиска

}


if( a_i == m ) return rez = 1; // Нет оптимального решения // выход


for( int i = a_i + 1; i < m; i++ ) // Проходим по столбцу еще раз для нахождения минимального отношения

if( T[i][a_j].get_d() > 0 ) // Положительный

if( fabs( (T[i][0]/T[i][a_j]).get_d() ) < fabs( (T[a_i][0]/T[a_i][a_j]).get_d() ) ) // Наименьшее отношение

a_i = i;


return rez = 2; // продолжение выполнений итераций // выход

}


return rez = 0; // оптимальное решение // выход

}


int CSM::operator<<=( CSM * csmIn ) // Здесь из предыдущей таблицы получается новая

{

a_i = csmIn->a_i;

a_j = csmIn->a_j;


// Делим на разрешающий элемент разрешающую строку и меняем базисную переменную

for( int j = 0; j < n + 1; j++ )

T[a_i][j] = csmIn->T[a_i][j] / csmIn->T[a_i][a_j];


// Домножаем разрешающую строку на эл-т в разрешающем столбце, соотв-щий данной строке, и складываем с данной строкой

for( int i = 0; i < m + 1; i++)

{

if( i == a_i) continue;

for( int j = 0; j < n + 1; j++ )

T[i][j] = csmIn->T[i][j] - T[a_i][j] * csmIn->T[i][a_j];

}


// Вводим новую переменную в базис

for( int i = 0; i < m; i++ )

baz[i] = csmIn->baz[i];

baz[a_i] = a_j;


return optim();

}


CD CSM::get_CF()

{

return T[m][0];

}


void CSM::Show( )

{

AnsiString tab;

tab = "БПtСЧ";

for( int j = 0; j < n; j++)// шапка

tab = tab + "tX" + AnsiString( j + 1 );

for( int i = 0; i < m + 1; i++ )

{

if( i == m ) tab = tab + "nY";

else tab = tab + "n" + baz[i];

for( int j = 0; j < n + 1; j++)

tab = tab + "t" + T[i][j].get_a();

}

// ShowMessage(tab);

}


AnsiString CSM::GetWord()

{

// Таблица

AnsiString tab;

tab = "n<table border=3 cellpadding=5 ><tr bgcolor="#aaaaaa">";


tab += "<td align="center">БП</td><td>СЧ</td>";

for( int j = 0; j < n; j++)// шапка

{

tab += "<td align="center">";

tab = tab + "X<sub>" + (j+1) + "</sub>";

tab += "</td>";

}

tab += "</tr>";


for( int i = 0; i < m + 1; i++ )

{

tab += "<tr>";


tab += "<td bgcolor="#aaaaaa" align="center">";

if( i == m ) tab += "F'";

else tab = tab + "X<sub>" + baz[i] + "</sub>";

tab += "</td>";


for( int j = 0; j < n + 1; j++)

{

if( i == a_i && j == a_j && rez == 2 ) tab += "<td bgcolor="#cccccc">";

else tab += "<td align="center">";

tab += T[i][j].get_a();

tab += "</td>";

}


tab += "</tr>";

}

tab += "</table>";


return tab;


/*

AnsiString tab;

tab = "БП;СЧ;";

for( int j = 0; j < n; j++)// шапка

if( j == n - 1 ) tab = tab + "X" + AnsiString( j + 1 );

else tab = tab + "X" + AnsiString( j + 1 ) + ";";

for( int i = 0; i < m + 1; i++ )

{

if( i == m ) tab = tab + "nF';";

else tab = tab + "nX" + baz[i] + ";";

for( int j = 0; j < n + 1; j++)

if( j == n ) tab = tab + T[i][j].get_a();

else tab = tab + T[i][j].get_a() + ";";

}

return tab;

*/

}


AnsiString CSM::GetTacker()

{

AnsiString tab;

for( int i = 0; i < m; i++ )

{

tab += AnsiString("X") + baz[i] + " = ";

tab += T[i][0].get_a() + " - ( " + T[i][1].get_a() + "*X1";


for( int j = 2; j < n + 1; j++)

{

bool is_b = false;

for( int d = 0; d < m; d++ )

if( j == baz[d] )

{

is_b = true;

break;

}

if( !is_b )

tab += T[i][j].get_s() + "*X" + AnsiString( j );

}

tab += " )n";

}

tab += "nЦелевая функция:";

tab += "nF' = " + T[m][0].get_a() + " - ( " + T[m][1].get_a() + "*X1";


for( int j = 2; j < n + 1; j++)

{

bool is_b = false;

for( int d = 0; d < m; d++ )

if( j == baz[d] )

{

is_b = true;

break;

}

if( !is_b )

tab += T[m][j].get_s() + "*X" + AnsiString( j );

}

tab += " )n";


return tab;

}


AnsiString CSM::Get_Rap()

{

AnsiString Rap;

if( rez == 0 )

{

if( T[m][0] == 0 )

Rap = "Решение оптимальное. Искусственный базис получен. Далее подставляем новые бвазисные пременные в целевую функцию.";

else Rap = "Решение оптимальное, но целевая функция не равна 0. искусственного базиса нет.";

}

else if( rez == 1 )

{

if( a_j == 0 ) Rap = AnsiString( "Решения не существует. Целевая функция неограничена, т.к. свободный член при X" ) + baz[a_i] + " отрицательный, а другие элементы строки не отрицательные.";

else if( a_i == m ) Rap = AnsiString( "Решения не существует. Целевая функция неограничена, т.к. элемент в строке целевой функции при X" ) + a_j + " отрицательный, а другие элементы столбца не положительные.";

}

else if( rez == 2 )

{

Rap = AnsiString( "Решение продолжается. Из базиса выводится X") + baz[a_i] + " и вводится X" + a_j + ".";

}

return Rap;

}


}

#endif // CSM_H


// Этот файл определяет класс дроби


#include <vcl.h>

#include <math.h>


#ifndef CD_H

#define CD_H


#define PR_COUNT 5000

int mas[PR_COUNT] = {0};

void Generate_Prost();


class CD // Класс дробь

{

public:

CD::CD( int = 0, int = 1 );

bool Set( int hi, int lo );

bool Set( double d );

bool Set( AnsiString d );

bool SetInv( AnsiString d );

int hi(){ return m_hi; }; // числитель

int lo(){ return m_lo; }; // знаменатель


double get_d(); // возвращает десятичное значение

AnsiString get_a(); // возвращает строку обычной дроби

AnsiString get_s(); // возвращает строку обычной дроби


CD get_dr();

int get_cel();

CD get_abs();


CD operator*(CD d);

CD operator*(int num);

CD operator/(CD d);

CD operator/(int num);

CD operator+(CD d);

CD operator+(int num);

CD operator-(CD d);

CD operator-(int num);

CD operator=(CD d);

CD operator=(int num);

bool operator==(CD d);

bool operator==(int num);

bool operator!=(CD d);

bool operator!=(int num);


private:

int m_hi; // числитель

int m_lo; // знаменатель


double m_d;

bool overflow;


void optim();

static bool gen;

};


bool CD::gen = false;


CD::CD( int hi, int lo )

{

if( !gen )

{

Generate_Prost();

gen = true;

}

overflow = false;

Set( hi, lo );

}

bool CD::Set( int hi, int lo )

{

overflow = false;

if( lo == 0 )

{

m_hi = 0;

m_lo = 1;

return false;

}

m_hi = hi;

if( m_hi == 0 ) m_lo = 1;

else

{

m_lo = lo;

optim();

}

return true;

}

bool CD::Set( double d )

{

overflow = true;

m_d = d;

return true;

}

bool CD::Set( AnsiString d )

{

int pos = 0;

if( pos = d.LastDelimiter("/") )

{

m_hi = StrToIntDef( d.SubString( 1, pos - 1 ), 0 );

m_lo = StrToIntDef( d.SubString( pos + 1, d.Length() ), 1 );

Set( m_hi, m_lo );

}

else if( pos = d.LastDelimiter(".,") )

{

Set( StrToFloat( d ) );

}

else

{

m_hi = StrToIntDef( d, 0 );

Set( m_hi, 1 );

}

optim();

//

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: