М-Чм-зао-09

Рис.3.1.

Таким образом, конечно разностная СЛАУ сформирована и имеет вид (3.19). Далее можно приступать к ее решению любым известным вам способом. На рабочем листе Excel (рис.3.1) система решена с использованием надстройки поиск решения.

21

Полученное решение Y (1,000; 1,245; 1,474; 1,673; 1,829; 1,930) можно принять за первую итерацию (первое приближение) решения исходной задачи на разностной сетке Ωn , n=5.

3.2.2. Построение второй итерации

Для нахождения второй итерации сделаем сетку вдвое гуще (n=10, шаг h=0,1) и повторим приведенный выше алгоритм.

Это можно проделать на этом же листе книги Excel. Однако, если необходимо графически сравнить два приближения, то вторую итерацию надо построить на другом листе книги Excel.

Последовательность действий.

1.Сделаем копию листа Excel (рис.3.1) для n=5 на новый лист.

2.В ячейку В2 введем число разбивок n=10.

Рис.3.2.

3.Выделим блок ячеек А12:Н12 и скопируем его вниз до 9-го узла, т.е. до х=1.9, рис.3.2.

4.Введем значения an, bn , dn (n=10) в ячейки Е18, F18, H18 в соответствии с формулами (3.9-3.10). Таким образом, будет сформирована конечно разностная СЛАУ.

5.Решив эту систему, получим второе приближение исходной краевой задачи с шагом h=0.1. Это решение приведено на рис.3.3.

Рис.3.3.

22

6. Сравним полученные приближения. Для наглядности удобно построить графики этих двух приближений (двух сеточных функций) на одной координатной сетке, рис.3.4.

3.2.3. Порядок построения графиков приближенных решений краевой задачи.

Данные для построения графиков двух приближений (итераций) находятся на двух листах книги Excel и приведены для двух разностных сеток

Ω10 и Ω5 (h=0,1 и h=0,2)

1.Построим график решения задачи для разностной сетки с шагом

h=0,2 (n=5).

2.Активизируем уже построенный график и выберем команду:

меню Диаграмма\Добавить данные

Рис.3.4.

3.В окне Новые данные укажем данные xi, yi cо второго листа для разностной сетки с шагом h/2 (n=10).

4.В окне Специальная вставка установим флажки в полях:

Øновые ряды,

Øкатегории (значения по оси х) в первом столбце.

Как видно из приведенных данных, два приближенных решения краевой задачи (две сеточные функции) отличаются друг от друга не более, чем на 5%.

Поэтому за приближенное решение исходной задачи принимаем вторую итерацию, т.е.

Y (1,000; 1,124; 1,246; 1,364; 1,478; 1,584; 1,683; 1,772; 1,849; 1,914; 1,964)

23

Контрольная работа №4

Тема. Численные методы решения задач оптимизации. Линейное программирование

З а д а н и е

Решить задачу линейного программирования графическим методом и на ЭВМ. Сравнить полученные решения. Исходные данные приведены в приложении 4.

Указания к выполнению четвертой работы 4.1. Теоретические сведения

Общая постановка задачи линейного программирования (ЛП)

Требуется найти экстремум (min/max) линейной функции (функции цели) от n независимых проектных параметров x1 , x2 ,.., xn

Множество X (x1, x2 ,.., xn ) , удовлетворяющее условиям (4.2) называется

областью допустимых решений ( D ).

Допустимое решение X * ( x1* , x2 * ,.., xn * ) , которое минимизирует целевую функцию (4.1), называется оптимальным решением.

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

Геометрический метод решения используется для случая n=2, когда задача линейного программирования содержит два проектных параметра.

Постановка задачи. Требуется найти экстремум целевой функции

при условии, что на проектные параметры наложены следующие ограничения:

am x1 + bm x2 £ d m x1 ³ 0; x2 ³ 0

24

Координаты этой точки М(2,3) и есть решение задачи, т.е. в этой точке функция цели достигает своего минимума, т.е. zmin = -4, при x1 = 2, x2 = 3.

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

Пример 4.2. Решить пример 4.1, используя возможности таблиц Excel

Порядок решения

Систему неравенств (4.4) приведем к виду:

1.Подготовим таблицу как показано на рис.4.2. Ячейки, содержащие

целевую функцию (С12) и проектные параметры х1, х2 (изменяемые ячейки) В9:С9 тонируем. Для контроля счета в ячейки В9:С9 введем единицы. Значения

проектных параметров х1=1 и х2=1 можно рассматривать как нулевое приближение решения задачи.

