close

Вход

Забыли?

вход по аккаунту

- Ухтинский государственный технический университет

код для вставкиСкачать
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ухтинский государственный технический университет»
(УГТУ)
Математические модели
информационных процессов управления
Методические указания
Ухта, УГТУ, 2014
УДК 519.87 (076)
ББК 22.18 я7
K 88
Кудряшова, О. М.
К 88
Математические модели информационных процессов управления [Текст] : метод. указания / О. М. Кудряшова. – Ухта : УГТУ,
2014. – 64 с.
Методические указания предназначены для студентов очной формы обучения
по направлению 230100 Информатика и вычислительная техника квалификации
«бакалавр», профиль подготовки «Автоматизированные системы обработки
информации и управления». Могут быть использованы для изучения алгоритмов оптимизации в задачах линейного программирования в рамках дисциплины
«Математические модели информационных процессов управления» при выполнении лабораторных и курсовой работ.
УДК 519.87 (076)
ББК 22.18 я7
Методические указания рассмотрены и одобрены заседанием кафедры АИС от
14.05.2014 г. протокол №9.
Рецензент: А. Г. Куделин, зав. кафедрой АИС Ухтинского государственного
технического университета, к.т.н.
Редактор: И. А. Базарова, доцент кафедры АИС Ухтинского государственного
технического университета.
Корректор: П. В. Котова. Технический редактор: Л. П. Коровкина.
В методических указаниях учтены предложения рецензента и редактора.
План 2014 г., позиция 78.
Подписано в печать 29.08.2014 г. Компьютерный набор.
Объём 64 с. Тираж 50 экз. Заказ №287.
© Ухтинский государственный технический университет, 2014
169300, Республика Коми, г. Ухта, ул. Первомайская, д. 13.
Типография УГТУ.
169300, Республика Коми, г. Ухта, ул. Октябрьская, д. 13.
Оглавление
1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ...................................................................................... 4 1.1. Общие сведения .......................................................................................................................... 4 1.2. Задачи распределения ресурсов................................................................................................. 4 1.2.1. Программная реализация задачи распределительного типа ........................................... 8 1.2.2. Лабораторная работа №1 .................................................................................................. 15 1.3. Транспортные задачи ................................................................................................................ 16 1.3.1. Метод северо-западного угла ........................................................................................... 19 1.3.2. Метод минимальной стоимости....................................................................................... 20 1.3.3. Приближенный метод Фогеля .......................................................................................... 20 1.3.4. Метод потенциалов ........................................................................................................... 21 1.3.5. Программная реализация решения транспортной задачи ............................................. 23 1.3.6. Лабораторная работа №2 .................................................................................................. 33 1.4. Задачи на графах ....................................................................................................................... 34 1.4.1. Минимизация сети ............................................................................................................ 35 1.4.1.1. Алгоритм Прима. ....................................................................................................... 35 1.4.1.2. Программная реализация алгоритма Прима ........................................................... 36 1.4.1.3. Алгоритм Краскала. ................................................................................................... 41 1.4.1.4. Программная реализация алгоритма Краскала ....................................................... 42 1.4.2. Алгоритм нахождения кратчайшего пути....................................................................... 46 1.4.2.1. Алгоритм Дейкстры. .................................................................................................. 46 1.4.2.2. Алгоритм Флойда. ..................................................................................................... 49 1.4.3. Лабораторная работа №3 .................................................................................................. 52 1.5. Курсовая работа ........................................................................................................................ 52 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ............................................................................................ 64 3
1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
1.1. Общие сведения
Классификацию математических моделей можно рассматривать по следующим элементам: исходным данным, искомым переменным, зависимостям,
описывающим целевую функцию и ограничения.
Таблица 1 – Классификация математических моделей
Исходные данные
Переменные
Детерминированные Непрерывные
Целочисленные
Непрер., целочисл.
Случайные
Непрерывные
Зависимости
Линейные
Линейные
Нелинейные
Линейные
Задача
Обозначения
Лин. прогр-я.
ЛП
Целоч. прогр-я
ЦЧП
Нелин. прогр-я
НЛП
Стохастич. прогр-я
СТП
Линейное программирование (ЛП) – это наука о методах исследования и
нахождения экстремальных значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой. Ограничения, записанные с помощью неравенств – системой ограничений.
Направление оптимизации целевой функции (max или min) называется критерием оптимальности.
1.2. Задачи распределения ресурсов
В общем виде математическая модель задачи ЛП распределительного типа может быть записана в виде:
max Z = C1X1 + C2X2 + … + CnXn
(min)
При ограничениях:
a11 x1  a12 x2    x1n xn  b1
a x  a x    x x  b
 21 1
22 2
2n n
2


am1 x1  am 2 x2    xmn xn  bm,
где
x1, x2, …, xn ≥ 0
либо max Z   C j X j
j
(min)
при ограничениях
a x
ij
j
 bi ; хj ≥ 0 (i = 1…m; j = 1…n)
j
4
Допустимым решением (планом) задачи ЛП можно считать вектор х = (х1,
х2, …, хn), удовлетворяющий системе ограничений. Множество допустимых
решений образуют область допустимых решений. Допустимое решение, при
котором целевая функция достигает своего экстремального значения (max или
min), называется оптимальным. Основной способ решения задачи ЛП – алгебраический. Он используется для решения задач с любым количеством переменных. Алгебраический метод решения задач ЛП называется симплекс-методом.
Прежде чем использовать симплекс-метод для решения линейных моделей, их
необходимо привести к стандартной форме:
 все ограничения записываются в виде равенств с неотрицательной
правой частью;
 значения всех переменных неотрицательны;
 целевая функция подлежит максимизации или минимизации.
Нахождение оптимального решения начинается с исходной, допустимой
угловой точки (обычно начала координат). Все переходы осуществляются к
смежным угловым точкам, каждая из которых предварительно проверяется на
оптимальность. Рассмотрим математическую модель, приведённую к стандартной форме, где n – количество переменных, m – количество ограничений.
Z = 3х1 + 2х2 + 0S1 + 0S2 + 0S3 + 0S4.
 х1  2 х2  S1  6
2 х  х  S  8
2
2
 1
  х1  х2  S3  1
х  S  2
4
 2
 х1 , х2 , S1 , S 2 , S3 , S 4  0
Рисунок 1 – Графический способ решения задачи ЛП
5
(1)
Вычислительные процедуры симплекс-метода:
 определить начальное допустимое базисное решение, приравнивая к
нулю (n – m) небазисных переменных;
 из числа небазисных переменных выбрать включаемую в новый базис
переменную, увеличение которой обеспечит улучшение значения целевой
функции. Если такой переменной нет, то значение оптимально и решение заканчивается, иначе переходим к следующему шагу;
 из числа переменных текущего базиса выбрать исключаемую переменную;
 найти новое базисное решение и перейти к шагу 1.
Рассмотрим предыдущий пример (1): в качестве начального решения используется решение, в котором две (6-4) переменные принимаются равными
нулю. Если взять x1 = x2 = 0, это обеспечит допустимость начального базисного
решения: s1 = 6, s2 = 8, s3 = 1, s4 = 2. Данное решение соответствует точке A
(началу координат) на графике. Занесем все данные в симплекс-таблицу
(табл. 3). В общем виде симплекс-таблица представлена в таблице 2.
Таблица 2 – Симплекс таблица в общем виде
Базисные пер.
x1
xn
S1
x2 …
Z
0
 c1
 cn
 c2 …
1
S1
a12 …
a11
a1n
0
S2
a22 …
a21
a2n
….
…
Sm
am1
…
am 2 …
…
…
0
amn
S 2...
Sm
Решение
0…
0
0
0…
0
1…
0
1
2
…
0…
…
1
…
m
xj – небазисные переменные (j = 1, 2 … n), si – базисные переменные
(i = 1, 2 … m).
Основные шаги симплекс метода:
 выбор включаемой в базис переменной: в задаче max выбирается cj –
минимальный отрицательный коэффициент, в задаче minсj – наибольший положительный. Соответствующий столбец называется ведущим столбцом;
 выбор исключаемой из базиса переменной: выбор k = min {i/aij’}, где
aij’ > 0 – коэффициент ведущего столбца. Соответствующая строка называется
ведущей строкой. Элемент на пересечении ведущего столбца и ведущей строки
называется ведущим элементом;
 поиск нового базисного решения осуществляется по методу ГауссаЖордана:
 новая ведущая строка = предыдущая ведущая строка / ведущий элемент: aij” = aij/k’, где aij – коэффициенты предыдущей ведущей строки, k’ – ведущий элемент;
