Алгоритмы и поиск решений

Пусть надо запрограммировать  запись на видеомагнитофоне - на 4 канале с 10.00 утра до 11.25. Это программа в  голове у человека кодируется примерно так:

ПОКА НЕ 10.00 - НИЧЕГО НЕ ДЕЛАТЬ

УСТАНОВИТЬ КАНАЛ НОМЕР 4

ВКЛЮЧИТЬ ЗАПИСЬ

ПОКА НЕ 11.25 - НИЧЕГО НЕ ДЕЛАТЬ

ВЫКЛЮЧИТЬ ЗАПИСЬ

Далее эта программа  должна быть перекодирована на язык видеомагнитофона:

ВЫБРАТЬ СВОБОДНОЕ МЕСТО

УСТАНОВИТЬ "ДАТА ЗАПИСИ" = СЕГОДНЯ

УСТАНОВИТЬ "НАЧАЛО ЗАПИСИ" = 10:00

УСТАНОВИТЬ "ОКОНЧАНИЕ  ЗАПИСИ" = 11:25

УСТАНОВИТЬ "НОМЕР ТЕЛЕКАНАЛА" = 4

Загрузка данной программы  в видеомагнитофон состоит в  нажатии на пульте видеомагнитофона соответствующих кнопок для каждой строки программы.

Компьютер - это такой  очень сложный и универсальный  домашний прибор. Компьютерная программа  является планом дальнейших действий компьютера так же, как программа  домашнего прибора является планом дальнейших действий этого прибора. Вывод: программирование компьютеров  ничем не отличается от программирования в быту.

Может ли человек, не прошедший  никакого курса информатики в  школе, разобраться с этим набором  современных домашних помощников? Это  очень трудный вопрос. На него нельзя ответить однозначно. Известно, что  люди старшего поколения сталкиваются с определенными трудностями  при проведении даже элементарных действий по программированию современной домашней техники. Конечно, проще всего это  объяснить старческим маразмом или  отсутствием современной техники  в домах «пожилых родителей». Но это не так - программированию можно  учить. А когда вокруг все техническое  окружение становится программируемым - нужно учить!

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

Программы из двух-трех шагов  можно просто запомнить и считать  своими рефлексами: «хочу кушать - жму  кнопку два, когда загорится лампочка - можно кушать». Но жить, зазубривая все нужные программы, - не получится. Программируемых приборов так много, инструкции к ним так объемны, требуемые программы так длинны, запоминать команды на языках приборов так лень. Для телевизора, например, нельзя благоприобрести рефлекс: НАЖАТЬ КНОПКУ ОДИН, ДОКРУТИТЬ РУЧКУ ДВА, ПОВТОРИТЬ ВСЕ СНАЧАЛА ДЛЯ  КАНАЛОВ 1-32, ЕСЛИ ТЕЛЕКАНАЛЫ УЖЕ НАСТРОЕНЫ, НИЧЕГО НЕ ДЕЛАТЬ. Как минимум в  данной инструкции нужно понимать, как менять номера каналов.

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

7.Поиск решений            

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

Для запуска надстройки Поиск решения  в Excel 2003 необходимо выбрать в строке Меню-Сервис-Надстройки-установить флажок против команды Поиск решения, если такая строка отсутствует, то необходимо нажать на строку с командой: Надстройки, и поставить отметку против строки Поиск решения (рис. 1). Тот, кто использует Excel 2007, необходимо открыть окно Параметры Excel, в котором следует выбрать (слева) кнопку  , затем в нижней части окна найти:  . После того, как будет нажата кнопка: Перейти…, поставить флажок против команды Поиск решения, как показано на рис. 1. После закрытия  окна Надстройки, на ленте в закладке Данные появится инструмент Анализ, внутри которого будет отображена команда: Поиск решения. Все дальнейшие действия для любой версии MS Excel будут аналогичными. 

 

Рис. 1. 

 

Для освоения правил работы с надстройкой Excel – Поиск решения, решим практическую задачу, постановка, которой заключается в следующем:

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

