Реализация целочисленных моделей принятия решений

Дробная часть = max(1/3; 2/3) = 2/3  дополнительное ограничение записываем по второй строке.

2/3 = 1/3х4 + 2/3S4 - S5  ,S5  0   -     пятое ограничение Гомори.

Вектор, вводимый в базис: вводим х4.
  соответствует строке Гомори.

План Х8 = (3; 2; 3; 2) - оптимальный целочисленный. Lmax = 36.

Экономическая интерпретация: согласно полученному решению предприятию необходимо закупить 3 машины типа "А" и 2 машины ти-па "В". При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

3. Геометрическая интерпретация метода Гомори

строим множество планов (см. рисунок). В точке 1 - оптимальный нецелочисленный план.

Первое ограничение Гомори:    2/9x3 + 8/9x4 - S1 = 4/9,  S1  0
Из первого ограничения задачи:    х3 = 19 - 2х1 - 5х2
Из второго ограничения задачи:    х4 = 16 - 4х1 - х2

Подставляем х3 и х4 в первое ограничение Гомори и после преобразований получаем: 4х1 + 2х2 + S1 = 18, S1  0.

Отсюда имеем:    4х1 + 2х2  18. Это ограничение отсекает от множества планов область, содержащую точку 1. Новый оптимальный нецелочисленный план - точка 2.

Второе ограничение Гомори :    1/4x3 + 7/8S1 - S2 = 1/2,  S2  0
Из первого ограничения задачи:    х3 = 19 - 2х1 - 5х2
Из первого ограничения Гомори:    S1 = 18 - 4х1 - 2х2

Получаем:    4х1 + 3х2 + S2 = 20, S2  0 или 4х1 + 3х2  20. Это ограничение отсекает от множества планов область, содержащую точку 2. Новый оптимальный нецелочисленный план - точка 3.

Третье ограничение Гомори :    2/7x3 + 6/7S2 - S3 = 4/7, S3  0
Из первого ограничения задачи:    х3 = 19 - 2х1 - 5х2
Из второго ограничения Гомори:    S2 = 20 - 4х1 - 3х2

После подстановки x3 и S2 в третье ограничение Гомори получаем: 4х1 + 4х2  22. Это ограничение отсекает от множества планов область, содержащую точку 3. Новый оптимальный нецелочисленный план - точка 4.

Четвертое ограничение Гомори :    1/4S3 - S4 = 1/2, S4  0
Из третьего ограничения Гомори:    S3 = 22 - 4х1 - 4х2

Получаем:    х1 + х2 + S4 = 5, S4  0. Отсюда имеем: х1 + х2  5. Это ограничение отсекает от множества планов область, содержащую точку 4. Новый оптимальный нецелочисленный план - точка 5.

Пятое ограничение Гомори :    1/3x4 + 2/3S4 - S5 = 2/3, S5  0
Из второго ограничения задачи:    х4 = 16 - 4х1 - х2
Из четвертого ограничения Гомори:    S4 = 5 - х1 - х2

Получаем:    2х1 + х2 + S5 = 8, S5  0. Отсюда: 2х1 + х2  8. Это ограничение отсекает от множества планов область, содержащую точку 5. Оптимальный целочисленный план - точка 6 с координатами (3;2).

Заштрихованная часть - целочисленное множество планов.

4. Компьютерная реализация

Программа написана с использованием собственных функций и процедур и трех стандартных модулей System, Crt и Graph.

При запуске программы она проверяет возможно ли использование графического интерфейса. Если это возможно то программа переходит к следующему этапу.

Далее процедурой ShowXOY Рисуется на экран координатные оси. На этом работа этой процедуры заканчивается и пользователь в следующей процедуре (EnterNerav и в частности в подпроцедуре GetNerav) предлагается ввести коэффициенты неравенства a1x+a2y=b в следующем порядке: a1 пробел a2 пробел b. Сразу после ввода всех коэффициентов процедурой ShowLine рисуется нужная линия. После нажатия [Esc] процедура EnterNerav заканчивается и передает управление процедуре EnterMainF в которой пользователю предлагается ввести коэффициенты целевой функции. Далее работа переходит к процедуре GetResult где идет подсчет оконцательного товета с помощбю процедуры SolveOprtel где считаетя определитель т. е. точки пересечения целевой функции с каждой линией ограничения. Далее выводится ответ, если это возможно.

Далее следует описание используемых стандартных процедур и функций.

Процедуры и функции модуля System:

Function Frac(X : Real) : Real;

Возвращает дробную часть аргумента.

Параметр X - выражение вещественного типа. Результат - дробная часть X, то есть Frac(X) = X-Int(X).