6
 новое уравнение = предыдущее уравнение – (коэффициент ведущего
столбца предыдущего уравнения) · (новая ведущая строка): aij”’ = aij – (aij’ · aij”), где
aij’ – коэффициент ведущего столбца рассматриваемой строки.
Таблица 3 – 1 итерация
Базовые
переменные
Z
S1
S2
S3
S4
ведущий
элемент
x1
x2
S1
S2
S3
S4
Решение
-3
1
2
-1
0
-2
2
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
6
8
1
2
← ведущая строка
S2 – исключаемая
х1 – включаемая
↑
ведущий
столбец
Включаемая переменная в задаче max (min) – небазисная переменная, являющаяся в Z уравнении наименьшим (наибольшим) коэффициентом; в случае
равенства нескольких коэффициентов выбор делается произвольно. Если все
коэффициенты неотрицательны (не положительны) – полученное решение есть
оптимальное (условие оптимальности).
Условие допустимости: в качестве исключаемой переменной при max
(min) выбирается базисная переменная, для которой отношение постоянной в
правой части соответствующего ограничения к положительному коэффициенту
ведущего столбца – минимально, а в случае равенства нескольких отношений
выбор делается произвольно.
Поиск нового базисного решения осуществляется по методу ГауссаЖордана: новая ведущая строка = предыдущая ведущая строка / ведущий элемент; новое уравнение = предыдущее уравнение – (коэффициент ведущего
столбца предыдущего уравнения) · (новая ведущая строка).
Таблица 4 – 2 итерация
Базовые
переменные
Z
S1
Х1
S3
S4
Z:
_
-3
-3
0
S1:
_
1
1
0
x1
x2
S1
S2
S3
S4
Решение
0
0
1
0
0
-1/2
3/2
1/2
3/2
1
0
1
0
0
0
3/2
-1/2
1/2
1/2
0
0
0
0
1
0
0
0
0
0
1
12
2
4
5
2
-2
-3/2
-1/2
0
0
0
0
-3/2
3/2
0
0
0
0
0
0
0
-12
12
2
1/2
3/2
1
0
1
0
1/2
-1/2
0
0
0
0
0
0
6
4
2
7
2:3/2 = 4/3
4:1/2 = 8
5:3/2 = 10/3
2:1 = 2
На следующей итерации – x2 – включаемая, s1 – исключаемая переменные. Итерационный процесс будет продолжаться, пока в z-строке (в задаче
max) все переменные не станут положительными (табл. 5):
Таблица 5 – Оптимальное решение
Базисные
переменные
Z
x2
x1
S3
S4
Z
x1
x2
S1
S2
S3
S4
Решение
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1/3
2/3
-1/3
-1
-2/3
4/3
-1/3
2/3
1
1/3
0
0
0
1
0
0
0
0
0
1
38/3
4/3
10/3
3
2/3
1.2.1. Программная реализация задачи распределительного типа
1. Пример пользовательского интерфейса для решения задачи (1) приведен на рисунке 2.
Рисунок 2 – Исходные данные задачи ЛП
Результат работы программы приведён на рисунке 3. Пример программного кода на языке Delphi с подробными комментариями приведён ниже.
8
Рисунок 3 – Результат работы программы
…
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids,math;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Button1: TButton;
Button2: TButton;
9
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
type
tabl=array of array of string; //пользовательский тип
const
e=1e-08;
var
Form1: TForm1;
a,b:integer;
matr:tabl; //исходный массив данных
flag:boolean;
s:string;
mas:array[1..5,1..7] of real=((-3,-,0,0,0,0,0),(1,2,1,0,0,0,6),(2,1,0,1,0,0,8),
(-1,1,0,0,1,0,1), (0,1,0,0,0,1,2)); //исходные данные рассматриваемого примера
implementation
{$R *.dfm}
procedure vklper(m:tabl;a,b:integer; var k:integer);
var //нахождение включаемой в базис переменной
i,j:integer;
min:real;
begin
min:=0;
for i:=1 to b - 1 do
//нахождение минимального эл-та в z строке
if strtofloat(m[1,i])<min then
begin min:=strtofloat(m[1,i]); k:=i; end;
end;
procedure isklper(m:tabl; a,b:integer; k:integer; var l:integer);
var //нахождение исключаемой из базиса переменной
i,j:integer; min:real;
begin
min:=10E5;
for i := 2 to a - 1 do
//нахождение минимального отношения
10
if (strtofloat(m[i,k])>0)and (strtofloat(m[i,b-1])/strtofloat(m[i,k])<min)
then begin
min:=(strtofloat(m[i,b-1])/strtofloat(m[i,k]));
l:=i;
end;
end;
procedure newresh(a,b,k,l:integer;m1:tabl; var m:tabl);
var //пересчёт таблицы
i,j:integer;vedel,vedelstr,c:real;
begin
vedel:=strtofloat(m[l,k]);
//вычисление новой ведущей строки
for j:=1 to b - 1 do
m1[l,j]:=(floattostr(strtofloat(m[l,j])/vedel));
for I := 1 to a - 1 do begin
vedelstr:=strtofloat(m[i,k]);
if i<>l then begin // вычисление всех остальных строк
for j := 1 to b - 1 do begin
c:= (strtofloat(m[i,j])-(vedelstr*strtofloat(m1[l,j])));
if (c>-1e-10) and (c<1e-10) then c:=0;
m1[i,j]:=floattostr(c);
end;
end; end;
for i:=0 to a-1 do
for j:=0 to b - 1 do
m[i,j]:=m1[i,j];
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i,j:Integer;
begin //формирование таблицы
a:=strtoint(edit1.Text);
b:=strtoint(edit2.Text);
stringgrid1.RowCount:=b+2; //кол-во строк: кол-во ограничений+2
stringgrid1.ColCount:=b+a+2;
//кол-во столбцов: кол-во перем-х+кол-во огранич.+2
stringgrid1.cells[0,0]:='баз.пер-е';
stringgrid1.cells[0,1]:='Z';
for j := 2 to stringgrid1.rowcount do
11
stringgrid1.cells[0,j]:='X'+inttostr(j+a-1);
for i := 1 to stringgrid1.colcount-2 do
stringgrid1.cells[i,0]:='X'+inttostr(i);
stringgrid1.cells[stringgrid1.colcount-1,0]:='Решение';
for i:=1 to stringgrid1.RowCount-1 do
for j:=1 to stringgrid1.ColCount-1 do
stringgrid1.cells[j,i]:=floattostr(mas[i,j]);
end;
procedure TForm1.Button2Click(Sender: TObject);
var //основная программа
i,j,k,l:integer;
begin
a:=stringgrid1.RowCount;
b:=stringgrid1.ColCount;
setlength(matr,a,b);//выделение памяти под массив
for i:=0 to stringgrid1.RowCount-1 do
for j := 0 to stringgrid1.ColCount-1 do
matr[i,j]:= stringgrid1.cells[j,i];
flag:=true;
for i:=1 to stringgrid1.ColCount- 1 do
if (strtofloat(matr[1,i])<0) then flag:=false;
if flag then MessageDlg('Решение оптимально или данные введены неверно!',mtWarning,[mbOk],0);
while flag=false do //пока решение неоптимально
begin
//поиск включаемой в базис
vklper(matr,a,b,k);//возвращается номер столбца
isklper(matr,a,b,k,l);// возвращается номер строки
s:=matr[0,k];
//меняем состав базисных и небазисных
matr[l,0]:=s;
newresh(a,b,k,l,matr,matr);// пересчёт симплекс-таблицы
flag:=true;
for i:=1 to stringgrid1.ColCount- 1 do
if (strtofloat(matr[1,i])<0) then flag:=false;
end;
for i := 1 to a - 1 do
for j:= 1 to b - 1 do
stringgrid1.cells[j,i]:=formatfloat('#0.###',strtofloat(matr[i,j]));
for i:=0 to a-1 do
12
stringgrid1.cells[i,0]:=matr[0,i];
for j:=0 to b-1 do
stringgrid1.cells[0,j]:=matr[j,0];
for i:=0 to a-1 do
finalize(matr[i]);//освобождение памяти
finalize(matr);
end; end.
2. Полученное решение можно проверить с помощью надстройки «Поиск
решения» в пакете MS Excel (рис. 4, 5, 7). В ячейках A2, B2 располагаем
начальные значения переменных задачи X1 = 1, X2 = 1. В дальнейшем в этих
ячейках будут найдены оптимальные значения переменных. В ячейки B3-B6
вводятся формулы левых частей ограничений. В ячейки C3-C6 вводятся значения правых частей ограничений. В ячейку B7 вводится правая часть уравнения
целевой функции Z. Ввод формул начинается со знака «=» (рис. 4). Далее вызывается окно раздела меню «Данные/Поиск решения», в котором указываются
ссылки на ячейки целевой функции, ограничений, переменных задачи и
направление оптимизации: максимум или минимум (рис. 5).
Если надстройка «Поиск решения» не установлена, её необходимо
установить по разделу меню «Файл/ Параметры/ Надстройки». Выбрать
надстройку «Поиск решения» и по кнопке «Перейти» в окне «Надстройки»
установить её (рис. 6).
Рисунок 4 – Исходные данные на листе Excel
13
Рисунок 5 – Параметры в надстройке «Поиск решения»
Рисунок 6 – Установка надстройки «Поиск решения»
14
Рисунок 7 – Результаты решения задачи
1.2.2. Лабораторная работа №1
Написать программу, реализующую решение задачи ЛП симплекс-методом
в среде программирования Delphi. Содержательная постановка задачи: изготовление продукции двух видов (П1 и П2) требует использования двух видов сырья
(ресурсов S1 и S2). Запасы сырья каждого вида ограничены (количественные данные приведены в таблице 6). В таблице 6 также указано, сколько единиц сырья
необходимо для изготовления единицы каждого из видов продукции.
Таблица 6 – Исходные данные
Виды сырья
Запасы сырья
S1
S2
Доход
b1
b2
Виды продукции
П1
П2
a11
a12
a21
a22
c1
c2
Требуется составить такой план выпуска продукции, при котором доход
предприятия от реализации был бы максимальным.
Математическую модель задачи можно сформулировать так:
Пусть X1 и X2 – число единиц продукции соответствующего вида П1 и П2.
Запасы сырья ограничены величинами b1 и b2 единиц, т. е. система ограничений:
a11 x1  a12 x2  b1
a21 x1  a22 x  b2
2
x1 , x2  0
Целевая функция включает в себя сумму доходов от реализации продукции обоих видов S1 и S2, т. е. z  c1 x1  c2 x2 . Целевая функция подлежит
максимизации.
15
Номер варианта N совпадает с порядковым номером студента в журнале преподавателя. Значения коэффициентов в соответствии с номером варианта выбираются из таблиц. Для вариантов с 1 по 10 – из таблицы 7, для вариантов с 11 по 20 – из таблицы 8.
Таблица 7 – Значения коэффициентов для вариантов 1-10
N вар.
c1
c2
a11
a12
b1
a21
a22
b2
1
3
2
1
2
6
2
1
8
2
1
1
2
1
6
1
2
6
3
1
4
3
2
12
1
2
6
4
2
2
3
1
3
3
2
12
5
3
2
1
1
4
4
1
8
6
2
1
3
4
24
2
1
8
7
1
2
3
1
6
1
1
5
8
3
4
1
1
6
2
1
8
9
2
3
1
1
7
2
1
10
10
4
5
1
2
8
4
3
24
19
2
3
1
1
7
1
2
10
20
4
5
2
1
8
3
4
24
Таблица 8 – Значения коэффициентов для вариантов 11-20
N вар.
с1
с2
a11
a12
b1
a21
a22
b2
11
3
2
2
1
6
1
2
8
12
1
1
1
2
6
2
1
6
13
1
4
2
3
12
2
1
6
14
2
2
1
3
3
2
3
12
15
3
2
1
1
4
1
4
8
16
2
1
4
3
24
1
2
8
17
1
2
1
3
6
1
1
5
18
3
4
1
1
6
1
2
8
1.3. Транспортные задачи
Транспортная модель (рис. 8) используется для предоставления наиболее
экономичного плана перевозки одного вида продукции из нескольких исходных
пунктов в пункты назначения. Для построения транспортной модели используются следующие величины:
 объём производства в каждом исходном пункте аi;
 спрос в каждом пункте назначения bj;
 стоимость перевозки единицы продукции из каждого исходного пункта
в каждой пункт назначения cij.
Цель задачи состоит в определении количества продукции xij, которое
следует перевезти из каждого исходного пункта в каждый пункт назначения,
чтобы транспортные расходы были минимальными.
16
Рисунок 8 – Транспортная модель перевозки продукции
m
n
min Z   CijXij
i 1 j 1

 xij  ai
 j 1
m
 xij  b j
 i 1
 xij  0


Транспортная задача называется сбалансированной или закрытой, если
суммарный объём производства равен суммарному спросу:
n
m
n
i 1
j 1
 ai   b j
Тогда в ограничениях знаки неравенства меняются на знаки равенства:
 n
 xij  ai
 j 1
m
 xij  b j
 i 1
 xij  0