Формализация постановки задачи начинается с ввода обозначений для будущей модели

- пусть намечается выпуск 3-х  видов продукции: П1, П2, П3, (j=1, …, 3);

- для производства продукции  используется шесть видов деталей  (ресурсов) (i=1, … , 6);

- известны нормы расхода деталей  (ресурсов) на изготовление единицы  каждого вида продукции a_ij [ед.детал./ед.прод.];

- каждый вид деталей (ресурса)  ограничен b_i [ед.детал.] наличием на складе;

- предполагается, что от реализации  единицы продукции, предприятие  получает прибыль P_j [ден.ед./ед.прод.].

Исходные данные оптимизационной  задачи сведены в таблице 1. 

 

Таблица 1 с исходными данными

Наименование деталей на складе	Наличие на складе	Вид продукции
		Телевизор	DVD плейер	Компьютер
Шасси	450	1	0	1
Динамик	340	4	2	1
Блок питания	500	1	1	1
Монитор	125	1	0	1
Электронная плата	270	2	1	1
Процессор	470	0	1	1
Прибыль от реализации единицы продукции (руб.):		75	50	35

 

 

Введем обозначения для построения математической модели:

Через X_j – обозначим неизвестное, которое показывает возможное количество выпускаемой продукции j-ого вида, при использовании (a_ij) существующих норм единицы деталей (ресурса) на выпуск определенного вида продукции, при ограничениях на общее использование ресурса b_i. Добавим дополнительное условие, которое показывает, что изготовляемая продукция должна быть выпущена всех видов. Это значит, что все переменные X_j должны быть не менее 1 (X₁ ? 1, X₂ ? 1,X₃ ? 1). Отметим, что, если не имеет значение, какие виды продукции следует выпускать при поиске оптимального использования ресурсов, то в ограничениях следует указать не 1, а 0. Обозначив через Z величину суммарной прибыли при организации выпуска продукции, можно записать следующую систему уравнений:  

 

Z = 450·X₁ + 125·X₂ + 340·X₃ ? max

1?X1 + 0?X2 +  1?X3  ? 450	Шасси
4?X1 + 2?X2 +  1?X3  ? 340	Динамик
1?X1 + 1?X2 +  1?X3  ? 500	Блок питания
1?X1 + 0?X2 +  1?X3  ? 125	Монитор
2?X1 + 1?X2 +  1?X3  ? 270	Электронная плата
0?X1 + 1?X2 +  1?X3  ? 470	Процессор
X1 ? 1, X2 ? 1, X3 ? 1	Ограничения для выпуска продукции

 

 

Создание  модели в Excel

1.      Открыть табличный процессор Excel.

Подготовить начальную таблицу для размещения  описаний задачи, исходных данных, ограничений, коэффициентов целевой функции, место для проведения вычислений и сохранения результатов. Начальная таблица, как она будет выглядеть в Excel, представлена на рис. 1. Столбец D введен для занесения результатов в ячейки D5:D10. В  этих ячейках будут отображаться результаты вычислений, т.е. сколько на самом деле будет задействовано единиц каждого вида ресурса для выпуска всей номенклатуры продукции. Добавить в таблицу новые обозначения, которые понадобятся для ввода начальных значений и вывода результатов. Для этой цели:

·          в строке 11 (ячейки E11:G11) ввести коэффициенты для целевой функции, ее название - «Прибыль от реализации единицы продукции»;

·          в строке 12 создать заголовок – «Значения X_j при решении задачи», ячейки E12:G12 понадобятся для ввода формул;

·          ячейку E13 можно выделить, в которой будет формироваться результат, поэтому в строке 13 сделана запись – «Конечная прибыль от реализации продукции», это и есть значение целевой функции. 

 

Рис. 1. 

 

2.      Ввести формулы в таблицу с начальными данными. Для решения оптимизационной задачи методом линейного программирования необходимо математическую модель записать в терминахExcel, т.е.  в определенные ячейки предварительно необходимо ввести формулы. В таблице 2 указаны координаты ячеек для рассматриваемого примера, математическая запись уравнений и формулы, которые введены в соответствующие ячейки в табличном процессоре Excel. 

 

