Информатика и информационные технологии

Y₂ = y(x₀+2h) = y₁ + hf(x₁,y₁),

И далее y_i+1 = y_i + hf(x_i,y_i),

При достаточно малой величине шага h метод Эйлера дает решение с большой точностью, т.к. погрешность решения близка к h² (h<<1) на каждом шаге интегрирования.

Алгоритм решения задачи в виде блок-схемы приведен на рис.18.

 

 

 

 

 

                                             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Рис.18.Блок-схема на решение дифференциального уравнения методом Эйлера

 

Задание

1.Создать проект на Delphi, позволяющий решать задачи на численные методы.

Пример:

Форма с решением задачи дифференциального  уравнения  (методом  Эйлера) на рис.19.

                                               Рис.19.Форма с Решение дифференциального уравнения        

Ниже приведена распечатка программы:

procedure TForm1.Button1Click(Sender: TObject);

var

x0,y0,xk,x,y,h:real;

Function f(x,y:real):real;

begin

f:=1+0.4*y*sin(x)-1.5*y*y;

end;

 begin

x0:=strtofloat(edit1.text);

y0:=strtofloat(edit2.text);

h:=strtofloat(edit3.text);

xk:=strtofloat(edit4.text);

memo1.Text:='   x   !   y    '+chr(13)+chr(10);

memo1.Text:=memo1.Text+'---------------'+chr(13)+chr(10);

x:=x0;

y:=y0;

repeat

y:=y+h*f(x,y);

x:=x+h;

memo1.Text:=memo1.Text+floattostrF(x,fffixed,5,2)+'   !   '+floattostrF(y,fffixed,5,2)+chr(13)+chr(10);

until

x>xk;

 end;

end.

 

 

 

 

2. Выполнить проверку решения данных задач в программе MathCAD.

Пример: Значение дифференциального уравнения  было найдено в Delphi по алгоритму. Была проведена проверка в MathCAD результат на рис.20.

                           Рис.20. Решение дифференциального уравнения в Mathcad

 

 

 

 

 

3.Оптимизационные модели

 

       3.1. Решение задачи линейного программирования симплекс-методом

Задание

Составить в табличном процессоре Excel таблицу, заполнить таблицу, выполнить вычисления. Описать теоретически выполненную работу.

Задача

Предположим, что для производства двух видов продукции А и В  можно использовать только материал трех сортов. При этом на изготовление единицы изделия вид А расходуется а1 кг материала первого сорта, a2 кг материала второго сорта и а3 кг материала третьего сорта. На изготовление единицы изделия вид В расходуется b1 кг материала первого сорта,  b2 кг материала второго сорта и b3 кг материала третьего сорта. На складе фабрики имеется всего материала первого сорта с1 кг, материала второго сорта с2 кг и материала третьего сорта с3 кг. От реализации единицы готовой продукции вида А фабрика имеет прибыль x рублей, а от продукции вида В прибыль составляет z  рублей.

Определить максимальную прибыль  от реализации всей продукции видов  А и В.

а1=19 ; a2=16; a3=19; b1=26; b2=17; b3=8; c1=868; с2= 638; c3=853; x=5; z=4;

 

Решение задачи линейного программирования в MS Excel

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

Необходимо решить задачу линейного  программирования вида:

19х1+26х2<=868

16x1+17x2<=638

19x1+8x2<=853

Fmax=5x1+4x2

 

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

1. Создать таблицу с исходными числовыми данными и ввести переменные с изменяемыми ячейками, в которые будут записываться получаемые результаты.
2. Составить формулу для целевой функции.
3. Указать адреса исходных и изменяемых данных, ограничения на переменные величины.
4. Сохранить полученные результаты и отчеты для анализа решения.

Выполнение работы

1. Составим на рабочем листе Excel таблицу – она изображена на рис.21.  В ячейки B4:B6 введем коэффициенты по переменной x₁, а в ячейки C4:C6 – по переменной x₂. В ячейки D4:D6 введем сводные члены.
2. Заполним формулами, необходимыми для создания ограничений столбца «Коэффициенты сравнения» в ячейки Е4:Е6. Выделим ячейку Е4, щелкнуть на значке f_x   на панели инструментов, в категории Математические выбрать функцию СУММПРОИЗВ, щелкнуть на кнопке ОК. В появившемся диалоговом окне щелкнуть на стрелке – указателе перехода в окне Массив 1. Диалоговое окно будет свернуто в строку ввода. Провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек B4:C4, щелкнуть на стрелке – указателе перехода для возврата в диалоговое окно. Аналогично ввести массив 2, выделив диапазон ячеек B11:C11. Закончить ввод, щелкнув на кнопке ОК. В строке формул появится формула с выбранными ссылками на ячейки.

Полученная формула  =СУММПРОИЗВ(B4:C4;B11:C11). Но для заполнения ячеек для последующих уравнений введем коррекцию в строке формул и добавим знаки «$» в формулу для диапазона В11:С11 и получим СУММПРОИЗВ(B4:C4;$B$11:$C$11).

3. Укажем необходимые ссылки на ячейки и ограничения для целевой функции, для этого выполним команду Сервис, Поиск решения. Появится диалоговое окно Поиск решения (Рис.22.), в котором требуется:

В поле Установить целевую ячейку необходимо указать ячейку Е12, для  этого надо щелкнуть на этой ячейке, если она видна из-под диалогового  окна, в противном случае следует щелкнуть на указателе перехода, чтобы свернуть окно (для возврата в диалоговое окно надо снова щелкнуть на указателе перехода). Результатом должна быть абсолютная ссылка $E$12.

Установить значение максимальному значению, щелкнув на соответствующем кружке.

В поле Изменяя ячейки указать диапазон $B$11:$C$11 либо прямым выделением этого диапазона с помощью мыши, либо с использованием указателя перехода.

