Информатика (стр. 4 )

Для решения задачи построим рабочую область на листе MS Excel (Рисунок 25). В первой таблице представлены все исходные данные, вторая таблица рабочая, предназначена для решения задачи. Рабочая таблица содержит формулы, предназначенные для контроля количества изделий привезенных на каждую стройку и полученных у каждого поставщика. Центральная часть таблицы предназначена для размещения решения задачи (значений Xij) и на этом этапе может оставаться пустой.

Рисунок 25– Подготовка области листа для решения транспортной задачи

Для вычисления стоимости перевозок использована функция СУММПРОИЗВ, которая имеет два аргумента, каждый из которых представляет собой массив (диапазон ячеек). Эти диапазоны имеют одинаковую размерность. В алгоритме работы этой функции предусмотрено умножение каждой ячейки одного диапазона на соответствующую ячейку второго диапазона и последующее сложение полученных результатов, что и требуется для вычисления общей стоимости перевозок (см. выражение (1) и (6)).

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

Попробуем составить хотя бы один допустимый план. Для этого можно использовать, например, метод северо – западного угла. При этом перевозки распределяются по диагонали, начиная с верхнего левого (северо – западного) угла. Рассматриваем взаимодействие двух объектов «Стройка1-ЖБИ-1». Поскольку первой стройке требуется 80 изделий, завод может предоставить 100, в ячейку В11 записываем число 80 и введенное значение сразу изменяет значение ячеек, контролирующих выполнение обязательств по поставкам. Сравнив контрольные значения с соответствующими ячейками верхней таблицы, понимаем, что нужно забрать еще 20 единиц у ЖБИ-1 и отправляем их на стройку 2. После этого переходим в ячейку С12 и вписываем 100 недостающих стройке 2 изделий, поскольку завод ЖБИ-2 готов их предоставить. Затем записываем 50 изделий для стройки 3 с ЖБИ-2 и т. д. По мере построения плана контрольные значения в ячейках (F11:F13) и (B14:E14) должны сравняться с соответствующими значениями в верхней таблице, а в ячейке В15 вычисляется общая стоимость перевозок.

Поставщики	Потребители	Получено у поставщика
Стройка 1	Стройка 2	Стройка 3	Стройка 4
ЖБИ-1	80	20			100
ЖБИ-2		100	50		150
ЖБИ-3			150	30	180
Доставлено на стройку	80	120	200	30
Стоимость перевозок равна	1520

Рисунок 26 – план перевозок, построенный методом северо-западного угла

Полученный план является допустимым, поскольку все условия (ограничения) выполнены и даже базисным, поскольку количество переменных 3+4-1=6 (n+m-1), однако он достаточно произвольный и нет никакой гарантии, что выбрав другие 6 ячеек в качестве базисных мы не получим план перевозок с меньшей стоимостью. Поскольку транспортная задача имеет достаточно богатую историю, существует различные способы улучшения подобного плана в сторону уменьшения его стоимости. Они дают неплохие результаты, но достаточно трудоемки.

Поскольку транспортная задача является типичной задачей оптимизации, для ее решения MS Excel хорошо подходит уже известное Вам средство «Поиск решения».

Рисунок 27 - Настройка окна "Поиск решения"

Чтобы задать исходные данные для решения задачи необходимо выполнить настройки диалогового окна «Поиск решения»: адрес ячейки, в которой содержится формула для вычисления затрат (целевая ячейка), направление оптимизации (выбираем минимальное значение), диапазон ячеек, предназначенных для значений Xij (параметр «изменяя ячейки») и набор ограничений. Чтобы перейти к формированию списка ограничений следует щелкнуть мышкой по окну «Ограничения» и нажать кнопку «Добавить». Каждое ограничение формируется в отдельном окошке, переход к следующему ограничению по кнопке «Добавить».

Рисунок 28 – Окно формирования ограничения

Следует обратить внимание на структуру окна формирования ограничения. Поле «Ссылка на ячейку:» содержит адрес ячейки или диапазона ячеек, являющихся переменными. Это могут быть ячейки, предназначенные для подбираемых параметров или ячейки, в которых записаны формулы. В поле «Ограничение:» записывается константа или адрес ячейки, содержащей константу, которая, собственно, и является ограничением для переменной (или группы переменных), адреса которых указаны в поле «Ссылка на ячейку:». Отношение между ними (среднее поле) выбирается из раскрывающегося списка.

Если группа переменных имеет одинаковое ограничение, есть смысл использовать групповые операции (указание диапазона), в противном случае следует формировать ограничение для каждой переменной. Обратите внимание: при формировании третьей и четвертой строки списка ограничений (Рисунок 27) правые части с точки зрения относительной адресации являются одинаковыми.

