Решения задачи планирования производства симплекс методом
Выбор разрешающего элемента завершает формирование нового базиса 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-строки
Заключение
Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования производственной деятельности. В этих условиях только научный подход к экономике предприятий позволит обеспечить высокие темпы развития промышленности. Научного подхода требует и решение тактических и стратегических задач.
В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение как в экономических исследованиях и планировании, так и в других задачах. Этому способствует развитие таких разделов математики как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники.
Уже накоплен большой опыт постановки и решения экономических и тактических задач с помощью математических методов. Особенно успешно развиваются методы оптимального управления. Экономика и производство развивается быстро там, где широко используются математические методы.
Список литературы
Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т.2: Пер с англ. - М.: Мир, 1991. - 342с., ил. Раздел Целочисленное линейное программирование
Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2002. - 208 с.: ил. - (Серия "Краткий курс"). Раздел 4.2 Метод Гомори
Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
Ершов А.Т., Карандаев И.С., Шананин Н.А. Планирование производства и линейное программирование. МИУ, М., 1981.
Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «Высшая школа» 1993г.
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «Высшая школа» 1980г.
Вентцель Е.С. Исследование операций: задачи, принципы, методологии. М.: Изд-во «Наука», 1980.
Джерод Холлингворс, Дэн Баттерфилд, Боб Свот C++ Builder 5. Руководство разработчика = C++ Builder 5 Developer's Guide. — М.: «Диалектика», 2001. — С. 884. — ISBN 0-672-31972-1
Джаррод Холингворт, Боб Сворт, Марк Кэшмэн, Поль Густавсон Borland C++ Builder 6. Руководство разработчика = Borland C++ Builder 6 Developer's Guide. — М.: «Вильямс», 2004. — С. 976. — ISBN 0-672-32480-6
Леоненков А.В. Решение задач оптимизации в среде 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();
//