2.В ячейки В3:D7 введем коэффициенты системы ограничений (4.5).

3.В ячейку E3 введем формулу для вычисления левой части первого ограничения, т.е. E3=СУММПРОИЗВ($B$9:$C$9;B3:C3)-D3, и после ввода скопируем ее вниз до конца таблицы. Будет не лишним проверить результаты счета для заданных значений х1=1 и х2=1.

Рис.4.2.

4. В ячейке C12 запишем формулу для целевой функции (4.3):

C12=1-В9-С9.

5. Минимизацию целевой функции (4.3) при ограничениях (4.4) выполним с помощью надстройки Excel Поиск решения. Для этого выделим ячейку С12. Выберем команду меню Сервис\Поиск решения и в появившемся

26

окне сделаем соответствующие установки, как показано на рис.4.3. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает окно для ввода этих ограничений (рис.4.3).

6.Щелкнем на кнопке Выполнить. Результат решения будет иметь вид, как показано на рис.4.2.

7.Результаты можно сохранить или отказаться (Восстановить исходные значения). Можно получить один из видов отчетов (Результаты, Устойчивость, Пределы). Отчет можно оформить на отдельном листе Книги с соответствующим именем.

Рис.4.3.

Таким образом, функция цели (4.3) при ограничениях (4.4) достигает своего минимума zmin = −4 при x1 = 2, x2 = 3, что соответствует решению этой же задачи геометрическим методом.

27

Контрольная работа №5

Тема. Численные методы решения задач оптимизации. Линейное программирование.

З а д а н и е

Составить математическую модель задачи линейного программирования: определить проектные параметры, записать целевую функцию и ограничения на проектные параметры. Решить задачу на ЭВМ. Выбрать задачу в соответствии с вариантом в приложении 5.

Рекомендации к выполнению работы №5

Основные стандартные схемы построения математических моделей задач линейного программирования и методы их решения приведены в [1]. Здесь приведены лишь некоторые из них.

Пример 5.1. Задача планирования производства.

Цех производит два вида продукции (Продукт1 и Продукт2) стоимостью соответственно 5 у.е. и 5,5 у.е. (усл. единиц).

На производстве действуют ограничения по ресурсам: сырье; трудовые затраты; транспортные расходы (аренда машины для вывоза продукции).

Расход каждого ресурса на изготовление того и другого продукта, количество ресурса в распоряжении цеха приведены в табл.5.1

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

Решение. В качестве проектных параметров x1, x2 выберем оптимальные объемы производства обоих продуктов. Тогда целевая функция запишется в

виде

Ограничения записываем из условия ресурсов, которыми располагает

цех.

Пример 5.2.. Транспортная задача.

На 3-х цементных заводах производится цемент одной и той же марки в количествах соответственно 100, 130, 170 тонн. Цемент следует доставить на четыре завода ЖБК, потребляющих его соответственно в количествах 150, 120, 80, 50 тонн. Стоимости (у.е.) перевозок одной тонны продукта с i-го (i=1,2,3) завода на j-ый (j=1,2,3,4) ЖБК приведены в таблице 5.2. Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Решение. В качестве проектных параметров xij выберем количество (т) продукта, перевозимого с i-го (i=1,2,3) завода на j-ый (j=1,2,3,4) ЖБК.

Ограничения записываем из условия, что вывозится весь произведенный на каждом заводе цемент (первые 3-и) и что каждый ЖБК полностью обеспечивается цементом.

x11 +x12 +х13+х14=100 x21 +x22 +x23+x24=130 x31 +x32.+x33+x34=170

(5.4)

x11 +x21 +х31=150 x12 +x22 +x32=120 x13 +x23.+x33=80 x14 +x24.+x34=50

xij³0 (i=1,2,3; j=1,2,3,4)

29

Пример 5.3. Задача рационального раскроя.

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

Количество и длины заготовок: заготовка №1 длиной 1655мм, 1шт.

№2 длиной 1050мм, 5шт. №3 длиной 210мм, 1шт.

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

Решение.

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

1) Составим таблицу-карту раскроя (табл.5.3):

Таким образом, получилось 4-е способа раскроя полос.

2)В качестве проектных параметров возьмем : xi – количество прокатных полос, раскроенных i-способом, i=1.2,3,4.

3)Определим длину отходов при каждом способе раскроя.

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

5) Запишем ограничения из условия, что для 12-и изделий необходимо: заготовок №1 – 12 шт.

заготовок №2 – 12*5 шт. заготовок №3 – 12 шт.

Т.е.