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

Таким образом, выберем в качестве начального базиса 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. Исходная симплекс таблица в общем виде

b

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x6

b6

a61

a62

a63

a64

a65

a66

a67

a68

a69

a610

x7

b7

a71

a71

a71

a71

a71

a71

a71

a71

a71

a710

x8

b8

a81

a82

a83

a84

a85

a86

a87

a88

a89

a810

x9

b9

a91

a92

a93

a94

a95

a96

a97

a98

a99

a910

x10

b10

a101

a102

a103

a104

a105

a106

a107

a108

a109

a1010

f(x)

f0

c1

c2

c3

c4

c5

c6

c7

c8

c9

c10

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

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

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X6	600	1	4	2	1	3	1	0	0	0	0
X7	590	2	2	1	4	2	0	1	0	0	0
X8	750	4	1	3	1	2	0	0	1	0	0
X9	670	3	2	4	2	1	0	0	0	1	0
X10	495	1	2	1	4	4	0	0	0	0	1
Y	0	-60	-50	-37	-45	-56	0	0	0	0	0

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

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

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

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

в опорной точке в соответствии с (7) xj=bi, i=6,…,10; j=6,…,10, поэтому признак допустимости базиса формулируется как условие bi0, 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

БП	СЧ	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_{" + (j+1) + "}";

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_{" + baz[i] + "}";

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();

// ShowMessage( "m_hi = " + AnsiString(m_hi) + "\nm_lo = " + m_lo );

return true;

}

bool CD::SetInv( 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 );

}

// ShowMessage( "m_hi = " + AnsiString(m_hi) + "\nm_lo = " + m_lo );

return true;

}

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

{

if( overflow ) return m_d;

if ( m_hi ) return float(m_hi)/m_lo;

else return 0;

}

AnsiString CD::get_a()

{

if( overflow ) return FloatToStrF( m_d, ffGeneral, 7, 0 );

if ( m_lo == 1 ) return AnsiString(m_hi);

else return AnsiString(m_hi) + "/" + AnsiString(m_lo);

}

AnsiString CD::get_s()

{

if( overflow )

{

if( m_d >= 0 ) return AnsiString( " + " ) + FloatToStrF( m_d, ffGeneral, 7, 0 );

else return AnsiString( " - " ) + FloatToStrF( -m_d, ffGeneral, 7, 0 );

}

if ( m_lo == 1 ) return (m_hi < 0)?AnsiString(" - ") + abs(m_hi):" + " + AnsiString(m_hi);

else return ((m_hi < 0)?AnsiString(" - ") + abs(m_hi):" + " + AnsiString(m_hi)) + "/" + AnsiString(m_lo);

}

CD CD::get_dr()

{

CD cd;

if( overflow )

{

cd.Set( m_d - floor(m_d) );

return cd;

}

ldiv_t r;

r = ldiv( m_hi, m_lo );

if( r.rem >= 0 )

{

cd.Set( r.rem, m_lo );

}

else

{

cd.Set( m_lo + r.rem, m_lo );

}

return cd;

}

int CD::get_cel()

{

int cd;

if( overflow )

{

cd = floor( m_d );

return cd;

}

if( m_hi >= 0 )

cd = ldiv( m_hi, m_lo ).quot;

else

cd = ldiv( m_hi, m_lo ).quot - 1;

return cd;

}

CD CD::get_abs()

{

CD cd;

if( overflow )

{

if( m_d >= 0 ) cd.Set( m_d );

else cd.Set( -m_d );

return cd;

}

if( m_hi < 0 ) cd.Set( -m_hi, m_lo );

else cd.Set( m_hi, m_lo );

return cd;

}

CD CD::operator+(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() + d.get_d() );

return cd;

}

cd.Set( m_hi*d.m_lo + d.m_hi*m_lo, m_lo*d.m_lo );

return cd;

}

CD CD::operator+(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() + num );

return cd;

}

cd.Set( m_hi + num*m_lo, m_lo );

return cd;

}

CD CD::operator-(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() - d.get_d() );

return cd;

}

cd.Set(m_hi*d.m_lo - d.m_hi*m_lo, m_lo*d.m_lo );

return cd;

}

CD CD::operator-(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() - num );

return cd;

}

cd.Set( m_hi - num*m_lo, m_lo );

return cd;

}

CD CD::operator*(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() * d.get_d() );

return cd;

}

cd.Set( m_hi*d.m_hi, m_lo*d.m_lo );

return cd;

}

CD CD::operator*(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() * num );

return cd;

}

cd.Set( m_hi*num, m_lo );

return cd;

}

CD CD::operator/(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() / d.get_d() );

return cd;

}

cd.Set( m_hi*d.m_lo, m_lo*d.m_hi );

return cd;

}

CD CD::operator/(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() / num );

return cd;

}

cd.Set( m_hi, m_lo*num );

return cd;

}

CD CD::operator=(CD d)

{

if( d.overflow)

{

Set( d.get_d() );

return *this;

}

Set( d.m_hi, d.m_lo );

return *this;

}

CD CD::operator=(int num)

{

Set( num, 1 );

return *this;

}

bool CD::operator==(CD d)

{

if( overflow || d.overflow )

{

return get_d() == d.get_d();

}

if( m_hi == d.m_hi )

if( m_lo == d.m_lo )

return true;

return false;

}

bool CD::operator==(int num)