Сбалансированность модели является обязательным условием применения специальных методов решения транспортной задачи. Транспортная модель
может быть представлена с помощью транспортной таблицы (рис. 9), строки
которой соответствуют исходным пунктам, столбцы – пунктам назначения, коэффициенты Сij располагаются в правом верхнем углу каждой ячейки.
17
b1
a1
x11
a2
x21
b2
c11
c21
x12
x22
c12
c22
Рисунок 9 – Транспортная таблица
Пример: В исходных пунктах имеются запасы продукции 90, 400 и 110
тонн. Потребители должны получить продукт в количестве 140, 300, 160 тонн.
Найти такое распределение груза, чтобы затраты на перевозку были минимальными, если матрица затрат имеет вид:
 2 5 2
C   4 1 5 
3 6 8


3
3
i 1
j 1
 ai   b j  600
b1
b2
a1
a2
a3
спрос
b3
2
5
2
Объём
90
4
1
5
400
3
6
8
140
300
160
110
Рисунок 10 – Транспортная таблица
min Z = 2 х11 + 5 х12 + 2х13 + 4х21 + х22 + 5х23 + 3х31 + 6х32 + 8х33
(2)
х11 + х12 + х13 = 90
х21 + х22 + х23 = 400
х31 + х32 + х33 = 110
х11 + х21 + х31 = 140
х12 + х22 + х32 = 300
х13 + х23 + х33 = 160
xij ≥ 0
В данном случае задача (2) сбалансирована, т. е. сумма объёмов производства равна сумме спросов: 90 + 400 + 110 = 140 + 300 + 160 = 600. Если задача не сбалансирована, вводится дополнительный фиктивный исходный пункт
или пункт назначения, куда распределяется избыток или недостаток продукции.
Т. к. пункт фиктивный, то стоимость перевозки берётся, равной 0, если не
18
предусмотрены штрафы за недопоставку продукции. Специальные методы решения транспортной задачи повторяют шаги симплексалгоритма:
 Нахождение начального допустимого решения или опорного плана.
 Проверка его на оптимальность.
 Нахождение нового решения, если решение не оптимально.
Нахождение начального допустимого решения можно осуществить тремя
способами:
 правило северо-западного угла;
 метод минимальной стоимости;
 приближённый метод Фогеля.
1.3.1. Метод северо-западного угла
Переменной х11 придадим минимальное значение по объёму производства
и по спросу. Вычеркнем строку или столбец, где ограничение на спрос или на
объём производства выполнено. Скорректируем спрос или объём производства.
Перейдём к ближайшей не вычеркнутой ячейке таблицы. Процесс распределения завершается, когда остаётся не вычеркнутой одна строка или столбец
(рис. 11).
b1
a1
a2
a3
спрос
b2
b3
2
90
4
50
5
1
300
3
140
6
300
50
110
8
2
Объём
90
5
400
110
160
Рисунок 11 – Решение методом северо-западного угла
Базисными переменными являются переменные, соответствующие заполненным клеткам таблицы (рис. 11), т. е. x11, x21, x22, x23, x33. Количество базисных
переменных определяется по формуле: m + n – 1, где m и n – количество строк и
столбцов соответственно. Общие затраты на перевозку:
Z = 9  2 + 50  4 + 300 + 50  5 + 110  8 = 1810 д. е.
Количество перевозимой продукции:
0 
 90 0

X   50 300 50 
0
0 110 

19
1.3.2. Метод минимальной стоимости
Из всей таблицы ищется ячейка, которой соответствует наименьшая стоимость, ей придадим минимальное значение по объёму производства и по спросу. Если таких переменных несколько, то выбирается любая. Вычёркивается
строка или столбец, где ограничение выполнено, корректируются спросы и
объёмы производства. Далее среди не вычеркнутых ищется ячейка с минимальной стоимостью. Процесс завершается, когда остаётся не вычеркнутой одна
строка или столбец (рис. 12).
b1
a1
a2
a3
спрос
b2
b3
2
30
110
140
4
5
1
300
3
6
300
90
70
8
2
Объём
90
5
400
110
160
Рисунок 12 – Решение методом минимальной стоимости
 х22 = 300, так как С22 = 1 – min; столбец 2 – вычеркнут;
 х13 = 90; строка 1 – вычеркнута;
 х31 = 110; строка 3 – вычеркнута;
 х21 = 30; столбец 1 – вычеркнут;
 х23 = 70; строка 2 – вычеркнута.
Общие затраты: Z = 90  2 + 30  4 + 300 + 70  5 + 110  3 = 1 280 денежных единиц
Количество перевозимой продукции:
0 90 
 0
X   30 300 70 
110 0
0 