После добавления последнего ограничения следует нажать кнопку «OK» для возвращения в окно поиска решений. В случае обнаружения неверно построенного ограничения его можно изменить или удалить, нажав мышкой на соответствующую кнопку.

Примечание: поскольку математическая модель транспортной задачи формулируется как линейная (все переменные в первой степени), не помешает открыть окно параметров (кнопка «Параметры» на окне «Поиск решения») и поставить галочку «Линейная модель». В некоторых случаях (когда «Поиск решения» не может найти решение) бывает полезно увеличить предельное число итераций (например, до 1000).

Рисунок 29 - Окно настройки параметров поиска решения

После нажатия кнопки «OK», подтверждающей изменения настроек последует возврат в окно «Поиск решения» (Рисунок 27) и после нажатия кнопки «Выполнить» будет открыто окно результатов решения.

Рисунок 30 - окно результатов решения

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

Поставщики	Потребители	Получено у поставщика
Стройка 1	Стройка 2	Стройка 3	Стройка 4
ЖБИ-1	0	0	70	30	100
ЖБИ-2	80	70	0	0	150
ЖБИ-3	0	50	130	0	180
Доставлено на стройку	80	120	200	30
Стоимость перевозок равна	1380

Рисунок 31 - решение транспортной задачи

Примечание: в целях более эффектного оформления таблицы решения в области значений Xij можно применить условное форматирование. Выделите область решения (диапазон ячеек (В11:Е13)), откройте окно условного форматирования (Меню Формат ® Условное форматирование) и для значений, равных нулю, установите формат – белый цвет шрифта.

Рисунок 32 - Окно условного форматирования

Окончательно область решения примет вид:

Рисунок 33 – Вид области решения после условного форматирования

Как видим, стоимость решения, полученного в результате оптимизации значительно ниже, чем для решения, построенного вручную (Рисунок 26).

3.  Задания для выполнения контрольной работы

3.1.  Решение нелинейных уравнений

1.	0.5x-0.4x+0.62=0	E=0.05	38.	0.3x-6.4x-6.9=0	E=0.03
2.	0.5x-0.8x+2.72=0	E=0.03	39.	0.3x-6.7x-8.1=0	E=0.05
3.	0.5x-1.2x+2.39=0	E=0.03	40.	0.3x-6.7x-8.1=0	E=0.05
4.	0.5x-1.6x+12.37=0	E=0.01	41.	0.3x-7x-2.43=0	E=0.05
5.	0.5x-x+2.98=0	E=0.05	42.	0.9x-0.4x+10.45=0	E=0.05
6.	0.5x-2.4x-1.73=0	E=0.02	43.	0.9x-0.8x+1.84=0	E=0.05
7.	0.5x-2.8x+1.51=0	E=0.02	44.	1.1x-6.5x+6.082=0	E=0.01
8.	0.5x-3.2x+6.16=0	E=0.02	45.	0.9x-1.2x-0.5=0	E=0.04
9.	0.5x-3.6x-3.71=0	E=0.01	46.	0.9x-1.6x-0.24=0	E=0.04
10.	0.5x-3.8x-3.59=0	E=0.01	47.	0.9x-2x+4.54=0	E=0.04
11.	0.5x-4.2x-4.57=0	E=0.02	48.	0.9x-2.4x+10.73=0	E=0.03
12.	0.5x-4.6x-3.31=0	E=0.02	49.	0.9x-2.8x-1.72=0	E=0.03
13.	0.5x-4.8x-3.81=0	E=0.03	50.	0.9x-3.2x-2.1=0	E=0.03
14.	0.5x-5.2x+3.38=0	E=0.03	51.	0.9x-3.4x-18.61=0	E=0.02
15.	0.5x-5.6x-3.89=0	E=0.03	52.	0.9x-3.8x-1.72=0	E=0.02
16.	0.5x-6x-4.29=0	E=0.05	53.	0.9x-0.3x-1.08=0	E=0.02
17.	0.5x-6.4x-4.48=0	E=0.05	54.	0.7x-0.7x+0.5=0	E=0.02
18.	0.5x-6.8x-4.22=0	E=0.05	55.	0.7x-1.1x+0.2=0	E=0.01
19.	0.5x-7.22x-2.71=0	E=0.05	56.	1.1x+0.1x+13.79=0	E=0.03
20.	0.3x-0.3x+0.32=0	E=0.02	57.	1.1x+0.3x+0.464=0	E=0.03
21.	0.3x-0.7x+0.06=0	E=0.02	58.	1.1x+0.5x+0.863=0	E=0.05
22.	0.3x-1.1x+2.92=0	E=0.02	59.	1.1x+0.7x+22.33=0	E=0.01
23.	0.3x-1.5x+3.74=0	E=0.03	60.	1.1x+0.9x+0.66=0	E=0.03
24.	0.3x-1.9x-1.78=0	E=0.03	61.	1.1x+1.1x+15.5=0	E=0.05
25.	0.3x-2.3x-2.42=0	E=0.03	62.	1.1x+1.3x+0.34=0	E=0.01
26.	0.3x-2.7x-3.1=0	E=0.03	63.	1.1x+1.5x+1.059=0	E=0.03
27.	0.3x-3.1x-3.81=0	E=0.02	64.	1.1x+1.7x+7.962=0	E=0.02
28.	0.3x-3.4x-3.8=0	E=0.01	65.	1.1x+1.9x+18.54=0	E=0.02
29.	0.3x-3.7x-2.96=0	E=0.01	66.	1.1x+2.1x+1.774=0	E=0.03
30.	0.3x-4x-4.66=0	E=0.02	67.	1.1x+2.3x+12.35=0	E=0.05
31.	0.3x-4.3x-5.25=0	E=0.02	68.	1.1x+2.5x+40.86=0	E=0.01
32.	0.3x-4.6x-4.83=0	E=0.02	69.	1.1x+2.7x+15.35=0	E=0.03
33.	0.3x-4.9x-3.46=0	E=0.01	70.	1.1x+2.9x+25.63=0	E=0.05
34.	0.3x-5.2x-7.66=0	E=0.01	71.	1.1x+3.3x+41.62=0	E=0.03
35.	0.3x-5.5x-7.96=0	E=0.01	72.	1.1x+3.5x+18.085=0	E=0.05
36.	0.3x-5.8x-4.12=0	E=0.03	73.	1.1x+3.7x+17.96=0	E=0.01
37.	0.3x-6.1x-7.36=0	E=0.03	74.	1.1x+3.9x+15.76=0	E=0.03
75.	1.1x+4.1x+12.65=0	E=0.05	82.	1.1x+5.5x+46.2=0	E=0.01
76.	1.1x+4.3x+28.187=0	E=0.01	83.	1.1x+5.7x+1.324=0	E=0.03
77.	1.1x+4.5x+25.31=0	E=0.03	84.	1.1x+5.3x+0.829=0	E=0.05
78.	1.1x+4.7x+27.45=0	E=0.05	85.	1.1x+6.1x+5.199=0	E=0.01
79.	1.1x+4.9x+28.68=0	E=0.01	86.	1.1x+6.3x+2.12=0	E=0.03
80.	1.1x+5.1x+0.562=0	E=0.03	87.	0.5x-1.9x+4.33=0	E=0.01
81.	1.1x+5.3x+19.95=0	E=0.05	88.	0.5x-1.6x+12.37=0	E=0.01