Таблица 2. Перечень формул для установки  в ячейках таблицы Excel

Ячейка	Математическая запись	Формула
D5	1?X1 + 0?X2 +  1?X3	=$E$13*E5+$F$13*F5+$G$13*G5
D6	4?X1 + 2?X2 +  1?X3	=$E$13*E6+$F$13*F6+$G$13*G6
D7	1?X1 + 1?X2 +  1?X3	=$E$13*E7+$F$13*F7+$G$13*G7
D8	1?X1 + 0?X2 +  1?X3	=$E$13*E8+$F$13*F8+$G$13*G8
D9	2?X1 + 1?X2 +  1?X3	=$E$13*E9+$F$13*F9+$G$13*G9
D10	0?X1 + 1?X2 +  1?X3	=$E$13*E10+$F$13*F10+$G$13*G10
E11	X1 ? 1	>=1
G11	X2 ? 1	>=1
F11	X3 ? 1	>=1
E14	450·X1 + 125·X2 + 340·X3	=E12*E13+F12*F13+G12*G13

 

 

3.      Работа с надстройкой Excel – Поиск решения

·          Вызвать окно: Поиск решения (рис. 1), нажать на кнопку  .

·          Ввести начальные значения X_j в ячейки E13:G13. Например, по двадцать единиц каждого вида изделия.

·          Выделить курсором ячейку E14 с целевой функцией.

·          Выбрать команду в меню Сервис-Поиск решения.

·                                В открывшемся диалоговом окне – Поиск решения, заполнить окна: Изменяя ячейки и Ограничения (можно проверить в диалоговом окне факт установки курсора на целевой ячейке, если требуется, то ее положение можно изменить). На рис. 3 показано всплывающее диалоговое окно Поиск решения, в котором проведены все перечисленные подготовительные действия. 

 

Рис. 3. 

 

·          Установить диапазон ячеек в строке всплывающего окна: Изменяя ячейки, в которых будет отображаться результат с количеством номенклатуры X_j изделий. В рассматриваемом примере, это будут ячейки E13:G13, которые должны быть фиксированными (перед координатами ячее ставится знак $).

·          Отметить селекторную кнопку: Равной максимальному значению, т.к. определяется максимальное использование ресурсов.

·          В окно с наименованием Ограничения последовательно ввести все ограничения для уравнений модели. В данном примере ячейки C5:C10 содержат количество деталей на складе, которые потребуются для выпуска всей номенклатуры продукции, а в ячейки D5:D10 были внесены формулы модели по каждому виду комплектующей, следовательно, суммарное количество используемых деталей не должно превышать величину, указанную в правой части уравнения. Для ввода ограничений, необходимо нажать на кнопку  . После выполненного действия будет открыто диалоговое окно с наименованием Добавление ограничений, которое показано на рис. 4. В окне видно, что вычисляемое значение в ячейке D5 должно быть меньше или равно установленной величины в ячейке C5.  

 

Рис. 4. 

 

·          Если требуется ввести еще ограничения, то нажать на кнопку  , в противном случае нажать на кнопку  .

·          Ввести ограничения на выпуск номенклатуры продукции в ячейки E13:G13 (в примере всего три вида продукции). Так, в качестве примера, на рис. 5 показано диалоговое окно для добавления ограничений, в котором указано, что вычисляемое значение в ячейке G13 должно быть более 1 единицы (это условие записано в исходной таблице для изделия – Компьютеры). 

 

Рис. 5. 

 

·          Ввести ограничения на форму представление результатов. В данной постановке задачи подразумевается, что количество изделий не может быть дробной величиной, а должны отображаться только целыми числами, следовательно, при выполнении расчетов, это обстоятельство необходимо учитывать. На рис. 6 показано диалоговое окно для добавления ограничений, в котором для ячейки E13 (в ней отображается количество единиц изделия), установлено условие ‘цел’, что означает целочисленное решение. В раскрывающемся списке выбирается необходимое условие.