1.3.3. Приближенный метод Фогеля
1. Вычислить штраф для каждой строки и столбца, вычитая наименьшее
значение стоимости строки или столбца из следующего за ним элемента (по величине стоимости) той же строки или столбца.
2. В строке или столбце с самым большим штрафом выбрать переменную
с самой низкой стоимостью и придать ей минимальное значение по спросу и
объёму производства. Скорректировать значение спроса и объёма, вычеркнуть
20
строку или столбец, где ограничение выполняется. Строка или столбец с нулевым значением производства или спроса в дальнейших вычислениях не участвует. Если остается не вычеркнутой строка или столбец с положительным объёмом производства или спроса, найти базисную переменную с помощью метода
наименьшей стоимости. Если всем не вычеркнутым строкам или столбцам соответствуют нулевые объемы производства и спроса, найти нулевые базисные
переменные, используя метод минимальной стоимости.
3. Вычислить новые значения штрафов для не вычеркнутых строк и
столбцов, перейти к пункту 2. Вычисления продолжаются, пока останется не
вычеркнутой одна строка или столбец. Количество базисных переменных:
m + n - 1 (рис. 13).
b1
b2
a1
2
a2
30
a3
110
4
b3
5
1
300
3
2
4
5
90
70
6
8
Спрос
140
300
160
Штрафы
1
1
2
4
4
4
-
3
3
3
5
-
Объём
90
Штрафы
3
2 2 -
-
400
3
1
1
1
4
110
3
5
-
-
-
Рисунок 13 – Решение методом Фогеля
m + n – 1 = 5 – количество базисных переменных, Z = 1 280 денежных единиц.
1.3.4. Метод потенциалов
Метод потенциалов (рис. 14) используется для проверки полученного
начального решения на оптимальность. В методе потенциалов строке i и столбцу j транспортной таблицы ставятся в соответствие так называемые потенциалы
Ui и Vj. Для каждой базисной переменной хij они должны удовлетворять следующему условию: Ui + Vj = Cij. Это приводит к системе из m + n – 1 уравнений,
решая которую получаем значения потенциалов, предполагая, что U1 = 0.
Оценки для небазисных переменных хij определяются из соотношения:
Ui + Vj – Cij = Ĉij (Ĉij – оценка для небазисной переменной). Если все оценки для
небазисных переменных неположительные, т. е. нулевые или отрицательные, то
решение оптимально (аналогично условию оптимальности симплекс-метода в
21
задаче минимизации). Если решение неоптимальное, необходимо выбрать
включаемую в базис переменную и исключаемую из базиса переменную. Для
включения в базис выбирается переменная с положительной наибольшей оценкой небазисной переменной.
V1 = 1
U1 = 0
2
-1
U2 = 3
30
U3 = 2
110
4
V2 = - 2
5
-7
1
300
3
V3 = 2
90
70
6
-6
2
5
8
-4
Рисунок 14 – Проверка начального решения методом потенциалов
Сначала вычисляем потенциалы Ui и Vj по базисным переменным:
х13 : U1 + V3 = C13 или 0 + V3 = 2 или V3 = 2;
х23 : U2 + V3 = C23 или U2 + 2 = 5 или U2 = 3;
х22 : U2 + V2 = C22 или 3 + V2 = 1 или V2 = -2;
х21 : U2 + V1 = C21 или 3 + V1 = 4 или V1 = 1;
х31 : U3 + V1 = C31 или U3 + 1 = 3 или U3 = 2.
Затем вычисляем оценки для небазисных переменных:
U1 + V1 – C11 = Ĉ11 или 0 + 1 – 2 = Ĉ11 или Ĉ11 = -1;
U1 + V2 – C12 = Ĉ12 или 0 – 2 – 5 = Ĉ12 или Ĉ12 = -7;
U2 + V2 – C22 = Ĉ22 или 2 – 2 – 6 = Ĉ22 или Ĉ22 = -6;
U3 + V3 – C33 = Ĉ33 или 2 + 2 – 8 = Ĉ33 или Ĉ33 = -4.
Так как все оценки для небазисных переменных отрицательны, то решение оптимально. Если решение не оптимально, необходимо найти исключаемую из базиса переменную, включаемую в базис переменную и построить контур перераспределения количества перевозимой продукции. Этот метод эквивалентен условию допустимости в симплекс-методе. Строится замкнутый цикл,
который начинается и заканчивается выбранной небазисной переменной, имеющей наибольшее положительное значение. Эта переменная будет включена в
базис на следующей итерации. Каждая ячейка, стоящая на изломе цикла (контура перераспределения), должна содержать базисную переменную. Направление цикла может быть любым. Для каждого базисного решения и соответствующей небазисной переменной строится только один цикл. Если значение включаемой в базис переменной увеличивается на 1, то для сохранения допустимости решения значения базисных переменных на изломах цикла корректируются. Исключаемая из базиса переменная имеет наименьшее значение из значений
ячеек, помеченных знаком «-». Все значения корректируются на эту величину.
Ячейки, помеченные «+» увеличиваются, ячейки, помеченные «-». уменьшаются. Оптимальность нового базисного решения снова проверяется вычислением
22
потенциалов. Процесс продолжается до тех пор, пока не будет получено оптимальное решение.
1.3.5. Программная реализация решения транспортной задачи
1. Результат работы программы на примере задачи (2) (рис. 15) и пример
программного кода приведены ниже.
Рисунок 15 – Результат работы программы
…
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, Menus;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
23
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
StringGrid2: TStringGrid;
StringGrid3: TStringGrid;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
MainMenu1: TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
N5: TMenuItem;
Edit3: TEdit;
Label6: TLabel;
Label7: TLabel;
N6: TMenuItem;
StringGrid4: TStringGrid;
StringGrid5: TStringGrid;
StringGrid6: TStringGrid;
Edit4: TEdit;
Edit5: TEdit;
procedure N2Click(Sender: TObject);
procedure N3Click(Sender: TObject);
procedure N4Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure N5Click(Sender: TObject);
procedure N6Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
type
Perevozka=record
24
x:real; // кол-во перевозимой продукции
c:real; //стоимость перевозки
flag:boolean;//признак вычеркнутой ячейки
nbaz_p:real; //значение небазисной переменной
metka:char;// ячейка, помеченная + или end;
mass=array of array of Perevozka;
var
Form1: TForm1;
mas:mass;
A:array of real;// спрос
B:array of real;// объём
m,n:integer; //кол-во строк, столбцов
z1,z2:real;
u,v:array of real;//массивы потенциалов
implementation
{$R *.dfm}
Procedure min(mm:mass; var k,l:integer);
//нахождение минимального значения затрат из невычеркнутых ячеек
var minimum:perevozka;
i,j:integer;
begin
minimum.c:=10e5;
for i:=0 to m-1 do
for j:=0 to n-1 do
if (mm[i,j].c<minimum.c) and (mm[i,j].flag=false) then
begin
minimum:=mm[i,j];
k:=i; l:=j;
end;
end;
procedure f1(p:integer; var k,l:integer);
//нахождение базисной переменной в строке
var
j:integer;
begin
k:=-1;l:=-1;
25
for j := 0 to n-1 do
if (mas[p,j].x<>-1) and (mas[p,j].flag=false)then begin
k:=p;l:=j;
end;
if (k<>-1) and (l<>-1) then
mas[k,l].flag:=true;
end;
procedure f2(p:integer; var k1,l1:integer); //нахождение базисной в столбце
var
i:integer;
begin
k1:=-1;l1:=-1;
for I := 0 to m-1 do
if (mas[i,p].x<>-1) and (mas[i,p].flag=false) then begin
k1:=i;
l1:=p;end;
if (k1<>-1) and (l1<>-1) then
mas[k1,l1].flag:=true;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
edit1.Clear;
edit2.Clear;
edit3.Clear;
//edit1.SetFocus;
end;
procedure TForm1.N2Click(Sender: TObject);//формирование таблицы
var
i,j:integer;
begin
m:=strtoint(edit1.Text);//кол-во строк
n:=strtoint (edit2.Text);// кол-во столбцов
try
begin
Stringgrid1.Colcount:=n+1;
Stringgrid1.RowCount:=m+1;
Stringgrid4.Colcount:=n+1;
26
Stringgrid4.RowCount:=m+1;
for i:=1 to n+1 do
Stringgrid1.Cells[i,0]:=inttostr(i);
for i:=1 to n+1 do
Stringgrid4.Cells[i,0]:=inttostr(i);
for i:=1 to n+1 do
Stringgrid1.Cells[0,i]:=inttostr(i);
for i:=1 to n+1 do
Stringgrid4.Cells[0,i]:=inttostr(i);
Stringgrid2.Colcount:=1;
Stringgrid2.RowCount:=m+1;
Stringgrid3.Colcount:=n+1;
Stringgrid3.RowCount:=1;
end;
except
on EConvertError do
begin
showmessage('Введите количество исходных пунктов и пунктов назначения');
edit1.SelectAll;
edit1.setfocus; exit;
end;
end;
end;
procedure TForm1.N3Click(Sender: TObject); //ввод данных и балансировка
var
i,j:integer;
s1,s2:real;
begin
setlength(mas,m,n); //отводится память под динамические массивы
setlength(A,n);
setlength(B,m);
for I := 1 to m do
for j:=1 to n do begin
mas[i-1,j-1].c:=strtofloat(stringgrid1.Cells[j,i]); //заполнение затрат
mas[i-1,j-1].x:=-1; //заполнение кол-ва перевозимой продукции (-1)
mas[i-1,j-1].flag:=false; //вычёркивание ячеек, изначально false, т. е.
27
//ячейка не вычеркнута
mas[m-1,j].metka:=' '; //ячейка будет помечена + или - в методе потенциалов, изначально заполняется пробелом
end;
for i:=1 to n do
a[i-1]:=strtofloat(stringgrid3.Cells[i,0]);
for i:=1 to m do
b[i-1]:=strtofloat(stringgrid2.Cells[0,i]);
s1:=0;s2:=0;
for i:=1 to n do
s1:=s1+a[i-1]; //общий спрос суммируется
for i:=1 to m do
s2:=s2+b[i-1]; //общий объём производства суммируется
if s1>s2 then // если спрос больше объёма производства
begin
m:=m+1; //добавление строки
setlength(mas,m,n); //добавляем строку – фиктивный исходный пункт
for j := 0 to n-1 do begin //заполнение новой ячейки
mas[m-1,j].c:=0; //стоимость перевозки нулевая
mas[m-1,j].x:=-1;
mas[m-1,j].flag:=false;
mas[m-1,j].metka:=' ';
end;
stringgrid1.RowCount:=stringgrid1.RowCount+1;
stringgrid1.Cells[0,m]:=inttostr(m);
for j := 1 to n do
stringgrid1.Cells[j,m]:=inttostr(0);
setlength(b,m); //добавляем строку в массив объёмов
stringgrid2.rowcount:=stringgrid2.rowcount+1;
stringgrid2.Cells[0,m]:=floattostr(s1-s2); //разность между общим спросом
//и объёмом и объёмом производства
b[m-1]:=s1-s2;
end;
if s2>s1 then //если объём больше спроса
begin
n:=n+1; //добавление столбца
setlength(mas,m,n);//добавляем столбец – фиктивный пункт назначения
28
for i:=0 to m-1 do begin //заполнение новой ячейки
mas[i,n-1].c:=0; //обнуляем стоимость перевозки
mas[i,n-1].x:=-1;
mas[i,n-1].flag:=false;
mas[m-1,j].metka:=' ';
end;
stringgrid1.colcount:=stringgrid1.colcount+1;
stringgrid1.Cells[n,0]:=inttostr(n);
for i:= 1 to m do
stringgrid1.Cells[n,i]:=inttostr(0);
setlength(a,n); //добавляем столбец в массив спросов
stringgrid3.colcount:=stringgrid3.colcount+1;
stringgrid3.Cells[n,0]:=floattostr(s2-s1);//разность между общим
//объёмом производства и спросом
a[n-1]:=s2-s1;
end;
end;
procedure TForm1.N4Click(Sender: TObject);//метод северо-западного угла
var
i,j,k:integer;
begin
i:=0;
j:=0;
while not(mas[i,j].flag)and (i<=m)and(j<=n) do //до тех пор, пока
//все ячейки не вычеркнуты
begin
if (b[i]>=a[j]) then begin
mas[i,j].x:=a[j];
b[i]:=b[i]-a[j];
stringgrid2.Cells[0,i+1]:=floattostr(b[i]);
for k:=i+1 to m-1 do
mas[k,j].flag:=true; j:=j+1; //вычёркивание строки
end else
if (b[i]<=a[j]) then begin
mas[i,j].x:=b[i];
a[j]:=a[j]-b[i];
29
stringgrid3.Cells[j+1,0]:=floattostr(a[j]);
for k:=j+1 to n-1 do
mas[i,k].flag:=true; i:=i+1; //вычёркивание столбца
end;
end; z1:=0;
for i:=1 to m do
for j:=1 to n do begin
stringgrid1.cells[j,i]:= floattostr(mas[i-1,j-1].x); //вывод количества
// перевозимой продукции
if mas[i-1,j-1].x<> (-1) then //подсчёт общих затрат
z1:=z1+mas[i-1,j-1].c*mas[i-1,j-1].x;
end;
edit3.Text:=floattostr(z1);
end;
procedure TForm1.N5Click(Sender: TObject);
// метод минимальной стоимости
var
i,j,k,l,p:integer;
r:perevozka;
begin
min(mas,k,l); //вызов функции нахождения минимальной стоимости из не вычеркнутых ячеек
while not(mas[k,l].flag) do //если ячейка не вычеркнута
begin
if (b[k]>=a[l]) then begin
mas[k,l].x:=a[l];
b[k]:=b[k]-a[l];
stringgrid2.Cells[0,k+1]:=floattostr(b[k]);
for p:=0 to m-1 do
mas[p,l].flag:=true; //вычёркивание столбца
end else
if (b[k]<=a[l]) then begin
mas[k,l].x:=b[k];
a[l]:=a[l]-b[k];
stringgrid3.Cells[l+1,0]:=floattostr(a[l]);
for p:=0 to n-1 do //вычёркивание строки
30
mas[k,p].flag:=true;
end;
min(mas,k,l); //вызов функции нахождения минимального значения затрат
end;
z2:=0;
for i:=1 to m do
for j:=1 to n do begin
stringgrid1.cells[j,i]:= floattostr(mas[i-1,j-1].x); //вывод количества
//перевозимой продукции
if mas[i-1,j-1].x<> (-1) then
//подсчёт общих затрат
z2:=z2+mas[i-1,j-1].c*mas[i-1,j-1].x;
end;
edit3.Text:=floattostr(z2);
end; end.
2. Решение транспортной задачи можно проверить с помощью надстройки «Поиск решения» в пакете Excel (рис. 16, 17, 18). В ячейках A2-C4 располагаются начальные значения переменных Xij (количества перевозимой продукции), равные единицам. Для каждой строки и столбца в ячейках D2-D4 и в
ячейках A5-C5 найдём сумму, т. е. общее количество перевозимой продукции
для каждого исходного пункта и для каждого пункта назначения. В ячейки A8C8 располагаются значения затрат Cij. В ячейках E8-E10 – объём перевозимой
продукции. В ячейках A12-C12 – спрос в каждом пункте назначения. В ячейках
A14-C14 располагаются формулы подсчёта затрат на перевозку количества перевозимой продукции по каждому пункту назначения, т. е. сумма произведений
количества на стоимость перевозки. В ячейке D14 – сумма всех затрат по каждому пункту назначения. Ячейка D14 соответствует целевой функции (рис. 16).
В окне «Поиск решения» отображаются ссылки на целевую функцию,
ограничения: первое ограничение показывает, что количество перевозимой
продукции не может быть отрицательной величиной; второе ограничение для
сбалансированной задачи показывает равенство количества перевозимой продукции по каждому пункту назначения и спросом; третье ограничение для сбалансированной задачи показывает равенство объёма производства в каждом исходном пункте и количества перевозимой продукции из каждого пункта назначения. Изменяемые ячейки – это начальные значения количества перевозимой
продукции – ячейки A2-C4 (рис. 17). Направление оптимизации – минимум.
31
Рисунок 16 – Исходные данные на листе Excel
Рисунок 17 – Параметры поиска в надстройке «Поиск решения»
32
Рисунок 18 – Результат решения задачи
1.3.6. Лабораторная работа №2
Написать программу нахождения начального решения транспортной
задачи одним из трех методов: северо-западного угла, минимальной стоимости, метода Фогеля (табл. 9). Значения коэффициентов cij распределительной
таблицы для вариантов с 1 по 10 приведены в таблице 10. Значения коэффициентов cij распределительной таблицы для вариантов с 11 по 20 приведены
в таблице 11.
Таблица 9 – Исходные данные транспортной задачи
ai
bj
1
2
3
4
30
25
15
30
40
20
40
C11
C21
C31
C41
C12
C22
C32
C42
C13
C23
C33
C43
Таблица 10 – Значения коэффициентов для вариантов 1-10
№
С11
С12
С13
С21
С22
С23
1
2
3
4
5
6
7
8
9
10
3
5
4
4
2
1
6
2
4
2
1
5
2
6
4
4
3
5
5
4
3
2
3
3
5
3
4
2
6
5
5
3
1
3
4
5
2
5
4
1
4
5
3
1
3
5
4
2
2
4
3
2
5
2
3
1
4
6
3
2
33
№
С31
С32
С33
С41
С42
С43
1
2
3
4
5
6
7
8
9
10
1
3
2
5
3
5
5
6
3
1
3
2
3
1
5
5
2
5
3
1
2
1
2
5
4
4
3
5
3
2
4
2
3
2
4
5
2
5
5
4
3
1
4
3
5
1
5
5
4
1
4
5
3
5
6
5
3
2
3
5
Таблица 11 – Значения коэффициентов для вариантов 11-20
№
С11
С12
С13
С21
С22
С23
С31
С32
С33
С41
С42
С43
11
12
13
14
15
16
17
18
19
20
5
3
2
1
4
6
3
1
4
4
1
2
4
3
5
5
6
3
2
6
1
4
5
6
6
5
3
5
5
6
2
5
4
4
5
6
3
5
6
6
2
1
1
4
5
5
4
4
6
4
5
6
5
4
3
3
4
5
6
6
3
4
4
5
5
6
3
3
2
1
1
4
3
3
5
4
5
6
6
3
4
5
5
3
2
6
4
4
6
6
5
2
3
4
6
5
5
6
3
3
4
5
1
4
5
6
3
4
6
5
5
4
3
3
5
6
2
3
4
5
1.4. Задачи на графах
Графом называется пара G = (V, E). Элементы множества V называются вершинами графа, элементы множества Е – рёбрами или дугами. Если множество Е
состоит только из рёбер, то граф называется неориентированным, если только из
дуг, то ориентированным или орграфом. Если в Е есть и рёбра и дуги, то граф
называется смешанным. Контур или цикл – это замкнутый маршрут, где V1 = Vn.
Последовательность различных дуг или рёбер, где V1 < > Vn, представляют путь или
цепь соответственно. Граф называется взвешенным, если его рёбрам приписаны
числа, называемые весами. Длиной пути называется сумма весов, входящих в него
дуг или рёбер. С помощью графов можно решить следующие задачи: проектирование газопровода, имеющего минимальную стоимость; определение кратчайшего
пути между двумя городами в сети шоссейных дорог; определение максимальной
пропускной способности трубопровода и так далее. Оптимизационные задачи на
графах можно описать четырьмя типами моделей:
 минимизация сети;
 нахождение кратчайшего маршрута;
 определение максимального потока;
 минимизация стоимости потока в сети с ограниченными пропускными
