183660 (596698), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Таким образом, выберем в качестве начального базиса XБО=(x6, x7, x8, x9, x10)T, так как столбцы A6, A7, A8, A9, A10 матрицы A образуют единичную матрицу.

Теперь перейдем к заполнению симплекс-таблицы. Пусть ЗЛП сформулирована в канонической форме (5). Мы выбрали базисные переменные x6, x7, x8, x9, x10. Разрешим систему неравенств в (5) относительно базисных переменных.

Система ограничений в форме Такера примет вид:

x6=600-(x1+4x2+2x3+x4+3x5);

x7=590-(2x1+2x2+x3+4x4+2x5);

x8=750-(4x1+x2+3x3+x4+2x5);(7)

x9=670-(3x1+2x2+4x3+2x4+x5);

x10=495-(x1+2x2+x3+4x4+4x5);

Целевую функцию можно представить в виде:

f(x)=f0-(-60x1-50x2-37x3-45x4-56x5), где f0=0.

Симплекс-таблица выглядит следующим образом:

Таблица 1. Исходная симплекс таблица в общем виде

В нашем случае:

Таблица 2. Исходная симплекс таблица поставленной задачи

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

Каждая симплекс-таблица анализируется по критериям допустимости и оптимальности базиса.

3.3.4 Проверка признака допустимости и оптимальности базиса

Признак допустимости базиса:

в опорной точке в соответствии с (7) xj=bi, i=6,…,10; j=6,…,10, поэтому признак допустимости базиса формулируется как условие bi 0, i=6,…,10.

Признак оптимальности базиса:

Если для то найденное решение оптимально и единственно.

Если для то найденное решение оптимально, но не единственно.

Если то решение неоптимально. В этом случае поиск оптимального решения продолжается и необходимо перейти к новой опорной точке.

Перейдем к конкретному случаю. В нашем случае выполняется условие допустимости базиса, так как b=(600, 590, 750, 670, 495)T<0 и bi<0 (i=6,…,10).

Выбранный нами начальный базис XБО=(x6, x7, x8, x9, x10)T не является оптимальным, так как c1=-60<0, c2=-50<0, c3=-37<0, c4=-45<0 и c6=56<0. Таким образом, необходимо осуществить переход к новой опорной точке (новому базису).

3.3.5 Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса

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

Выбор переменной xr. Выбор переменной xr осуществляется по результатам анализа коэффициентов cj симплекс-таблицы. Найдем cr= .

В нашем случае min{c1, c2, c3, c4, c5}=c1=-60 и xr=x1.

Столбец, который соответствует переменной xr=x1 в симплекс-таблице, будем называть разрешающим.

Выбор переменной xs. Выбор переменной xs проводится по результатам анализа коэффициентов air i=1,2,3,4,5 разрешающего столбца.

Если , это означает, что ОДР такова, что неограниченное увеличение свободной переменной xr приводит к неограниченному возрастанию целевой функции (ОДР не замкнута).

Если , то соответствующие базисные переменные xi (i=6,7,8,9,10) получают отрицательные приращения при увеличении xr=x1. Среди этих переменных xi необходимо отыскать xs, достигающую нуля при минимальном значении приращения xr. Нужно найти

.

В нашем случае min{600/1, 590/2, 750/4, 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

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.

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

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

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

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

Анализ Таблицы 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

#include

#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

tab += "БПСЧ";

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

{

tab += "";

tab = tab + "X_{" + (j+1) + "}";

tab += "";

}

tab += "";

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

{

tab += "";

tab += "";

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

else tab = tab + "X_{" + baz[i] + "}";

tab += "";

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

{

if( i == a_i && j == a_j && rez == 2 ) tab += "";

else tab += "";

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

tab += "";

}

tab += "";

}

tab += "";

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 )

{

Характеристики

Список файлов ВКР