Реферат: Нахождение опорного плана транспортной задачи
⚡ 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
.
ЛИНЕЙНЫЕ МЕТОДЫ
ОПТИМИЗАЦИИ,
ЗАДАЧА ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ,
ЕЕ ПОСТАНОВКА
И СВОЙСТВА
1.1 Постановка
задачи линейного
программирования
В экономике
помимо соотношений
затрат, выпуска,
спроса, предложения
и т.п., часто
возникает
необходимость
выбора одного
из возможных
вариантов
функционирования
экономической
системы. Экономически
оправдано в
таких условиях
ставить вопрос
о выборе наилучшего
варианта. Что
понимать под
лучшим вариантом
задается в виде
критерия (цели).
В количественном
выражении
критерий представляет
собой функциональную
зависимость
от переменных
показателей,
в дальнейшем
будем ее называть
целевой (критериальной)
функцией. Наилучший
вариант в таком
случае соответствует
наибольшему
(экстремальному,
оптимальному)
значению функции.
В экономических
задачах, как
правило, область
изменения
переменных
параметров
ограничена
и оптимальное
значение целевой
функции требуется
найти на ограниченном
множестве.
Область исследования,
заключающаяся
в нахождении
алгоритмов
решения подобных
задач, образует
направление,
которое называется
математическим
программированием.
Экономические
требования
накладывают
свои особенности:
в практических
задачах число
переменных
и ограничений
достаточно
велико, целевая
функция не
всегда дифференцируема.
Поэтому методы
классического
анализа для
отыскания
экстремумов
к задачам
математического
программирования
часто неприменимы.
Возникает
необходимость
разработки
специальных
методов решения
задач математического
программирования
и, следовательно,
как всегда в
таких случаях,
появляются
новые направления,
требующие
упорядочения,
классификации.
Классификация
задач происходит
в зависимости
от экономических
условий, видов
ограничений,
переменных
и параметров,
методов решения.
Традиционно
в математическом
программировании
выделяют следующие
основные разделы.
Линейное
программирование
- целевая функция
линейна, множество,
на котором
ищется экстремум
целевой функции,
задается системой
линейных равенств
и неравенств.
В свою очередь
в линейном
программировании
существуют
классы задач,
структура
которых позволяет
создать специальные
методы их решения,
выгодно отличающиеся
от методов
решения задач
общего характера.
Так, в линейном
программировании
появился раздел
транспортных
задач, блочного
программирования
и др.
-
выпуклое
программирование
- когда выпукла
целевая функция,
если рассматривается
задача ее минимизации
(либо выпуска,
если ищется
максимум), и
выпукло множество,
на котором
решается
экстремальная
задача;
- квадратичное
программирование
- когда целевая
функция квадратичная,
а ограничения
- линейные равенства
и неравенства.
Многоэкстремальные
задачи - здесь
обычно выделяют
специализированные
классы задач,
часто встречающихся
в приложениях,
например, задачи
о минимизации
на выпуклом
множестве
вогнутых функций.
Важным разделом
математического
программирования
является
целочисленное
программирование
- когда на переменные
накладываются
условия целочисленности.
Первой из
"неклассических"
задач оптимизации
была подробно
исследована
задача отыскания
экстремума
линейной функции
на множестве,
заданном линейными
неравенствами
и равенствами.
Раздел теории
оптимизации,
изучающий такие
задачи, получил
название "линейное
программирование".
В данном
разделе изучается
задача линейного
программирования,
которая задается
следующим
образом.
1. Задача решается
относительно
переменных
.
В дальнейшем
они будут
записываться
в виде либо
вектора-столбца
либо вектора-строки
х = (х1,
..., хn).
Предполагается,
что вектор х
должен удовлетворять
системе n
линейных неравенств
3. В экономических
задачах присутствует
дополнительное
необходимое
условие: координаты
вектора х должны
быть неотрицательными:
где 0 - нулевой
вектор-столбец
размерности
n.
4. Целевая
функция представляет
собой линейную
функцию переменных
X1,…..,Xn
P1X1+…..PmXn=f(x1,….,xn)
(3)
5 .
Общая задача
линейного
программирования
(ЛП) состоит в
выборе вектора
х, удовлетворяющего
системе неравенств
(1),
(2)
и максимизирующего
целевую функцию
( 3 ).
Математически
задача ЛП
записывается
следующим
образом:
P1X1+…..+PnXn
max
(x1<….xn) (4)
Задача Линейного
Программирования
в матричной
форме записывается
следующим
образом. Обозначим
через b
вектор-столбец
правой части
СЛН
ч ерез
р - вектор-строку
коэффициентов
целевой функции.
Напомним, выражение
(р, х) означает
скалярное
произведение
векторов р и
х. Тогда в матричном
виде задача
ЛП записывается:
Таким образом,
в задаче Линейного
Программирования
константами
(параметрами)
являются коэффициенты
матрицы А, вектор
правой части
В и коэффициенты
целевой функции
- вектор P.
Подлежит определению
вектор х*=х1,..,,хn,),
который удовлетворяет
ограничениям
( 8 ),
( 9):
и доставляет
максимум целевой
функции ( 7):
Это матричная
запись задачи
ЛП на максимум
в стандартной
форме.
Запись задачи
линейного
программирования
( 4) -
(6)
или (7)
- (9) называют
записью ЗЛП
в стандартной
форме.
Иногда, исходя
из практических
требований,
отдельные
ограничения
на переменные
х,, ..., х„ могут
иметь вид точного
равенства
Это значит,
что решение
требуется
искать среди
векторов х,
координаты
которых удовлетворяют
i-му
ограничению
как точному
равенству.
Чтобы привести
в этом случае
задачу к стандартному
виду, уравнение
(10)
достаточно
заменить на
систему из двух
^неравенств:
У равнение
( 11)
и система (
12 ) или эквивалентны.
Задача линейного
программирования
вида:
называется
задачей линейного
программирования
в канонической
форме.
Чтобы привести
задачу линейного
программирования
в стандартной
фюрме к форме
канонической,
следует ввести
дополнительные
переменные
ui,ui>=0,i=1,2,….,m
, такие,
что
Причем целевая
функция при
этом должна
оставаться
неизменной.
Для этого запишем
целевую функцию
в виде:
Здесь коэффициенты
при переменных
u1,….,um
полагаются
равными нулю.
Тогда задача
(7)
- (9)
в каноническом
виде принимает
вид:
Стандартная
задача линейного
программирования
на минимум
(матричная
запись) записывается
в виде:
Таким образом,
не важно, в какой
форме получаются
линейные ограничения:
в форме равенств
или в форме
неравенств.
Эквивалентными
преобразованиями
возможно привести
неравенства
к равенствам
и наоборот.
Необходимость
преобразований
обычно связана
с тем, какой
применяется
метод решения.
Пусть некоторый,
однородный
товар (продукт)
хранится на
M
складах и
потребляется
в N
пунктах (например,
магазинах).
Известны следующие
параметры:
ai - запас
продукта на
-ом
складе,
ai>0, i=1,….,m
bj-
потребность
в продукте в
-ом
пункте,
bj>0,j=1,….,n
Cij -
стоимость
перевозки
единичного
количества
товара с -го
склада в
-й
пункт,
. Планируется
полностью
перевезти товар
со складов и
полностью
удовлетворить
потребности
в пунктах назначения.
При этом предполагается,
что суммарные
запасы равны
суммарным
потребностям:
Транспортная
задача ставится
как каноническая
задача ЛП следующего
специального
вида:
где - количество
товара, перевозимого
с I-го
склада в J-ый
пункт. Иными
словами, требуется
так организовать
перевозки
продукта со
складов в пункты
потребления,
чтобы при полном
удовлетворении
потребностей
минимизировать
суммарные
транспортные
расходы. Заметим,
что условие
( )
является необходимым
и достаточным
для существования
решения транспортной
задачи.
4.1 Определение
опорного плана
транспортной
задачи
Для решения
транспортной
задачи разработано
несколько
методов, каждый
из которых
отличается
от другого
методом заполнения
матрицы перевозок.
Существуют
два типа транспортной
задачи:
открытая и
закрытая.
Транспортная
задача называется
открытой если
сумма запасов
товара на складах
отличается
от суммы потребностей
товаров у магазинов.
Транспортная
задача называется
закрытой , если
сумма запасов
товара на складах
равняется сумме
потребностей
магазинов.
Решение существует
только для
закрытой транспортной
задачи, поэтому
если транспортная
задача открытая
, то ее надо привести
к закрытому
типу. Для этого
в случае , если
запас товара
на складах
превышает
потребность
магазинов, то
вводят фиктивного
потребителя,
который выбирает
весь избыток
товара. В случае
же, если существует
дефицит товара,
т.е. потребность
магазинов
больше, чем
запас товаров
на складах, то
вводят фиктивного
поставщика,
с фиктивным
запасом товара
на складе. В
обоих случаях
в матрице тарифов
перевозок |C|
данному
складу или
магазину
проставляется
нулевая цена
перевозки.
Алгоритм
метода минимального
элемента состоит
в следующем.
Просматривается
вся матрица
тарифов перевозок,
и из нее выбирается
позиция с наименьшим
значением
тарифа C,
затем просматриваются
значения наличия
запасов на
складе
A и потребности
у потребителя
B,
затем в данную
клетку записывается
величина D=MIN(A,B).
Из запасов
соответствующего
склада и потребностей
магазина вычитается
величина D
. Если запас
товара на складе
исчерпан, то
эта строка
исключается
из дальнейшего
рассмотрения.
Если потребность
магазина в
товаре удовлетворена
полностью, то
этот столбец
исключается
из дальнейшего
рассмотрения.
Может быть
случай , когда
одновременно
исключаются
и строка и столбец,
этот случай
называется
вырожденным.
В дальнейшем
весь процесс
повторяется
до тех пор , пока
не будет исчерпан
весь запас
товаров на
складах и не
будет удовлетворена
потребность
всех магазинов.
По полученной
матрице перевозок
вычисляется
целевая функция
задачи Z.
Метод состоит
в следующем.
Просматриваются
все строки и
столбцы матрицы
тарифов, вычисляется
разность между
двумя наименьшими
элементами
в строке или
в столбце. Затем
из всех этих
разностей
выбирается
строка или
столбец с
максимальной
разность. В
выбранной
строке или
столбце , как
и в методе
минимального
элемента, заполняется
клетка с наименьшим
значением
тарифа. Затем
обнулявшаяся
строка или
столбец исключаются
из рассмотрения
и весь процесс
повторяется
до полного
исчерпания
запаса товаров
на складах. По
полученной
матрице перевозок
вычисляется
целевая функция
Z.
В начальной
своей стадии
этот метод
похож на метод
минимального
элемента , но
для столбцов.
Просматривается
первый столбец
матрицы тарифов,
в нем находится
наименьший
элемент. Затем
проверяется
, минимален ли
этот элемент
в своей строке.
Если элемент
минимален в
своей строке,
то по методу
минимального
элемента в эту
клетку заносится
значение D=MIN(A,B),
соответствующие
запас и потребность
уменьшаются
на эту величину.
Обнулившаяся
строка или
столбец исключаются
из рассмотрения
и процесс
повторяется,
начиная с первого
неисключенного
столбца. Если
найденный
минимальный
элемент не
минимален в
своей строке,
то происходит
переход к следующему
столбцу и так
до тех пор, пока
не будет найден
такой элемент.
По полученной
матрице перевозок
вычисляется
целевая функция
Z. Этот
метод требует
интенсивных
операции обмена
с памятью , поэтому
более громоздок
по сравнению
с остальными
и требует больших
вычислительных
ресурсов.
Как и любая
задача линейного
программирования,
необходимо
построить
первоначальный
опорный план
для решения
задачи. Одним
из методов
построения
исходного
опорного плана
является так
называемый
метод «северо-западного»
угла.
Метод состоит
в следующем.
Просматривается
матрица тарифов
перевозок C
, начиная
с левого верхнего
угла (клетки).
В эту клетку
записывается
величина D=MIN(A,B).
Она вычитается
из запасов и
потребностей
соответствующего
склада и магазина.
Обнулившаяся
строка или
столбец исключаются
из рассмотрения,
затем процесс
опять повторяется
для левой верхней
клетки оставшейся
матрицы и так
до тех пор пока
весь запас
товаров не
будет исчерпан.
Полученный
опорный план
не оптимален,
поэтому его
дальнейшее
решение продолжают
одним из вышерассмотренных
методов.
2.1 Анализ
существующих
аналогов и
подсистем
Программное
обеспечение
для решения
задач линейного
программирования
и в частности,
транспортной
задачи разработано
уже в конце
60-ых – начале
70-ых годов и было
реализовано
как пакет программ
– библиотек.
Данный пакет
задач был реализован
на таких алгоритмических
языках как
Алгол, Фортран.
В западных
разработках
в основном
применялся
алгоритмический
язык Кобол. С
появлением
персональных
компьютеров
данный пакет
был перемещен
на ПК, с учетом
особенностей
реализации
трансляторов
вышеперечисленных
языков на ПК.
Также дополнительно
были реализованы
пакеты программ,
в основном
усилиями вузов
на языках Паскаль,
Си. Перенос
программного
обеспечения
на ПК открыл
новые возможности
в решении задач
линейного
программирования
и наглядного
отображения
результатов
вычислении,
что отсутствовало
на больших
вычислительных
системах –
мэйнфреймах.
Ход вычислении
и его результаты,
особенно для
многомерных
задач с большим
числом переменных
можно было
наглядно отобразить
на мониторе.
Кроме того
появление
интерактивных
программ, программ
, в ход которых
человек- оператор
мог активно
вмешаться,
корректировать
промежуточные
результаты
, изменить методику
расчетов, значительно
облегчал и
ускорял разработку
нового программного
обеспечения.
С развитием
аппаратного
обеспечения
совершенствовалось
и программное
обеспечение.
Алгоритмические
языки тоже
совершенствовались
согласно потребностям
экономики,
науки и т.д.
Особо бурное
развитие программного
обеспечения
началось с
появлением
операционной
системы Windows.
Почти все
существующее
программное
обеспечение
и алгоритмические
языки были
перенесены
на эту операционную
платформу.
Возможности
Windows усилили
интерактивную
сторону этих
алгоритмических
языков, перейдя
на объектно-ориентированный
принцип построения
алгоритмов,
что позволяло
использовать
уже наработанное
программное
обеспечение
без больших
изменений.
Одним из бурно
развивающихся
алгоритмических
языков является
Pascal и
его диалекты.
Первоначально
этот язык был
создан для
обучения студентов
основам программирования,
ввиду своей
простоты и
наглядности
конструкции.
Он был создан
Никлаусом
Виртом, и послужил
основой для
целого семейства
паскале-подобных
языков –
Modula, Classcal, Object Pascal.
Наиболее
развитую систему
программирования
на языке Pascal
построила
фирма Borland
– Turbo Pascal. Первоначально
она была реализована
для DOS,
с появлением
Windows ,
она была перенесена
в нее. И наконец,
была выпущена
новая версия
для Windows
– Delphi.
Без баз данных
сегодня невозможно
представить
работу большинства
финансовых,
промышленных,
торговых и
прочих организаций.
Потоки информации,
циркулирующие
в мире, который
нас окружает,
огромны. Во
времени они
имеют тенденцию
к увеличению.
Не будь баз
данных, мы давно
захлебнулись
бы в информационной
лавине. Базы
данных позволяют
информацию
структурировать,
хранить и извлекать
оптимальным
для пользователя
образом.
Поскольку
использование
баз данных
является одним
из краеугольных
камней, на которых
построено
существование
различных
организаций,
пристальное
внимание
разработчиков
приложений
баз данных
вызывают инструменты,
при помощи
которых такие
приложения
можно было бы
создавать.
Выдвигаемые
к ним требования
в общем виде
можно сформулировать
как:
"быстрота,
простота,
эффективность,
надежность".
Среди большого
разнообразия
продуктов для
разработки
приложений
Delphi занимает
одно из ведущих
мест. Delphi и
отдают предпочтение
разработчики
с разным стажем,
привычками,
профессиональными
интересами.
С помощью Delphi
написано
колоссальное
количество
приложений,
десятки фирм
и тысячи
программистов-одиночек
разрабатывают
для Delphi дополнительные
компоненты.
В основе такой
общепризнанной
популярности
лежит тот факт,
что Delphi, как
никакая другая
система программирования,
удовлетворяет
изложенным
выше требованиям.
Действительно,
приложения
с помощью Delphi
разрабатываются
быстро, причем
взаимодействие
разработчика
с интерактивной
средой Delphi
не вызывает
внутреннего
отторжения,
а наоборот,
оставляет
ощущение комфорта.
Delphi -приложения
эффективны,
если разработчик
соблюдает
определенные
правила (и часто
- если не соблюдает).
Эти приложения
надежны и при
эксплуатации
обладают
предсказуемым
поведением.
Б лок-схема
меню определение
опорного плана
(Transtask.pas)
Блок-схема
подпрограммы
решения методом
минимального
элемента MINIELEM
Блок-схема
подпрограммы
решения транспортной
задачи
Transsolver
Windows,
Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
Windows,
Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls,
ExtCtrls, Grids, ComCtrls, Math;
procedure
FormCreate(Sender: TObject);
procedure
edProviderCountChange(Sender: TObject);
procedure
edCustomerCountChange(Sender: TObject);
procedure
btnLoadDataClick(Sender: TObject);
procedure
btnLoadDataCClick(Sender: TObject);
procedure
btnSolveClick(Sender: TObject);
procedure
btnPrintClick(Sender: TObject);
a,b:
array of integer;// наличие
груза у поставщиков
c:
array of array of integer; // матрица
тарифов перевозок
d:
array of array of integer;// матрица
перевозок
(решение)
z,m,n:integer;
//число поставщиков
и потребителей
fmTransTask.stgSolve.Cells[j+1,i+1]:=IntToStr(d[i,j]);
fmTransTask.lblZ.Caption:=IntToStr(z);
for
i:=0 to m-1 do include(set_i,i);
for
j:=0 to n-1 do include(set_j,j);
//
поиск первоначального
минимального
ьэлемента в
матрице тарифов
if
(i in set_i) and (j in set_j) then
if
(i in set_i) and (j in set_j) then
d[imin,jmin]:=min(a[imin],b[jmin]);
//
определяем
исключаемую
строку столбец
SubCol,SubRow:array
of array of integer;
for
i:= 0 to m-1 do SetLength(SubRow[i],2);
for
j:= 0 to n-1 do SetLength(SubCol[j],2);
for
i:=0 to m-1 do include(set_i,i);
for
j:=0 to n-1 do include(set_j,j);
//
ищем первоначальный
минимальный
элемент в строке
//
ищем 1-ое наименьшее
значение в
строке
//
ищем первоначальный
минимальный
элемент в строке
if
(j in set_j) and (j<>SubRow[i,1]) then
//
ищем 2-ое наименьшее
значение в
строке
if
(j in set_j) and (j<>SubRow[i,1]) then
//
Вычисляем
разность между
двумя наименьшими
//
ищем первоначальный
минимальный
элемент в столбце
//
ищем 1-ое наименьшее
значение в
столбце
//
ищем первоначальный
минимальный
элемент в столбце
if
(i in set_i) and (i<>SubCol[j,1]) then
//
ищем 2-ое наименьшее
значение в
столбце
if
(i in set_i) and (i<>SubCol[j,1]) then
//
Вычисляем
разность между
двумя наименьшими
// сперва
находим начальный
наибольший
элемент
//отыскиваем
максимальное
значение в
строке
//
сперва находим
начальный
наибольший
элемент
//
сравниваем
максимальное
значение разности
по строкам и
столбцам
d[imax,SubRow[imax,1]]:=min(a[imax],b[SubRow[imax,1]]);
a[imax]:=a[imax]-d[imax,SubRow[imax,1]];
b[SubRow[imax,1]]:=b[SubRow[imax,1]]-d[imax,SubRow[imax,1]];
if
a[imax]=0 then Exclude(set_i,imax);
z:=z+d[imax,SubRow[imax,1]]*c[imax,SubRow[imax,1]];
d[SubCol[jmax,1],jmax]:=min(a[SubCol[jmax,1]],b[jmax]);
a[SubCol[jmax,1]]:=a[SubCol[jmax,1]]-d[SubCol[jmax,1],jmax];
b[jmax]:=b[jmax]-d[SubCol[jmax,1],jmax];
if
a[SubCol[jmax,1]]=0 then Exclude(set_i,SubCol[jmax,1]);
z:=z+d[SubCol[jmax,1],jmax]*c[SubCol[jmax,1],jmax];
for
i:=0 to m-1 do include(set_i,i);
for
j:=0 to n-1 do include(set_j,j);
//
находим начальный
минимальный
элемент строки
//
минимальный
элемент в j-ом
столбце найден
//
проверяем ,
минимальный
ли он в своей
строке
//
проверяем по
индексу не тот
ли это элемент
if
a[imin]=0 then exclude(set_i,imin);
procedure
TfmTransTask.FormCreate(Sender: TObject);
for
i:= 0 to m-1 do SetLength(c[i],n);
for
i:= 0 to m-1 do SetLength(d[i],n);
stgProvider.Cells[i-1,0]:=IntToStr(i);
stgCustomer.Cells[j-1,0]:=IntToStr(j);
procedure
TfmTransTask.edProviderCountChange(Sender: TObject);
stgProvider.ColCount:=StrToInt(edProviderCount.Text);
stgTarif.RowCount:=stgProvider.ColCount+1;
stgSolve.RowCount:=stgTarif.RowCount;
for
i:= 0 to m-1 do SetLength(c[i],n);
for
i:= 0 to m-1 do SetLength(d[i],n);
stgProvider.Cells[stgProvider.ColCount-1,0]:=edProviderCount.Text;
stgTarif.Cells[0,stgProvider.ColCount]:=edProviderCount.Text;
stgSolve.Cells[0,stgProvider.Colcount]:=edProviderCount.Text;
procedure
TfmTransTask.edCustomerCountChange(Sender: TObject);
stgCustomer.ColCount:=StrToInt(edCustomerCount.Text);
stgTarif.ColCount:=stgCustomer.ColCount+1;
stgSolve.ColCount:=stgTarif.ColCount;
for
i:= 0 to m-1 do SetLength(c[i],n);
for
i:= 0 to m-1 do SetLength(d[i],n);
stgCustomer.Cells[stgCustomer.ColCount-1,0]:=edCustomerCount.Text;
stgTarif.Cells[stgCustomer.ColCount,0]:=edCustomerCount.Text;
stgSolve.Cells[stgCustomer.Colcount,0]:=edCustomerCount.Text;
procedure
TfmTransTask.btnLoadDataClick(Sender: TObject);
a[i]:=StrToInt(stgProvider.Cells[i,1])
for
i:= 0 to m-1 do suma:=suma+a[i];
lblProvider.Caption:=IntToStr(suma);
b[j]:=StrToInt(stgCustomer.Cells[j,1])
for
j:= 0 to n-1 do sumb:=sumb+b[j];
lblCustomer.Caption:=IntToStr(sumb);
lblMsg.Caption:='Создать
фиктивного
поставщика
с грузом '+IntToStr(sumb
lblMsg.Caption:='Создать
фиктивного
потребителя
со спросом '+
procedure
TfmTransTask.btnLoadDataCClick(Sender: TObject);
c[i,j]:=StrToInt(stgTarif.Cells[j+1,i+1]);
procedure
TfmTransTask.btnSolveClick(Sender: TObject);
procedure
TfmTransTask.btnPrintClick(Sender: TObject);
writeln(out,'Исходные
данные транспортной
задачи');
writeln(out,'потребность
потребителей');
for
j:= 0 to n-1 do write(out,b[j]:8);
writeln(out,'Матрица
тарифов перевозок');
for
j:= 0 to n-1 do write(out,c[i,j]:8);
writeln(out,'Матрица
перевозок
(решение)');
Для нормальной
работы программы
необходим
персональный
компьютер
совместимый
с IBM PC ,
с процессором
не ниже
486, тактовой
частотой 120 Мгц,
оперативной
памятью не
менее 8 МБ, занимаемое
место на диске
после инсталляции
5 МБ.
Операционная
система Windows
95,98,NT.
К
основным критериям
качества любой
модели относятся
такие как:
Под
адекватностью
модели понимается
ее способность
наиболее точно
отражать все
свойства и
характеристики
моделируемой
среды. В качестве
критериев
адекватности
можно выбрать
, например, величину
отличия (абсолютных
и относительных)
входных и выходных
характеристик
модели и реального
объекта, сравнительная
оценка реакции
модели и объекта
и т.д.
Под
критерием
чувствительности
понимают степень
воздействия
изменения
параметров
модели на результаты
выдаваемые
моделью. Изменение
параметров
можно моделировать
меняя коэффициенты
в системе уравнений
, описывающих
модель, характер
изменения
входных данных
и т.д.
Критерий
устойчивости
– это количественная
или качественная
оценка, которая
характеризует
исследуемую
модель как
устойчивую
или неустойчивую.
Синтаксическая
отладка предназначена
для устранения
ошибок в языковых
конструкциях
на этапе написания
исходного
текста программы.
Большинство
интегрированных
пакетов разработки
программного
обеспечения
содержат встроенные
средства проверки
прямо в ходе
написания кода
программы.
Средства проверки
не только находят
синтаксические
ошибки, но также
делают подсказки
или дают рекомендации
для написания
данной конструкции.
Второй этап
, на котором
выявляются
синтаксические
ошибки – это
компиляция,
когда компилятор
строка за строкой
анализирует
исходный код
и выдает листинг
синтаксических
ошибок.
Семантическая
отладка осуществляется
для проверки
семантики
языковых конструкции
и является
одним из этапов
синтаксической
отладки.
Тестовые
отчеты и анализ
тестирования
При
сдаче программного
обеспечения
в эксплуатацию
необходима
провести его
тестовый прогон
в области допустимых
значении входных
параметров.
Для этого , в
основном проводят
ручной обсчет
одного или
нескольких
вариантов
решения задачи
и затем сверяют
воспроизводим
ость результатов
моделью. Адекватностью
модели служит
полная воспроизводим
ость тестовых
данных.
Семантическая
отладка - это
процесс нахождения
и исправления
ошибок связанных
с неправильным
указанием
логических
страниц данных.
Семантическая
отладка подразумевает
в себя проверку
поэтапного
хода выполнения
программы. Это
можно выявить
при тестирование
программы
правильно ли
мы задали тип
False или True
.
В Delpfi
при выполнении
операций в
логических
выражениях
поддерживается
две различные
модели:
При полной
схеме всегда
вычисляются
все операнды
и выполняются
все операции
выражения, даже
если его результат
будет известен
уже после первой
операции.
При использовании
короткой схемы
вычисление
операндов и
результатов
операций выполняется
строго с лева
на право и
прекращается,
как только
выполнение
дальнейших
действий перестанет
оказывать
влияние на
конечный результат
всего выражения.
В
ходе отладки
программного
пакета возникает
вопрос о таких
показателях
как скорость
(быстродействие)
работы программы,
объем занимаемого
места на диске,
необходимый
объем оперативной
памяти
О писание
блок-схемы
программы
Transtask.pas
Ввод
размерности
таблицы перевозок
m,n
Отображение
пустой таблицы
перевозок
m*n
Ввод
таблицы данных:Вектор
А, Вектор В,
Матрица С
Да.
Введение
фиктивного
поставщика
или потребителя.
Описание
Блок-схемы меню
определение
опорного плана.
О писание
блок-схемы
Определение
опорного плана
транспортной
задачи методом
минимального
элемента.
Корректируем
элементы исходного
массива
Заносим
в матрицу
перевозок
значение A
min
Тема:
Нахождение
опорного плана
транспортной
задачи
Тестирование
алгоритмов
и программ --
одна из наиболее
сложных и
ответственных
задач в процессе
их отладки.
Времени для
тестирования
мало, но и спешка
в работе недопустима,
слишком дорого
обходятся
неудачные
попытки предъявить
решение задачи.
Проверка корректности
алгоритмов,
равно как и
составление
авторами задачи
достаточно
полного набора
корректных
тестов -- наборов
данных для
задачи и ответов
к ним -- далеко
не всегда
представляют
собой простую
проблему.
В
задачах на
этапе тестирования
программ есть
много общего
-- и те и другие
должны обеспечить
корректность
алгоритмов.
Но есть и различия.
Автор задачи
не ограничен
во времени, но
должен предусмотреть
все возможные
огрехи участника.
Специфика
положения
тестирующего,
связана с коварством
составителя
тестов, от которого
можно ожидать,
например,
непредвиденной
глубины рекурсии,
разрядности,
точности вычислений
или размерности
наборов данных.
Поэтому будет
неправильно,
успешно решив
задачу для
нарисованного
на листочке
бумаги примера.
Будьте
внимательны!
Всегда есть
опасность
получить по
существу правильный,
но не тот ответ.
Кроме того,
способ описания
ответа может
послужить
намеком на
используемый
автором алгоритм
решения задачи.
Проверка
алгоритма на
данных максимальной
установленной
размерности:
по количеству
перечисленных
в условиях
задачи объектов,
по количеству
связей между
ними, по разрядности
и точности
машинного
представления
числовых параметров
и пр. Такая проверка
нужна для выявления
и отсева неэффективных
- медленно работающих
или нерационально
использующих
память программ.
Известны случаи,
когда, в принципе,
правильно
работающий
алгоритм приводил
к ошибочному
ответу из-за
ошибок переполнения
-- в условиях
задачи оговаривается
диапазон или
разрядность
исходных данных,
но не разрядность
промежуточных
результатов
или ответа.
Типичным примером
грубой ошибки
такого рода
может служить
нахождение
опорного плана
транспортной
задачи. Проверка
работоспособности
алгоритма в
вырожденных
случаях: срабатывание
пустого или
состоящего
из единственного
элемента цепного
списка, работа
программы с
графом, не содержащим
дуг и т.п. В некоторых
случаях, например,
при декомпозиции
задачи, когда
решение задачи
сводится к
решению задачи
меньшей размерности
переход от
начального
i=0 уменьшением
на единицу
может привести
к непредусмотренному
эффекту выхода
за границы
зарезервированной
памяти. Результат
работы на нижней
границе размерности
легко просчитывается,
иногда он будет
получен как
и в общем случае,
иногда удобней
вручную просчитать
его и предусмотреть
особую ветку
программы, но
никогда о нем
не следует
забывать.
Следует
иметь ввиду,
что построение
авторами заданий
тестов, особенно,
значительной
размерности
представляет
собой непростую
задачу. Возможно
несколько
подходов к
построению
тестов.
С оставление
тестов вручную.
Это возможно,
когда решение
задачи не
представляет
собой вычислительной
сложности (вся
сложность --
логическая).
Задача "Путь
на кубе" раздела
"Геометрия"
-- пример именно
такой задачи.
Во всех остальных
случаях подобный
путь тупиковый.
У участников
олимпиады
иногда выбора
нет, но не забывайте
проверить
случаи вырожденной
и максимальной
размерности
хотя бы в тривиальном
варианте (матрица
из нулей и единиц
не содержит
нулей или единиц,
в ней единственная
строка или
единственный
столбец, в графе
нет дуг, или
граф полный).
П рименение
случайных
чисел. Такие
генераторы
тестов удобно
конструировать
для числовых
последовательностей,
матриц или
графов. Достаточно
задать один
-- два параметра
настройки
датчика случайных
чисел и в вашем
распоряжении
замечательные
тесты. При
построении
матрицы из 0-1
таким параметром
будет доля
единиц среди
элементов
матрицы, координаты
очередной
единицы определяются
в результате
испытания с
равномерным
распределением
среди элементов
этой матрицы,
при построении
графа -- среднее
число дуг, выходящих
из вершины.
По дисциплине
Компьютерное
моделирование
На тему:
Нахождение
опорного плана
транспортной
задачи
Специальность
2203 “Программное
обеспечение
ВТ и АС”
1 .2
Описание целей
моделирования
их приоритеты.
Цель - Это
образ несуществующего,
но желаемого
с точки зрения
рассматриваемой
проблемы состояния
среды.
Система
- Средство достижения
цели, т,е всё
то, что нужно
для достижения
цели.
Моделирование
является
экспериментальной
и прикладной
методологией
имеющая целью:
по строительные
теории и гипотезы
которые могут
объяснить
наблюдаемое
поведение.
Использовать
эти теории для
предсказания
будущего поведения
системы, т.е
тех воздействий
которые могут
быть вызваны
изменением
в системе или
изменение
способов её
функционирования.
Данные с
которыми приходиться
иметь дело ,
часто представляются
в виде таблицы.
Это может быть
связано либо
с тем, что объём
таблиц ограничен
и в них можно
привести лишь
некоторые
данные.
Цель интерполяции
состоит в отыскании
значения функции
в некоторой
промежуточной
точке по отношению
к табличным
данным.
ЭВМ широко
применяется
для решения
научных, технических
и экономических
задач. Они способны
производить
вычисления
очень быстро,
выводить очень
точные результаты,
заполнять
большие массивы
информации
и производить
длинные и сложные
последовательные
вычисления
без вмешательства
человека.
Современный
компьютер имеет
следующие
основные компоненты:
центральный
процессор ,
который выполняет
арифметические
и логические
операции и
организует
процесс выполнения
программ.
Память служащая
для хранения
информации
В нешние
устройства
для управления
компьютеров
и ввода - вывода
информации.
Название: Нахождение опорного плана транспортной задачи
Раздел: Рефераты по информатике, программированию
Тип: реферат
Добавлен 09:59:59 02 августа 2005 Похожие работы
Просмотров: 2582
Комментариев: 18
Оценило: 7 человек
Средний балл: 4.4
Оценка: 4 Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" учебная работа...) - обращайтесь: https://clck.ru/P8YFs - (просто скопируйте этот адрес и вставьте в браузер) Сделаем все качественно и в самые короткие сроки + бесплатные доработки до самой сдачи/защиты! Предоставим все необходимые гарантии.
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Реферат: Нахождение опорного плана транспортной задачи
Курсовая Работа На Тему Сберегательный Банк Российской Федерации
Метод Лагранжа (метод вариации постоянной).
Курсовая работа по теме Расхищение памятников Камбоджи как международная проблема
Экспертные Методы Принятия Решений Реферат
Направления Сочинений 20 21
Воображение Сочинение Примеры
Дипломная работа по теме Организация документационного обеспечения деятельности службы кадров и направления его совершенствования на примере Акционерного общества 'Информационные спутниковые системы'
Отчет по практике по теме Анализ деятельности компании 'Лукойл'
Реферат по теме Понятие цели и задачи прокурорского надзора
Контрольная работа по теме Управление рисками в деятельности предприятия
Иностранные заимствования в лексике английского языка
Эссе Век Живи Век Учись Обществознание
Статья: Землетрясение у берегов Суматры
Место Расположения Церкви Покрова На Нерли Сочинение
Лабораторная работа: Решение задач методами Эйлера и Рунге-Кутта
#НАЗНАЧЕHИЕ: Реферат
Решу Огэ Сочинение На Тему Дружба
Контрольная работа: Природа и психологические особенности конфликта
Доклад по теме Юрий Павлович Казаков
Темы Дипломных Работ По Машиностроению
Реферат: Дидаскология
Реферат: Дивиденды
Доклад: Субстанциональный и процессуальный подход в психологии