{

if( overflow )

{

return get_d() == num;

}

if( m_hi == num )

if( m_lo == 1 )

return true;

return false;

}

bool CD::operator!=(CD d)

{

if( overflow || d.overflow )

{

return get_d() != d.get_d();

}

if( m_hi == d.m_hi )

if( m_lo == d.m_lo )

return false;

return true;

}

bool CD::operator!=(int num)

{

if( overflow )

{

return get_d() != num;

}

if( m_hi == num )

if( m_lo == 1 )

return false;

return true;

}

void CD::optim()

{

if( overflow ) return;

m_hi *= m_lo/abs(m_lo); // для знака

m_lo = abs(m_lo);

if( m_hi ) // далее сокращение дроби

{

int i = 0;

while(1)

{

while( ldiv( m_hi, mas[i] ).rem == 0 && ldiv( m_lo, mas[i] ).rem == 0 )

{

m_hi /= mas[i];

m_lo /= mas[i];

}

if( (mas[i + 1] > abs(m_hi) && mas[i + 1] > m_lo) || i + 1 > PR_COUNT - 1 ) break;

i++;

}

if( abs(m_hi) > mas[PR_COUNT - 1] || m_lo > mas[PR_COUNT - 1] )

{

overflow = true;

m_d = double(m_hi)/m_lo;

return;

}

}

}

void Generate_Prost()

{

bool is_prost;

float per;

int kol = 1;

mas[0] = 2;

int i = 3;

while(1)

{

is_prost = true;

for( int j = 0; j < kol; j++ )

if( ldiv( i, mas[j] ).rem == 0 )

{

is_prost = false;

break;

}

if( is_prost )

{

mas[kol] = i;

kol++;

}

if( kol >= PR_COUNT ) return;

i++;

}

/*

AnsiString p;

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

p = p + mas[i] + " ";

// ShowMessage( p );

//*/

}

#endif // CD_H

Приложение 2

Леонид Витальевич Канторович

Рис. 15 Портрет Л.В. Канторович

Леонид Витальевич Канторович вошел в плеяду крупнейших ученых двадцатого века благодаря своему капитальному вкладу в математику и экономику. Исследования Л.В. Канторовича в области функционального анализа, вычислительной математики, теории экстремальных задач, дескриптивной теории функций и теории множеств оказали влияние на становление и развитие указанных математических дисциплин, послужили основой для формирования новых научных направлений.

Л.В. Канторович по праву считается одним из основоположников современного экономико-математического направления, ядро которого составляют теория и модели линейных экстремальных задач. Это направление было затем переоткрыто и развито в трудах других ученых (прежде всего Дж. Данцига) и получило название линейное программирование. Идеи и методы этой дисциплины широко используются для постановки и решения разнообразных экстремальных и вариационных задач не только в экономике, но и в физике, химии, энергетике, геологии, биологии, механике и теории управления. Линейное программирование оказывает существенное влияние также на развитие вычислительной математики и вычислительной техники. Нам представляется, что никто другой не сделал так много для использования линейного программирования в экономической теории, как Л. В. Канторович.

В настоящее время многочисленные ученики и последователи Л. В. Канторовича успешно работают в различных областях современной математики и экономики, добиваясь значительных научных результатов. Выдающиеся заслуги Л. В. Канторовича были отмечены государством. Он награжден двумя орденами Ленина -- в те годы наивысшими наградами страны, тремя орденами Трудового Красного Знамени, орденами «Знак Почета» и Отечественной войны II степени, многими медалями.

Л.В. Канторович являлся членом ряда зарубежных академий и почетным доктором многих университетов, участвовал в работе международных научных обществ. С момента основания «Сибирского математического журнала» до своей кончины Леонид Витальевич Канторович входил в состав редколлегии, определяя научное лицо журнала в области прикладного функционального анализа и математической экономики.

До последних своих дней Леонид Витальевич был полон творческих планов и активно работал над их претворением в жизнь. Уже в последние месяцы своей жизни, находясь в больнице, он продиктовал свои автобиографические заметки «Мой путь в науке», опубликованные в «Успехах математических наук», и работал над статьей «Функциональный анализ (основные идеи)», опубликованной в СМЖ в 1987 г.

Леонид Витальевич всегда мечтал о внедрении новых математических методов в хозяйственную практику своей Родины и служил этой мечте до своей кончины 7 апреля 1986 г., невзирая на непонимание и откровенное противодействие ретроградов от науки и политики, управлявших страной. Л. В. Канторович похоронен в Москве на Новодевичьем кладбище. Эти факты имеет смысл напомнить еще и потому, что после смерти Л. В. Канторовича в «Новом мире» (№ 12 за 1996 г.) были опубликованы выдумки о борьбе Л. В. Канторовича с идеей планирования в экономике и якобы имевшей место эмиграции в Америку еще в 70-е гг. Клевета настигла его и после смерти …

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

Для своих учеников и последователей Леонид Витальевич всегда был образцом честности, бескомпромиссности и твердости в науке, объективности и трудолюбия. Подкупающими чертами его личности были исключительная доброта, простота и легкость в общении, скромность и даже застенчивость. Он всегда с удовольствием работал с молодежью, и молодежь тянулась к нему.

Леонид Витальевич Канторович указал нам один из путей в будущее. Мы не сомневаемся, что этот путь выберут многие.