способностями коммуникаций.
34
Рассмотренные модели связаны с определением расстояний и материальных потоков.
1.4.1. Минимизация сети
1.4.1.1. Алгоритм Прима
Данная задача состоит в нахождении рёбер, соединяющих все узлы графа
и имеющих минимальную длину. В итоге должно получиться минимальное дерево-остов, граф, в котором отсутствуют циклы. Алгоритм данного метода:
 начать с любого узла графа, соединить его с ближайшим узлом. Соединённые узлы образуют связное множество, остальные – несвязное;
 в несвязном множестве выбрать узел, который расположен ближе других к любому из узлов связного множества;
 скорректировать связное и несвязное множества;
 повторять до тех пор, пока в связное множество не попадут все узлы
сети.
Рассмотрим задачу (3) (рис. 19): телевизионная фирма планирует создание кабельной сети для обслуживания пяти районов-новостроек. Числа на рёбрах указывают длину кабеля. Узел 1 представляет телевизионный центр, а
остальные – районы-новостройки. Нужно найти такие рёбра, которые потребуют кабель минимальной длины для связи (прямой или через другие пункты)
всех районов с телевизионным центром.
Рисунок 19 – Исходные данные задачи в виде графа
0. C = {1} – связное множество и Ĉ = {2, 3, 4, 5, 6} – несвязное множество
1. C = {1, 2} – связное множество, т. к. ближайший узел 2
2. C = {1, 2, 5}
35
3. C = {1, 2, 4, 5}
4. C = {1, 2, 4, 5, 6}
5. C = {1, 2, 3, 4, 5, 6}
Минимальная длина кабеля: Z = 1 + 3 + 4 + 3 + 5 = 16.
1.4.1.2. Программная реализация алгоритма Прима
Пример пользовательского интерфейса и результат работы программы,
реализующей алгоритм Прима для задачи (3), приведён на рисунке 20.
Рисунок 20 – Результат работы программы
unit Unit2;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls;
type
TForm2 = class(TForm)
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Button1: TButton;
36
StringGrid1: TStringGrid;
Button2: TButton;
StringGrid2: TStringGrid;
Edit3: TEdit;
Button3: TButton;
Label3: TLabel;
Label4: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Type
N=set of 1..100;//тип множество
Puzel=^Uzel;//тип указатель на запись
Uzel=record//тип запись
nomer:integer; //номер узла
d:array of real; //расстояния между узлами
end;
var
Form2: TForm2;
var a,b,n1,n2:integer;
m_sv:N;//связное множество
m_nesv:N; //несвязное множество
mas_d:array of real; //массив расстояний между узлами
min:real;
flag:boolean;
list,minlist:Tlist; //список
rab,r1,r2:PUzel; //рабочая переменная
implementation
uses Unit1;
{$R *.dfm}
function Form_svmn(list:Tlist;m:N):integer; //нахождение ближайшего узла связного множества к узлам несвязного
var i,j,t,g:integer; min:real;
37
Rab:PUzel;
begin
min:=1000;
for i:=1 to a do //нахождение миним.расстояния
begin
if i in m then //проверка вхождения в множество
begin
rab:=list[i-1];
for j:=low(rab^.d) to high(rab^.d) do //цикл по значениям расстояний до узлов
if (Rab^.d[j]<min) and (Rab^.d[j]<>0) then
begin
min:=Rab^.d[j];
t:=j+1; //номер узла (столбца)
g:=i; //номер строки (пред.узла)
end; end; end;
form2.StringGrid2.Cells[t,g]:=floattostr(min);
form2.StringGrid2.Cells[g,t]:=floattostr(min);
rab:=list[g-1];
Rab^.d[t-1]:=0;
rab:=list[t-1];
rab^.d[g-1]:=0;
result:=t;
end;
procedure TForm2.Button1Click(Sender: TObject);
var
i,j:integer;
begin
a:=strtoint(edit1.text);
b:=strtoint(edit2.Text);
stringgrid1.ColCount:=b+1;
stringgrid1.RowCount:=a+1;
stringgrid2.ColCount:=b+1;
stringgrid2.RowCount:=a+1;
for i:=1 to a do
stringgrid1.Cells[0,i]:=inttostr(i);
for i:=1 to b do
stringgrid1.Cells[i,0]:=inttostr(i);
for i:=1 to a do
stringgrid2.Cells[0,i]:=inttostr(i);
38
for i:=1 to b do
stringgrid2.Cells[i,0]:=inttostr(i);
for i:=1 to a do
for j:=1 to b do
stringgrid1.Cells[j,i]:=floattostr(0);
for i:=1 to a do
for j:=1 to b do
stringgrid2.Cells[j,i]:=floattostr(0);
m_sv:=[1]; //формирование связного множества на 1 этапе
for i:=2 to a do
include(m_nesv,i);//формирование несвязного множества
end;
procedure TForm2.Button2Click(Sender: TObject);
var
i,j,k,l:integer;
s:real;
begin
for i:=1 to a do
begin
new(Rab);
Rab^.nomer:=i;
setlength(Rab^.d,a);
for k:=low(Rab^.d) to high(Rab^.d) do
Rab^.d[k]:=0;
for j:=1 to b do
if strtofloat(stringgrid1.cells[j,i])<>0 then
Rab^.d[j-1]:=strtofloat(stringgrid1.cells[j,i]);
list.add(Rab);
end;
l:=Form_svmn(list,m_sv);
include(m_sv,l);
exclude(m_nesv,l);
while m_nesv<>[] do
begin
l:=Form_svmn(list,m_sv);
include(m_sv,l);
exclude(m_nesv,l);
end;
{for i:=0 to list.Count-1 do
39
begin
r1:=list[i];
r2:=minlist[i];
for k:=0 to high(r2^.d) do
edit3.Text:=edit1.Text+floattostr(r2^.d[k]);
for k:=0 to high(r2^.d) do
r1^.d[k]:=r1^.d[k]-r2^.d[k];
for j:=1 to b do
stringgrid2.Cells[j,i]:=floattostr(r1^.d[j-1]);
end; }
s:=0;
for i:=1 to a do
for j:=1 to b do
if (i<j) then
s:=s+strtofloat(stringgrid2.Cells[j,i]);
edit3.Text:=floattostr(s);
form1.show;
end;
procedure TForm2.Button3Click(Sender: TObject);
var
i,j:integer;
begin
for i:=1 to a do
for j:=1 to b do
stringgrid1.cells[i,j]:=stringgrid1.cells[j,i];
end;
procedure TForm2.FormCreate(Sender: TObject);
var
i:integer;
begin
n1:=0;n2:=0;
list:=Tlist.Create; //создание списка
//minlist:=Tlist.Create;//
//setlength(mas_d,a);
end;
end.
40
1.4.1.3. Алгоритм Краскала
Идея алгоритма: искомые рёбра соединяют вершины. Поэтому возможны
две стратегии построения. Можно идти от вершин и для каждой из них искать
минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого
ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, рёбра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с
первого проверяем, соединяет или нет оно две несвязные вершины, если да, то
его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то
работа алгоритма начинается с V несвязных компонент графа (пока из графа
все ребра исключаем). Для того чтобы их связать, необходимо найти V-1 ребро.
Другими словами, алгоритм организует процесс роста компонент связности в
процессе которого они объединяются друг с другом до тех пор, пока не останется одна, являющаяся конечным результатом.
В алгоритме используется термин «компонента связности». Такой конструкции нет ни в одном языке программирования. Это исключительно математический термин, поэтому для конкретной реализации алгоритма необходимо
тщательно продумать вопрос о представлении «компоненты связности» существующими языковыми конструкциями, например, использовать множества.
Алгоритм:
 Создаём список ребер по возрастанию.
 Создаём множество компонент связности, каждая из которых содержит ровно одну вершину.
 Пока компонент связности больше чем одна.