В поле Ограничения необходимо создать список всех ограничений нашей задачи, для этого надо щелкнуть на кнопке Добавить. Появится диалоговое окно Добавление ограничения. $D$4:$D$6=$E$4:$E$6 – Условие полного распределения. После ввода ограничения по щелчку на кнопке Отмена, при этом возвращается диалоговое окно Поиск решения. Для корректировки ограничений имеются кнопки Удалить, Изменить, Добавить.

4. После ввода всех параметров  щелчок на кнопке Выполнить запустит поиск оптимального решения, Появится диалоговое окно Результаты поиска решения с сообщением об успехе или неуспехе поиска.

В случае, если решение найдено, можно выбрать переключатель Сохранить найденное решение и щелкнуть на кнопке ОК. В изменяемые ячейки В11:С11 будут записаны значения оптимального плана, а в ячейку Е12 – значение целевой функции.

Отменить результаты поиска, не выходя из окна Результаты поиска решения, можно так: либо щелкнуть на кнопке Отмена, либо установив переключатель Восстановить исходные значения, щелкнуть на кнопке ОК.

   Рис.21. Изображение таблицы на рабочем листе Excel

                   Рис.22. Диалоговое окно Поиск решения

     Рис.23. Решение задачи линейного программирования в MS Excel

 

3.2.Решение транспортной задачи

Задание

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

 

Решение транспортной задачи

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

Широкий класс экономических задач  приводит к поиску оптимального значения целевой функции, которая представляет собой линейную функцию нескольких переменных. К этому классу относится транспортная задача. Многие задачи, не являющиеся транспортными по физическому смыслу, в математической модели подобны им. Таковы, например, задачи оптимального распределения финансов, кредитов, производства между предприятиями, посевных площадей, задачи о назначениях, закреплении механизмов за видами работ и др. Решение транспортной задачи является основой решения всех перечисленных задач.

Транспортная задача формулируется  следующим образом: имеется т пунктов поставки и п пунктов потребления некоторого продукта. Для каждого пункта поставки задан имеющийся запас А_т продукта, а для каждого пункта потребности задан объем В_n потребностей. Известна также стоимость перевозки с_тп (тариф) из каждого пункта поставки в каждый пункт потребления единицы продукта. Требуется составить план перевозок с минимальной стоимостью.

Транспортная задача, в которой  сумма запасов равна сумме  потребностей, т. е. ΣА_m = ΣB_n называется задачей с закрытой моделью. Если же это равенство не выполняется, то говорят, что задача имеет открытую модель.

Стоимость перевозки от т-го поставщика к n-му потребителю равна произведению x_mn·c_mn, где x_mn - перевозимое количество продукта.

Стоимость всех перевозок равна  сумме стоимостей всех частичных  перевозок Σx_mn·c_mn, эту сумму и принимают за целевую функцию, для которой требуется найти минимальное значение.

В табличной форме эта задача выглядит так:

 

	B1	B2	B3
A1	5	4	3	60
A2	3	5	2	70
A3	4	3	6	75
A4	1	3	7	80
	50	65	70

 

Транспортная задача с закрытой моделью

Представим эту задачу в табличной  форме:

Здесь в каждой из первых трех строк  указаны поставщик, тарифы на перевозку  к каждому потребителю и величина запаса. В нижней строке указаны потребности, причем сумма по строке «Потребность» равна сумме по столбцу "Запасы".

Подсчитаем стоимость отдельной  перевозки, например 15 единиц продукта от поставщика A₂ к потребителю В₃: она составляет 15·4=60, при этом у поставщика остается еще 25 единиц продукта, а потребителю необходимо привезти от других поставщиков еще 20 единиц.

Общая стоимость перевозок равна  сумме стоимостей всех перевозок, т. е. сумме произведений соответствующих  тарифов на перевозимые количества продукта. В явном виде ее можно записать так:

F_min=5·x₁₁+4·x₁₂+3·x₁₃+3·x₂₁+

+5·x₂₂ +2·x₂₃+4·x₃₁+3·x₃₂+

+6·х₃₃+1·х₄₁+3·х₄₂+7·х₄₃

Величины х_тп являются искомыми переменными, а вся сумма - целевой функцией, минимальное значение которой надо найти.

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

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

2. Составить формулу для целевой  функции.

3.Указать адреса исходных и изменяемых данных, ограничения на переменные величины.

4. Сохранить полученные результаты  и отчеты для анализа решения.

 

Выполнение работы

      1. Составим на рабочем листе Excel две таблицы - они изображены на рис. 24. В таблице «Тарифы» записываются исходные числовые данные.

2. Заполним формулами, необходимыми  для создания ограничений на  запасы, ячейки F15:F18 столбца «Использовано»:

• В ячейку F15 ввести формулу суммы. Для этого надо выделить эту ячейку, щелкнуть на значке Σ на панели инструментов, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек В15:Е15, нажать клавишу Enter.

  Рис.24. Изображение двух таблиц на рабочем листе Excel

• Выделить ячейку F15, установить указатель мыши на маркер автозаполнения, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек F16:F18.

3. Заполним формулами, необходимыми  для создания ограничений на  потребности, ячейки В19:Е19 строки «Удовлетворено»:

• В ячейку B19 ввести формулу суммы. Для этого надо выделить эту ячейку, щелкнуть на значке Σ на панели инструментов, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек В15:B18, нажать клавишу Enter.
• Выделить ячейку B19, установить указатель мыши на маркер автозаполнения, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек C19:E19.

4. Для наглядности запишем общие  суммы по столбцам и строкам:

• в ячейку G19 - по столбцу «Запасы»: =СУММ(G15:G18);
• в ячейку F19- по строке «Потребность»: =СУММ (B19:E19).