Procedure Str(X [: Width [: Decimals ]]; Var S : String);

Преобразовывает число в строку. Преобразовывает числовое значение X в строковое представление этого числа, которое можно выводить операторами типа Write и OutText.

Function Round(X : Real) : Longint;

Округляет значение вещественного типа до значения целочисленного типа. X - выражение с реальным типом. Round возвращает значение типа Longint, которое является значением X, округленного к самому близкому целому числу. Если X - ровно посередине между двумя целыми числами, то результатом будет число с самой большой абсолютной величиной.

Если округленное значение X ненаходится внутри допустимого диапазона Longint, то происходит ошибка во время выполнения программы.

Модуль Crt:

В модуле Crt находятся мощные подпрограммы, которые дают вам возможность полного управления возможностями вашего PC.

Подпрограммы модуля Crt обеспечивают контроль над текстовыми режимами экрана, расширенными кодами клавиатуры, цветами, окнами и звуком.

Crt может использоваться только в программах, предназначенных для IBM PC, AT, PS/2 и полностью совместимых.

Procedure Read( [ var F : Text; ] V1 [ , V2, ..., VN ]); (текстовые файлы)

Читает одну или более величин из текстового файла в одну или более переменных. Параметры: F - необязательная переменная текстового файла, если не указана, то используется стандартная переменная Input; V1,...,VN - переменные типа Char, Integer, Real или String.

В случае переменной типа Char процедура Read считывает из файла один символ и присваивает его переменной. В случае переменной целого типа процедура Read ожидает поступления последовательности символов, образующих число со знаком, согласно принятому в Паскале синтаксису. Любые пробелы, знаки табуляции или метки конца строки, предшествующие числовой строке, пропускаются. Считывание прекращается при обнаружении первого пробела, символа табуляции или метки конца строки, которые следуют за числовой строкой, или в том случае, если функция Eof(F) принимает значение True. Если числовая строка не соответствует ожидаемому формату, то происходит ошибка ввода-вывода, в противном случае переменной присваивается считанное значение. Если Eof(F) принимала значение True перед выполнением процедуры Read, или Eof(F) приняла значение True при пропуске начальных пробелов, знаков табуляции или меток конца строки, то переменной присваивается нулевое значение. Следующая операция Read начнется с пробела, символа табуляции или метки конца строки, которыми завершилась числовая строка.

В случае переменной вещественного типа процедура Read ожидает поступления последовательности символов, которые образуют число со знаком в соответствии с принятым в Паскале синтаксисом за исключением того, что шестнадцатиричное представление не допускается. Любые пробелы, знаки табуляции или метки конца строки, предшествующие числовой строке, пропускаются. Считывание прекращается при обнаружении первого пробела, символа табуляции или метки конца строки, которые следуют за числовой строкой или в том случае, если функция Eof(F) принимает значение True. Если числовая строка не соответствует ожидаемому формату, то происходит ошибка ввода-вывода, в противном случае переменной присваивается считанное значение.

Если Eof(F) принимало значение True перед выполнением процедуры Read, или Eof(F) приняло значение True при пропуске начальных пробелов, знаков табуляции или меток конца строки, то переменной присваивается нулевое значение. Следующая операция Read начнется с пробела, символа табуляции или метки конца строки, которыми завершилась числовая строка.

Procedure Write( [ var F : Text; ] P1 [ , P2,..., PN ] ); (текстовые файлы) Записывает одну или более величин в текстовый файл. F - переменная текстового файла, если не указана, то предполагается использование стандартной файловой переменной Output, P1,...,PN - параметры записи, которые содержат выводимые выражения типов Char, Integer, Real, String, Packed String или Boolean. Параметр записи также может содержать спецификацию ширины поля и количество десятичных знаков. Параметр записи имеет следующий вид: OutExpr [ : MinWidth [ : DecPlaces ] ], где OutExpr представляет собой выводимое выражение, MinWidth - целое число, задающее минимальную ширину поля, которая должна быть больше нуля. Записывается ровно столько символов, сколько определено в MinWidth (при необходимости используются ведущие пробелы) за исключением случаев, когда OutExpr имеет значение, которое должно быть представлено большим количеством символов, чем указано в MinWidth. В этом случае записывается количество символов, достаточное для представления выводимой величины. Аналогично, если параметр MinWidth опущен, то записывается необходимое количество символов. DecPlaces задает число десятичных знаков в представлении вещественного значения с фиксированной точкой. Оно может указываться только в том случае, если OutExpr имеет тип Real, и указан параметр MinWidth. Если параметр MinWidth указан, то он должен быть больше или равен нулю.