• Взять ребро из начала списка рёбер.
• Если ребро соединяет две разных компоненты связности, то компоненты связности объединить в одну.
Рассмотрим предыдущую задачу (3) (рис. 19).
1.Расположим рёбра в порядке возрастания их весов: (1,2), (2,5), (4,6), (1,3),
(2,4), (3,4), (2,3), (1,4), (4,5), (1,5), (3,6).
2.Создадим множества компонент связности, каждая из которых содержит
одну вершину: [1], [2], [3], [4], [5], [6].
3.Пока компонент связности больше, чем одна:
3.1. Возьмём ребро (1,2). Ребро соединяет две разные компоненты связности, поэтому объединяем их в одну [1,2].
3.2. Возьмём ребро (2,5). Ребро соединяет две разные компоненты связности, поэтому объединяем их в одну [1,2,5].
41
3.3. Возьмём ребро (4,6). Ребро соединяет две разные компоненты связности, поэтому объединяем их в одну [4,6].
3.4. Возьмём ребро (1,3). Ребро соединяет две разные компоненты связности, поэтому объединяем их в одну [1,2,3,5].
3.5. Возьмём ребро (2,4). Ребро соединяет две разные компоненты связности, поэтому объединяем их в одну [1,2,3,4,5,6].
3.6. Все вершины вошли в одну компоненту связности – алгоритм заканчивается. Выбранные рёбра входят в остовное дерево. Полученное решение
такое же, как с помощью предыдущего алгоритма, сумма рёбер z = 16.
1.4.1.4. Программная реализация алгоритма Краскала
Пример пользовательского интерфейса и результат работы программы,
реализующей алгоритм Краскала для задачи (3), приведён на рисунке 21.
Рисунок 21 – Результат работы программы
42
…
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;
type
TForm1 = class(TForm)
Label1: TLabel;
Edit1: TEdit;
StringGrid1: TStringGrid;
StringGrid2: TStringGrid;
Button1: TButton;
Button2: TButton;
Memo1: TMemo;
Memo2: TMemo;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Edit2: TEdit;
Button3: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Type
PDuga=^Duga;
Duga=Record
v1,v2:integer; //1 и 2 вторая вершины
d:real;// вес дуги
end;
N=set of 1..100;//тип множество из 100 узлов
var
Form1: TForm1;
43
a,k,l,m1,m2,t:integer;
r1,r2:PDuga;
list,list_ostov:Tlist;
mas:array[1..6,1..6] of real=((0,1,4,7,9,0),(1,0,6,5,3,0),(4,6,0,5,0,10),
(7,5,5,0,8,3),(9,3,0,8,0,0),(0,0,10,3,0,0));
masmn:array of N;
n1,n2:N;
implementation
uses Unit2;
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
//формирование таблиц
var
i,j:integer;
begin
a:=strtoint(edit1.Text);
stringgrid1.RowCount:=a+1;
stringgrid1.colCount:=a+1;
stringgrid2.RowCount:=a+1;
stringgrid2.colCount:=a+1;
for i:=1 to a do
stringgrid1.Cells[i,0]:=inttostr(i);
for i:=1 to a do
stringgrid1.Cells[0,i]:=inttostr(i);
for i:=1 to a do
stringgrid2.Cells[i,0]:=inttostr(i);
for i:=1 to a do
stringgrid2.Cells[0,i]:=inttostr(i);
for i:=1 to a do
for j:=1 to a do
stringgrid1.cells[j,i]:=floattostr(mas[i,j]);
end;
procedure TForm1.Button2Click(Sender: TObject);
//нахождение остовного дерева
var
i,j:integer; s:real;
begin
memo1.Clear;
memo2.Clear;
44
for i:=1 to a do
for j:=1 to a do
if (i<j) and (strtofloat(stringgrid1.Cells[j,i])<>0) then
begin
new(r1);
r1^.v1:=i;
r1^.v2:=j;
r1^.d:=strtofloat(stringgrid1.Cells[j,i]);
list.Add(r1);
memo1.Lines.add(inttostr(r1^.v1)+' ' +inttostr(r1^.v2)+' '+floattostr(r1^.d));
end;
//сортировка по возрастанию методом пузырька
for i := 1 to list.Count-1 do
for j:=0 to list.Count-i-1 do
begin
r1:=list[j]; r2:=list[j+1];
if r1.d>r2.d then
list.exchange(j,j+1);
end;
//формирорвание массива множеств
setlength(masmn,a); // по количеству вершин
for i:=1 to a do
begin
masmn[i-1]:=[];
include(masmn[i-1],i); //в каждом множестве одна вершина
end;
//рассматриваем список
for i:=0 to List.Count - 1 do
begin
r1:=list[i];
for j:=0 to high(masmn) do
begin
if r1^.v1 in masmn[j] then k:=j+1; //номер множества, в котором эта вершина
if r1^.v2 in masmn[j] then l:=j+1; //находится
end;
if k<>l then //если вершины в разных множествах
begin
masmn[k-1]:=masmn[k-1]+masmn[l-1]; //объединяем в одно
new(r2);
45
r2^.v1:=r1^.v1;
r2^.v2:=r1^.v2;
r2^.d:=r1^.d; list_ostov.Add(r2); //добавляем в новый список //остовного дерева
masmn[l-1]:=[];
end;
end; s:=0;
for i:=1 to a do
for j:=1 to a do
stringgrid2.Cells[j,i]:=floattostr(0);
for k := 0 to List_ostov.Count - 1 do begin // вывод для контроля
r1:=list_ostov[k];
//элементов остова
s:=s+r1^.d; //сумма длин ребер
memo2.Lines.add(inttostr(r1^.v1)+' ' +inttostr(r1^.v2)+' '+floattostr(r1^.d));
for i:=1 to a do
for j:=1 to a do
if (i=r1^.v1) and (j=r1^.v2) then
stringgrid2.Cells[j,i]:=floattostr(r1^.d); //заполнение таблицы
end;
edit2.Text:=floattostr(s);
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
Form2.Show;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
list:=Tlist.Create;
list_ostov:=TList.Create;
end;
end.
1.4.2. Алгоритм нахождения кратчайшего пути
1.4.2.1. Алгоритм Дейкстры
В этом разделе представлены два алгоритма для решения задачи поиска
кратчайшего пути как в сетях, имеющих циклы, так и в сетях, не имеющих циклов. Алгоритм Дейкстры разработан для поиска кратчайшего пути между заданным исходным узлом и любым другим узлом сети. Алгоритм Флойда более
общий, поскольку он позволяет одновременно найти минимальные пути между
любыми двумя узлами сети.
46
Алгоритм Дейкстры. В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки рёбер. Обозначим через u, кратчайшее расстояние от исходного узла 1 до узла i, через dij – длину ребра (i, j). Тогда для узла j определим метку [uj, i] следующим образом:
[uj,i] = [ui + dij,i], dij>0.
Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и
постоянные. Временная метка впоследствии может быть заменена на другую
временную, если будет найден более короткий путь к данному узлу. Когда же
станет очевидным, что не существует более короткого пути от исходного узла к
данному, статус временной метки изменяется на постоянный. Вычислительная
схема алгоритма состоит из следующих этапов:
Этап 0. Исходному узлу (узел 1) присваивается постоянная метка [0, –].
Полагаем i = 1.
Этап 1. а) Вычисляются временные метки [ui + dij, i] для всех узлов j, которые
можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [uj, k], полученную от другого узла k, и если
ui + dij < ui, тогда метка [uj, k] заменяется на [ui + dij, i].
б) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [ur, s] с наименьшим значением
расстояния ur среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем этап i.
Рассмотрим пример (4). На рисунке 22 показана транспортная сеть, состоящая из пяти городов (расстояния между городами (в милях) приведены
возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния
от города 1 (узел 1) до всех остальных четырёх городов.
2
15
4
100
1
20
30
10
3
50
60
5
Рисунок 22 – Транспортная сеть в виде графа
47
Этап 0. Назначаем узлу 1 постоянную метку [0, —].
Этап 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих
узлов, в результате получаем следующую таблицу меток.
Таблица 12 – Таблица меток 1 этапа
Узел
1
2
3
Метка
[0,-]
[0 + 100, 1] = [100,1]
[0 + 30, 1] = [30, 1]
Статус метки
Постоянная
Временная
Временная
Среди узлов 2 и 3 узел 3 имеет наименьшее значение расстояния
(U3 = 30). Поэтому статус метки этого узла изменяется на «постоянная».
Этап 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в
узлы 4 и 5. Получаем следующий список узлов.
Таблица 13 – Таблица меток 2 этапа
Узел
1
2
3
4
5
Метка
[0,-]
[100, 1]
[30, 1]
[30 + 10, 3] = [40, 3]
[30 + 60, 3] = [90, 3]
Статус метки
Постоянная
Временная
Постоянная
Временная
Временная
Временный статус метки [40, 3] узла 4 заменяется постоянным (U4 = 40).
Этап 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток
получим следующий их список.
Таблица 14 – Таблица меток 3 этапа
Узел
Метка
1
2
3
4
5
[О,-]
[40 + 15, 4] = [55, 4]
[30,1]
[40, 3]
[90, 3] или [40 + 50, 4] = [90, 4]
Статус метки
Постоянная
Временная
Постоянная
Постоянная
Временная
Временная метка [100, 1], полученная узлом 2 на втором этапе, изменена
на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу
(проходящий через узел 4). На третьем этапе узел 5 получает две метки с одинаковым значением расстояния U5 = 90.
48
Этап 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном этапе получаем такой
же список меток, как и на предыдущем, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остаётся только узел 5, но,
так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается. Алгоритм позволяет проводить вычисления непосредственно на схеме сети. Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путём прохождения их в обратном направлении с
помощью информации, представленной в постоянных метках. Например, для
определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов 2) -> [55, 4] -> 4) -> [40, 3] 3) -> [30, 1] -> 1). Таким
образом, получаем путь 1 -> 3 -> 4 -> 2 общей длиной 55 миль.
1.4.2.2. Алгоритм Флойда
Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так
как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n-строками и nстолбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет
конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае. Покажем сначала основную идею метода Флойда. Пусть есть три
узла i, j и k и заданы расстояния между ними (рис. 23). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i- > k путём i -> j -> k.
Такая замена (далее её будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.
j
dij
i
djk
k
dik
Рисунок 23 – Треугольный оператор Флойда
Алгоритм Флойда требует выполнения следующих действий:
Этап 0. Определяем начальную матрицу расстояний Do и матрицу последовательности узлов So. Диагональные элементы обеих матриц помечаются
49
знаком «–», показывающим, что эти элементы в вычислениях не участвуют.
Полагаем k = 1.
Основной этап k. Задаём строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk = 1. Если выполняется неравенство
dik + dkj < dij, (i ≠ k, j ≠ k и i ≠ j), то делаем следующее:
 создаём матрицу Dk путём замены в матрице Dk-1 элемента dij суммой
dik + dkj;
 создаём матрицу Sk, меняя в матрице Sk-1 элемент Sij на k. Полагаем
k = k +1 и повторяем этап k.
Поясним действия, выполняемые на k-м этапе алгоритма, представив
матрицу Dk-l так, как она показана на рисунке 26. На этом рисунке строка k и
столбец k являются ведущими. Строка i – любая строка с номером от 1 до k – 1,
а строка р – произвольная строка с номером от k + 1 до n. Аналогично столбец j
представляет любой столбец с номером от 1 до k – 1, а столбец q – произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов, ведущих строки и столбца (показанных в квадратиках) меньше элементов, находящихся на пересечении столбца и
строки (показаны в кружках), соответствующих рассматриваемым ведущим
элементам, то расстояние (элемент в кружке) заменяется суммой расстояний,
представленных ведущими элементами. После реализации n-этапов алгоритма
определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам:
1. Расстояние между узлами i и j равно элементу dij в матрице Dn.
2. Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn.
Пусть Sij = k, тогда имеем путь i -> k -> j. Если далее Sik = k и Skj = j, тогда считаем, что весь путь определён, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к
узлу k и от узла k к узлу j.
Положим, что в качестве матрицы смежности, каждый элемент которой
хранит вес некоторого ребра, была задана следующая матрица:
Dij
1
2
3
1
0
1
2
2
9
0
4
3
2
4
0
Рисунок 24 – Матрица смежности Dij
50
Количество вершин в графе, представлением которого является данная
матрица, равно 3, и, причём, между каждыми двумя вершинами существует
ребро. Вот собственно сам этот граф:
Рисунок 25 – Исходные данные в виде графа
Задача алгоритма: перезаписать данную матрицу так, чтобы каждая ячейка вместо веса ребра из i в j, содержала кратчайший путь из i в j. Для примера
взят совсем маленький граф, и поэтому не будет ничего удивительного, если
матрица сохранит свое изначальное состояние. Но результат тестирования программы показывает замену двух значений в ней. Следующая схема поможет с
анализом этого конкретного примера.
Рисунок 26 – Итерационный процесс выполнения алгоритма Флойда
51
На рисунке 26 показаны 27 шагов выполнения основной части алгоритма.
Их столько по той причине, что время выполнения метода равно O(|V|3). Наш
граф имеет 3 вершины, а 33 = 27. Одна из двух замен происходит на итерации,
при которой k = 1, i = 2, а j=3. В тот момент D[2][1] = 1, D[1][3] = 2, D[1][2] = 4.
Условие истинно, т. е. D[2][1] + D[1][3] = 3, а 3 < 4, следовательно, элемент
матрицы D[1][2] получает новое значение. Следующий шаг, когда условие также истинно, привносит изменения в элемент, расположенный на пересечении
первой строки и второго столбца.
1.4.3. Лабораторная работа №3
Разработать программу нахождения остовного дерева с помощью алгоритмов Прима и Краскала на примере задачи (3) и кратчайшего расстояния от
любого узла до всех остальных с помощью алгоритмов Дейкстры и Флойда на
примере задачи (4).
1.5. Курсовая работа
Номер варианта курсовой работы выбирается по порядковому номеру в
общем списке в журнале преподавателя.
1 вариант
На строительном полигоне имеется пять кирпичных заводов, объём производства которых в сутки равен 600, 600, 500, 650, 700 т. Заводы удовлетворяют потребности семи строительных объектов соответственно в количестве 350,
450, 300, 450, 300, 200, 450 т. Оставшийся кирпич отправляют по железной дороге в другие районы. Кирпич на строительные объекты доставляется автомобильным транспортом. Расстояние в километрах от заводов до объектов указано в следующей таблице:
Таблица 15
Заводы
А1
А2
А3
А4
А5
В1
14
13
18
14
11
В2
5
4
8
7
15
Объекты
В4
8
9
18
19
25
В3
10
11
14
13
14
52
В5
16
20
23
15
19
В6
10
12
13
16
15
В7
25
23
21
23
20
Определите, с каких заводов и на какие объекты должен доставляться
кирпич, а также какие заводы и в каком количестве должны отправлять кирпич
в другие районы, чтобы транспортные издержки по доставке кирпича автотранспортом были минимальными. Стоимость перевозки 1 т кирпича автотранспортом удовлетворяет условию c = a + d(l – 1), где a = 25 д. е., d = 5 д. е.,
l – пробег, км.
2 вариант
Имеются две станции технического обслуживания (СТО), выполняющие
ремонтные работы для трёх автопредприятий. Производственные мощности
СТО, стоимость ремонта в различных СТО, затраты на авто транспортировку от
автопредприятий на СТО и обратно приведены в таблице:
Таблица 16
СТО
1
2
Объём средств,
(тыс. руб.)
Стоимость ремонта Затраты на транспортировку, руб. Производственная
ед., руб.
мощность, шт.
АТП-1
АТП-2
АТП-3
520
70
20
60
10
710
40
50
30
6
7
5
8
18
Требуется определить, какое количество автомашин из каждого автопредприятия необходимо отремонтировать на каждой СТО, чтобы суммарные
расходы на ремонт и транспортировку были минимальными.
3 вариант
Найдите оптимальный план распределения заявок на ремонт для условий,
приведённых в следующей таблице:
Таблица 17
СТО
1
2
3
Объём средств,
(тыс. руб.)
Затраты на транспортировку,
Затраты на ТО
1 автомобиля, руб.
и ремонт одного
автомобиля, руб. АТП-1 АТП-2 АТП-3 АТП-4
720
20
40
30
10
650
30
20
25
45
690
35
50
20
30
30
10
40
20
53
Производственная
мощность, шт.
80
20
40
4 вариант
Промышленный концерн имеет два завода и пять складов в различных
регионах страны. Каждый месяц первый завод производит 40, а второй – 70 ед.
продукции. Вся продукция, производимая заводами, должна быть направлена
на склады. Вместимость первого склада равна 20 ед. продукции; второго – 30;
третьего – 15; четвертого – 27; пятого – 28 ед. Издержки транспортировки продукции от завода до склада следующие (руб.)
Таблица 18
Заводы
1
2
1
520
450
Склады
3
650
630
2
480
525
4
500
560
5
720
750
Распределите план перевозок из условия минимизации ежемесячных расходов на транспортировку.
5 вариант
Три нефтеперерабатывающих завода с суточной производительностью
10, 8, 6 млн галлонов бензина снабжают три бензохранилища, спрос которых
составляет 6, 11 и 7 млн галлонов. Бензин транспортируется в бензохранилища
по трубопроводу. Стоимость перекачки бензина на 1 км составляет 5 д. е. на
100 галлонов. Завод 1 не связан с хранилищем 3. Расстояние от заводов до бензохранилищ следующее (км):
Таблица 19
Номер завода
1
2
3
Бензохранилища
2
150
180
280
1
100
420
200
3
60
120
Минимизируйте затраты.
6 вариант
Автомобили перевозятся на трайлерах из трёх центров распределения пяти продавцам. Стоимость перевозки в расчете на 1 км пути, пройденного трайлером, равна 60 д. е. Один трайлер может перевозить до 15 автомобилей. Стоимость перевозок не зависит от того, насколько полно загружается трайлер. В
приведённой ниже таблице указаны расстояния (км) между центрами распределения и продавцами, а также величины, характеризующие ежемесячный спрос
и объёмы поставок, исчисляемые количеством автомобилей:
54
Таблица 20
Центр
распределения
1
2
3
Спрос
на автомобили
1
80
60
30
Продавцы
2
3
120
180
70
50
80
120
4
150
65
140
5
50
90
90
Объём поставок,
шт.
300
350
120
110
250
150
120
770
140
Определите минимальные затраты на доставку автомобилей.
7 вариант
Решите задачу распределения станков четырёх различных типов по шести
типам работ. Пусть имеется 30, 45, 25, и 20 станков соответствующих типов.
Шесть типов работ характеризуются 30, 20, 10, 40, 10 и 10 операциями соответственно. На станке 3 не может выполняться работа 6. Исходя из коэффициентов
стоимости операции, представленных в следующей таблице, выполните оптимальное распределение станков по работам.
Таблица 21
Тип станков
1
2
3
4
Тип работ
1
10
4
12
11
2
1
8
3
12
3
3
12
14
9
4
7
2
6
5
5
14
10
2
1
6
8
7
3
8 вариант
Пусть штрафы за недопоставку единицы продукции в пункты назначения
1, 2, 3 равны соответственно 5, 3, и 2. Исходные данные следующие:
Таблица 22
1
2
3
1
3
5
1
Потребители
2
2
4
6
3
4
5
7
Потребность, шт.
60
40
70
Заводы
Найти оптимальный план перевозки продукции.
55
Объём
производства, шт.
50
75
30
9 вариант
Пусть коэффициенты стоимости хранения груза в исходных пунктах 1, 2,
3 соответственно равны 5, 6, 2. Найдите оптимальное решение, если весь объём
груза исходного пункта 2 должен быть вывезен для того, чтобы освободить место для новой продукции. Стоимости перевозок (д. е.):
Таблица 23
Пункты
хранения
1
2
3
Спрос, т
Потребители
2
0
1
2
320
1
1
3
1
280
3
4
2
1
200
Запасы
продукции, т
300
400
250
10 вариант
Рассмотрите задачу о загрузке самолета предметами пяти различных типов. Вес wi, объём vi и стоимость ri одного предмета каждого типа приведены в
таблице.
Таблица 24
i
1
2
3
4
5
wi
5
8
3
2
7
vi
1
8
6
5
4
ri
4
7
6
5
4
Максимальная грузоподъёмность и объём самолета W = 112 т;
V = 109 м3.Определить набор предметов, обеспечивающих максимальную стоимость груза (д. е.).
11 вариант
Изделия четырёх типов проходят последовательную обработку на двух
станках. Время обработки одного изделия каждого типа на каждом из станков
приведено в таблице.
Таблица 25
Станок
1
2
тип 1
2
3
Время обработки одного изделия, ч.
тип 2
тип 3
3
4
2
1
тип 4
2
2
Затраты на производство одного изделия каждого типа определяются как
величины, прямо пропорциональные времени использования станков (в машино-часах). Стоимость машино-часа составляет 10 $ для станка 1 и 15 $ – для
станка 2. Допустимое время использования станков для обработки изделий всех
56
типов ограничено следующими значениями: 500 машино-часов – для станка 1 и
380 машино-часов для станка 2. Цены изделий 1, 2, 3 и 4 типов равны 65, 70, 55,
45 $ соответственно. Требуется максимизировать суммарную чистую прибыль.
12 вариант
Цех выпускает три вида деталей – А, В, С. Каждая деталь обрабатывается
тремя станками. Организация производства в цехе характеризуется следующей
таблицей.
Таблица 26
Станок
1
2
3
Отпускная цена
за одну деталь
Длительность
обработки деталей, мин.
А
В
С
12
10
9
15
18
20
6
4
4
30
32
30
Фонд времени, ч
220
400
100
Составьте план загрузки станков, обеспечивающий цеху получение максимальной прибыли.
13 вариант
Решите задачу распределения станков четырёх различных типов по пяти
типам работ. Пусть имеется 25, 30, 20, 30 станков соответствующих типов.
Пять типов работ характеризуются 20, 20,30,10 и 25 операциями соответственно. На станке 4 не может выполняться работа 4. Исходя из коэффициентов стоимости операции, представленных в таблице, постройте модель для оптимального распределения станков по работам.
Таблица 27
Тип станков
1
2
3
4
1
10
5
15
20
Тип работ
3
3
15
14
13
2
2
10
5
15
4
15
2
7
-
5
9
4
15
8
14 вариант
Имеются четыре оперативных базы и три цели. В силу различия в типах
самолётов и высоте полета вес бомб (т), доставляемых с любой базы к любой
цели, определяется по следующей таблице:
57
Таблица 29
База
Цель
2
6
6
8
6
1
8
6
10
8
1
2
3
4
3
5
6
4
4
Дневная интенсивность каждой базы составляет 150 самолёто-вылетов в
день. На каждую цель необходимо организовать 200 самолёто-вылетов в день.
Определите план вылетов с каждой базы к каждой цели, дающий максимальный вес бомб, доставляемый к целям.
15 вариант
На швейной фабрике для изготовления четырёх видов изделий может быть
использована ткань трёх артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в таблице. В ней так же указаны имеющиеся в распоряжении фабрики общее количество тканей каждого артикула и цена изделия
данного вида. Определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной.
Таблица 30
Артикул ткани
I
II
III
Цена одного изделия (руб.)
Норма расхода ткани (м) на одно изделие вида
1
2
3
4
1
2
1
1
3
2
4
2
4
9
6
4
Общее количество
ткани (м)
180
210
800
7
16 вариант
Предприятие выпускает четыре вида продукции и использует три типа
основного оборудования: токарное, фрезерное и шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования
приведены в таблице. В ней же указаны общий фонд рабочего времени каждого
из типов оборудования, а также прибыль от реализации одного изделия данного
вида. Определить такой объём выпуска каждого из изделий, при котором общая
прибыль от их реализации является максимальной.
58
Таблица 31
Тип оборудования
Токарное
Фрезерное
Шлифовальное
Прибыль от реализации
единицы продукции (руб.)
Затраты времени (станко-час)
на единицу продукции вида
1
2
3
4
2
1
1
3
1
2
1
1
2
1
8
3
2
Общий фонд рабочего
времени (станко-час)
300
70
340
1
17 вариант
Для перевозок груза на трёх линиях могут быть использованы суда трёх
типов. Производительность судов при использовании их на различных линиях
характеризуются данными, приведёнными в таблице. В ней же указаны общее
время, в течение которого суда каждого типа находятся в эксплуатации, и минимально необходимые объёмы перевозок на каждой линии. Определить, какие
суда, на какой линии и в течение какого времени следует использовать, чтобы
обеспечить максимальную загрузку судов с учётом возможного времени их
эксплуатации.
Таблица 32
Тип судна
I
II
III
Заданный объём
перевозок (млн тонн)
Производительность судов
(млн тонн в сутки) на линии
1
2
3
8
14
11
6
15
13
12
12
4
3000
5400
Общее время
эксплуатации судов
(лет)
20
30
30
3300
18 вариант
Найти решение, состоящее в определении плана изготовления изделий A,
B и C, обеспечивающего максимальный их выпуск, в стоимости, выраженной с
учётом ограничений на возможное использование сырья трёх видов. Нормы
расхода сырья каждого вида на одно изделие, цена одного изделия соответствующего вида, а также имеющегося сырья, приведены в таблице.
Таблица 33
Вид сырья
I
II
III
Цена одного изделия (руб.)
Нормы затрат (кг) на одно изделие
A
B
C
18
15
12
6
4
8
5
3
3
9
10
16
59
Общее количество
сырья (кг)
360
192
180
-
19 вариант
На заводе выпускают изделия четырёх типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д. е. На изготовление изделий расходуются ресурсы трёх типов: энергия, материалы, труд. Данные о технологическом процессе приведены в следующей таблице:
Таблица 34
Ресурсы
Энергия
Материалы
Труд
1
2
4
1
Затраты ресурсов на ед. изделия
2
3
3
1
2
1
2
3
4
2
2
1
Запасы ресурсов, ед.
30
40
25
Спланируйте производство изделий так, чтобы прибыль от их реализации
была наибольшей.
20 вариант
Для обогрева помещений используются четыре агрегата, каждый из которых может работать на любом из пяти сортов топлива, имеющемся в количествах 90, 110, 70, 80 и 150 т. Потребность в топливе каждого из агрегатов соответственно равна 80, 120, 140 и 160 т. Теплотворная способность i-ого сорта
топлива при использовании его на j-ом агрегате задаётся матрицей:
 8 7 9 11 8 
6 5 8 7 6 

(Cij )  
 7 11 5 8 7 


 9 8 7 9 11
Найти такое распределение топлива между агрегатами, при котором получается максимальное количество теплоты от использования всего топлива.
21 вариант
Изготовляемый на пяти кирпичных заводах кирпич поступает на шесть
строящихся объектов. Ежедневное производство кирпича и потребность в нём
указаны в таблице. В ней же указана цена перевозок 1 000 шт. кирпича с каждого из заводов к каждому из объектов. Составить план перевозок, согласно которому обеспечиваются потребности в кирпиче на каждом из строящихся объектов при минимальной общей стоимости перевозок.
60
Таблица 35
Кирпичный завод
I
II
III
IV
V
Потребность в кирпиче
(тыс. шт.)
Цена перевозки 1 тыс. шт. кирпича
к строящемуся объекту
1
2
3
4
5
6
8
7
5
10
12
8
13
8
10
7
6
13
12
4
11
9
10
11
14
6
12
13
7
14
9
12
14
15
8
13
230
220
130
170
190
Производство
кирпича (тыс. шт.)
240
360
180
120
150
110
-
22 вариант
Цех выпускает три вида деталей – А, В, С. Каждая деталь обрабатывается
тремя станками. Организация производства в цехе характеризуется следующей
таблицей.
Таблица 36
Станок
1
2
3
Отпускная цена
за одну деталь
Длительность обработки деталей, мин.
А
В
С
12
10
9
15
18
20
6
4
4
30
32
30
Фонд времени, ч
220
400
100
Составьте план загрузки станков, обеспечивающий цеху получение максимальной прибыли.
23 вариант
Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12, 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т. Тарифы (в д. е. за 1 т) указаны в
следующей таблице:
Таблица 37
Овощехранилища
1
2
3
4
Магазины
1
2
3
5
3
2
7
2
6
4
3
4
1
2
7
Составьте план перевозок, минимизирующий суммарные транспортные
расходы.
61
24 вариант
При откорме каждое животное должно получить не менее 9 ед. белков,
8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:
Таблица 38
Количество единиц питательных веществ на 1 кг
Корма 1
Корма 2
3
1
1
2
1
6
Питательные вещества
Белки
Углеводы
Протеин
Стоимость 1 кг корма первого вида – 4 д. е., второго – 6 д. е.
Составьте дневной рацион питательности, имеющий минимальную
стоимость.
25 вариант
Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд –
120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции П1, П2, П3,
П4. Организация производства характеризуется следующей таблицей:
Таблица 39
Продукция
П1
П2
П3
П4
Затраты на 1 ед. продукции
площадь
труд
тяга
2
2
2
3
1
3
4
2
1
5
4
1
Доход от единицы
продукции
1
4
3
5
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль.
26 вариант
Совхоз отвёл три земельных массива размером 5 000, 8 000, 9 000 га на
посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по
массивам указана в следующей таблице:
Таблица 40
Посевы
Рожь
Пшеница
Кукуруза
Массивы
2
14
14
35
1
12
14
30
62
3
15
22
25
За 1 ц ржи совхоз получает 2 д. е., за 1 ц пшеницы – 2,8 д. е., за 1 ц кукурузы – 1,4 д. е. Сколько гектаров и на каких массивах совхоз должен отвести на
каждую культуру, чтобы получить максимальную выручку, если по плану он
обязан сдать не менее 1 900 т ржи, 158 000 т пшеницы и 30 000 т кукурузы?
27 вариант
Три типа самолётов следует распределить между четырьмя авиалиниями.
Данные об организации процесса перевозок приведены в следующей таблице:
Таблица 41
Тип самолета
1
2
3
Объём перевозок одним
Эксплуатационные
Число самолётов, самолетом по авиалиниям расходы на один самолёт
в месяц, ед.
по авиалиниям, ден. ед.
ед.
1
2
3
4
1
2
3
4
50
15
10
20
50
15
20
25
40
20
20
25
10
10
70
28
15
45
30
35
50
30
45
40
70
50
65
28 вариант
Из трёх продуктов – 1, 2, 3 составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед.
вещества С. Структура химических веществ приведена в следующей таблице:
Таблица 42
Продукт
1
2
3
Содержание химического вещества в 1 ед. продукции
А
В
С
2
1
3
1
2
4
3
1.5
2
Стоимость 1 ед.
продукции
2
3
2,5
Составьте наиболее дешёвую смесь.
29 вариант
Заводы №1, 2, 3 производят однородную продукцию в количестве соответственно 500, 400 и 510 единиц. Себестоимость производства единицы продукции на
заводе №1 составляет 25 д. е., на заводе №2 – 20 д. е., на заводе №3 – 23 д. е. Продукция отправляется в пункты А, В, С, потребности которых равны 310, 390 и 450
единицам. Стоимости перевозок 1 ед. продукции заданы матрицей:
7 5 1
C   2 3 2 
 3 5 4


63
Составьте оптимальный план перевозок продукции при условии, что
коммуникации между заводом №2 и пунктом А не позволяют пропускать в рассматриваемый период более 250 единиц продукции.
30 вариант
Рассмотреть задачу распределения самолётов трёх типов по четырём
маршрутам. Характеристики парка самолетов и движения по авиалиниям приведены в табл. 43, 44.
Таблица 43
Тип
самолёта
Вместимость
(число пассажиров)
Количество
самолётов
1
2
3
50
30
20
Суточный пассажиропоток
5
8
10
Количество рейсов в сутки
на каждом маршруте
1
2
3
4
3
2
2
1
4
3
3
2
5
5
4
2
100
200
90
120
Стоимости характеристики авиаперевозок:
Таблица 44
Тип самолета
1
2
3
Убыток от неудовлетворённого спроса
(на одного неперевезённого пассажира)
Эксплуатационные расходы на 1 рейс
по данному маршруту, д. е.
1
2
3
4
1000
1100
1200
1500
800
900
1000
1000
600
800
800
900
40
50
45
70
Минимизировать сумму эксплуатационных расходов и потерь из-за неудовлетворенного спроса.
Библиографический список
1. Таха, Х. Введение в исследование операций. В 2 т. / Х. Таха. – М. :
Мир, 1985.
2. Красс, М. Основы математики и её приложения в экономическом образовании / М. С. Красс, Б. П. Чупрынов. – М. : Изд. Дело, 2001.
3. Вагнер, Г. Основы исследования операций / Г. Вагнер. – М. : Мир,
1973.
64
1/--страниц
Пожаловаться на содержимое документа