3.2.  Численное интегрирование

1.		Iточн.=13.416	14.		Iточн.=26.329
2.		Iточн.=-20.405	15.		Iточн.=2.033
3.		Iточн.=11.234	16.		Iточн.=2.574
4.		Iточн.=0.556	17.		Iточн.=-46.788
5.		Iточн.=2727	18.		Iточн.=-6.272
6.		Iточн.=4.887	19.		Iточн.=6.909
7.		Iточн.=12.667	20.		Iточн.=5.437
8.		Iточн.=2.316	21.		Iточн.=63.017
9.		Iточн.=5.907	22.		Iточн.=2.933
10.		Iточн.=17.354	23.		Iточн.=8.048
11.		Iточн.=19.037	24.		Iточн.=1.333
12.		Iточн.=3.566	25.		Iточн.=0.614
13.		Iточн.=6.5	26.		Iточн.=2.678
27.		Iточн.=0.969	34.		Iточн.=17.822
28.		Iточн.=-31.356	35.		Iточн=2.525
29.		Iточн.=0.65	36.		Iточн=-4.829
30.		Iточн.=7.273	37.		Iточн=-11.952
31.		Iточн.=0.732	38.		Iточн=10.699
32.		Iточн.=3.106	39.		Iточн=2.865
33.		Iточн.=1.638	40.		Iточн=3.582

3.3.  Решение системы линейных алгебраических уравнений (СЛАУ)

1.		6.
2.		7.
3.		8.
4.		9.
5.		10.
11.		23.
12.		24.
13.		25.
14.		26.
15.		27.
16.		28.
17.		29.
18.		30.
19.		31.
20.		32.
21.		33.
22.		34.

3.4.  Аппроксимация. Метод наименьших квадратов (МНК)

X	0.78	1.56	2.34	3.12	3.81
Y	2.5+N	1.2+N	1.12+N	2.25+N	4.28+N

Внимание! Приведенные в таблице данные являются базовыми. Индивидуальные данные для задания на контрольную работу определяются номером варианта (N) контрольной работы, выданным студенту преподавателем.