Математические модели

S – размер склада, предусмотренного для хранения изделий, выраженный в количествах изделий;

C_kl – себестоимость изготовления k-го наименования l-м способом (k= , l= )

C_Оl – требуемая себестоимость изготовления изделия k-го наименования (k= )

П_k – прибыль от реализации изделия k-го наименования (k= )

3. Управляющие переменные:

X_kl – число изделий k-го наименования, выпускаемых l-м способом (k= , l= )

4. Определение области допустимых решений.

(1.3)

i= – ограничение по фонду работы оборудования;

(1.4)

ограничение по размеру  склада;

k=

(1.5)

ограничение по спросу;

k= , хkl 0, l=

(1.6)

ограничение по себестоимости  изготовления;

5. Выражение критерия эффективности через параметры и управляющие переменные модели.

1) Максимизация прибыли.

П – суммарная прибыль.

П= max

(1.7)

2) Минимизация себестоимости.

Является критерием  при отсутствии ограничения (1.6)

С= min

(1.8)

3)

а) Минимизация суммарного времени обработки Т, выраженного, например, в станко-часах.

T= min

(1.9)

б) Минимизация суммарного времени обработки T_l, выраженного в часах.

Tl= min

(1.10)

В формуле (1.10) предполагается, что станки начинают работать одновременно и работают параллельно.

Таким образом, построены  три однокритериальные линейные модели:

(1.3) – (1.7) — формирование  производственного заказа по  критерию максимизации прибыли;

(1.3) – (1.5), (1.6), (1.8) — организация производственного процесса по критерию минимальной себестоимости изготовления;

(1.3) – (1.6), (1.9), (1.3) –  (1.6), (1.10) — организация производственного  процесса по критерию минимального времени изготовления.

Если прибыль нелинейно зависит от числа выпускаемых изделий,

П= max,

(1.11)

где f – некоторая нелинейная функция, то переходим к нелинейной оптимизационной модели (1.3) – (1.6), (1.11).

Модели (1.3) – (1.6), (1.7), (1.9) или (1.3) – (1.6), (1.7), (1.10) являются многокритериальными.

Решениями исходной задачи, получаемыми в результате расчета  любой из предложенных моделей, служат значения переменных х_kl; k= ; l= , которые удовлетворяют ограничениям, сформулированным в пункте 4 (при определении области допустимых решений), и доставляют экстремум одному или нескольким выбранным критериям оптимизации.

Задача 2.

Фирма должна отправить  некоторое количество кроватей с  трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице 1.1 – Стоимость перевозок.

Таблица 1.1 – Стоимость перевозок

Склады	Магазины
	В1	В2	В3	В4	В5
А1	1	0	3	4	2
А2	5	1	2	3	3
А3	4	8	1	4	3

Как следует спланировать перевозку, чтобы её стоимость была минимальной?

Построение математической модели.

Пусть Хij – количество кроватей, отправляемых со склада i в магазин j. Все Хij 0, и в силу ограничений на возможности поставки со складов (предложение) и спрос в магазинах они удовлетворяют следующим условиям:

 

(для предложения)

(для спроса)

Стоимость перевозок  равна

F=1*x₁₁+0*x₁₂+3*x₁₃+4*x₁₄+2*x₁₅+5*x₂₁+…+4*x₃₄+3*x_35.

Таким образом, имеем  следующую математическую модель

F=1*x₁₁+0*x₁₂+3*x₁₃+4*x₁₄+2*x₁₅+5*x₂₁+…+4*x₃₄+3*x₃₅,

Рассмотренная задача является задачей линейного программирования, но специального вида. Её результат можно обобщить на транспортную задачу общего вида.

 

2 РЕАЛИЗАЦИЯ МАТЕМАТИЧЕСКОГО

МОДЕЛИРОВАНИЯ С ПОМОЩЬЮ ЭВМ

2.1 Постановка задачи

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

Транспортная задача.

Однородный груз, имеющийся  в m пунктах отправления (производства) А₁, А₂, ..., А_m соответственно в количествах а₁, а₂, ..., а_m единиц, требуется доставить в каждый из n пунктов назначения (потребления) В₁, В₂, ..., В_n соответственно в количествах b₁, b₂ ..., b_n единиц. Стоимость перевозки (тариф) единицы продукции из А_i в В_j известна для всех маршрутов A_iB_j и c_ij (i=1,m; j=1,n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех пунктов потребления удовлетворяются (закрытая модель), то есть

, а суммарные транспортные расходы минимальны.

Математическая модель транспортной задачи

Будем называть любой  план перевозок допустимым, если он удовлетворяет системам ограничений и требованием неотрицательности.

Допустимый план, будем  называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

План будет называться оптимальным, если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок.

Рассмотрим постановку задачи и реализацию программного модуля для задачи 2.

Решение задачи разбивается на два этапа:

1. Определение опорного плана
2. Нахождение оптимального решения, путем последовательных операций

Допустимое (опорное) решение транспортной задачи можно найти, используя метод "северо-западного угла" или метод "минимального элемента".

Для нахождения оптимального плана для рассматриваемой задачи можно воспользоваться методом потенциалов.

Так как решение транспортной задачи является отдельной, большой  по объему, задачей, в данной работе не будем его рассматривать. Отметим только, что решая задачу 2 указанными методами, получим ответ

F=1*15+1*12+3*8+3*5+4*5+1*5+3*10=121.

2.2 Разработка программы

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

Процедуры и функции  модуля 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 находятся мощные подпрограммы, которые дают нам возможность полного управления возможностями нашего компьютера.

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