Ленинградский ордена Ленина государственный университет имени А.А.Жданова

ВОЛКОВ В.А.

ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СРЕДНЕЙ ШКОЛЕ

Специальность 732- методика математики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата педагогических наук по методике математики

Ленинград 1968

Работа выполнена при Ленинградском ордена Ленина государственном университете им. А.А.Жданова.

Научный руководитель кандидат физико-математических наук И.В.Романовский.

Официальные оппоненты:

профессор.доктор физико-математических наук Залгаллер В.А. .

доцент «кандидат педагогических наук Кисельгоф С.И.. Ведущее предприятие Ленинградский государственный педагогический институт им. А.И.Герцена.

Автореферат разослан _ 1968 г.

Защита диссертации состоится __ 1968 г.

на заседании Ученого Совета математико-механического факультета Ленинградского ордена Ленина государственного университета ил.А.А.Жданова по адресу: г.Ленинград. В.О.. 10 линия, дом 33, ауд. 73.

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

Вопрос о реформе школьного образования, в частности о реформе математического образования, привлекает сейчас всеобщее внимание. Этому вопросу посвящены многие статьи в печати (например, А.Н.Колмогоров, И.М.Яглом "О содержании школьного курса математики", "Математика в школе", № 4, 1965, Б.В.Гнеденко "О перспективах математического образования", "Математика в школе", № 6, 1965 и др.), ряд выступлений видных ученых на различных совещаниях и конференциях. Например, в докладе "О математической подготовке экономистов и инженеров-экономистов" на пленарном заседании Научно-методического Совета по математике Министерства высшего и среднего специального образования СССР 20 декабря 1965 года лауреат Ленинской премии академик Л. В Канторович, ставя вопрос о коренной перестройке преподавания математики в вузах и о необходимости введения в их программы современных разделов математики таких, как линейное и нелинейное программирование, теория игр и статистических решений, теория графов и т.п., настаивал на том, чтобы эта перестройка отразилась также на программах средних школ.

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

Являясь одной из более гибких форм отражения в школьном образовании современных достижений науки, факультативные

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

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

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

Одним из таких направлений является линейное программирование.

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

показателей, которые могут быть при надлежащих условиях реализованы до разработки и осуществления полной системы оптимального планирования. А ведь они могут дать немедленный и большей эффект - значительно увеличить выпуск конечного продукта и повысить уровень жизни советских людей" ("Правда" от 24 августа 1965 года статья "Математика и экономика"). А профессор H.Я.Виленкин, обобщая опыт внеклассной работы по математике (Н.Я.Виленкин "О научном содержании внеклассной работы по математике", "Математика в школе", № 6:1965 г.) считает, что уже для учащихся VIII-IX классов посильно решение задач линейного программирования, представляющих интерес для хозяйственных органов.

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

За последние годы появилось значительное количество справочной, учебной и методической литературы по линейному программированию. Однако в подавляющем своем большинстве ока предназначена для высшей школы и недоступна для чтения учащимися средней школы. Отдельные попытки более популярного изложения вопросов линейного программирования, как в отечественной, так и в переводной литературе (на-

пример, В.А .Булавский, Г.Ш.Рубинштейн "Несколько лекций по линейному программированию", изд.СО АН СССР, 1965 г., Рейнфельд Н., Фогель У. "Математическое программирование (методы решения производственных и транспортных задач)", ИЛ , 1960 г. и др.) посвящены в основном частной задаче линейного программирования - транспортной задаче - и сводятся часто к рецептам, как решать те или иные задачи, не объясняя и не вскрывая полностью математической сущности методов линейного программирования.

Во всех известных пособиях по линейному программированию, за исключением книги С.И.Зуховицкого и Л.И.Авдеевой "Линейное и выпуклое программирование", изд."Наука", 1967 года, изложение элементов линейной алгебры, необходимых для объяснения постановки и решения задач линейного программирования, построено на теории определителей. По мнению диссертанта, такое построение не является вполне удовлетворительным не только для средней школы, но и для вузов.

Диссертант полагает, что наиболее рациональным методом ручного счета линейных систем и задач линейного программирования является метод, построенный на полных преобразованиях Жордана и описанный в книге С.И.Зуховицкого и Л.И.Авдеевой. Этому методу отдается предпочтение и с педагогической точки зрения, так как, во-первых, преобразования Гордана построены на способе подстановки, хорошо известном учащимся у уже VII класса средней школы, и их введение не вызыва-

ет трудностей и не требует много времени; во-вторых, этот метод позволяет построить простой и легко объяснимый алгоритм решения общей задачи линейного программирования.

В качестве основного понятия в диссертации вводится так называемое "преобразование таблиц с разрешающим элементом", представляющее из себя табличную модификацию обыкновенных исключений Жордана:

система

(1)

записывается в виде таблицы

(2)

Преобразованием таблицы с разрешающим элементом называется схематизированный перевод табл. (2) в таблицу

(3)

совершаемый по пяти правилам:

1) разрешающий элемент Ars заменяется единицей;

2) остальные элементы & -го столбца (разрешающего столбца) остаются без изменения;

3) остальные элементы Г -вой строки (разрешающей строки) лишь меняют свои знаки;

4) элементы, не принадлежащие разрешающим столбцу и строке, вычисляются по единому так называемому "правилу прямоугольника": 4ij 2 &у - &с5 <Xrj ;

5) все элементы новой таблицы делятся на разрешающий элемент Ars

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

относительно неизвестной Х$ , подстановка ее во все остальные уравнения системы (I) и запись полученной системы в виде новой таблицы.

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

Если невозможно все неизвестные поместить слева от таблицы, то система либо не имеет решений, либо имеет бесчисленное множество решений.

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

1. Метод 0-таблиц, когда исходная таблица, соответствующая) системе

записывается в виде следующей таблицы, получившей название нуль-таблицы:

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

2. Метод Гаусса, когда после каждого преобразования 0-таблицы вычеркивается не только О-столбец, но и разрешающая строка, которая предварительно выписывается и запоминается.

Метод преобразования таблиц с разрешающим элементом позволяет просто выяснить вопрос о совместности линейных систем в области неотрицательных чисел и находить одно из них, если они имеются.

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

(указанная нумерация неизвестных приведена лишь для удобства записи), в которой либо все свободные члены Ci (i**, **^*) неотрицательны, тогда система имеет неотрицательные решения, и одно из них получается приравниванием к нулю неизвестных, стоящих наверху таблицы; либо среди свободных членов есть отрицательные и их строки не содержат положитель-

ных элементов, тогда система не имеет неотрицательных решений.

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

Алгоритм решения общей задачи линейного программирования:

среди неотрицательных решений линейной системы

найти такое, при котором линейная функция

принимает наименьшее значение -

построен полностью на преобразованиях таблиц с разрешающими элементами.

На этапе 1 система ограничений приводится к указанному виду и вместе с целевой функцией записывается в таблицу

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

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

На этапе 3 определяется оптимальное решение, признаком которого является неотрицательность всех элементов строки целевой функции.

Если в столбце отрицательного элемента строки целевой функции нет отрицательных элементов, то задача не имеет конечного решения.

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

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

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

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

Основное внимание в работе обращается на педагогическую сторону вопроса.

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

расчету электрических цепей для постановки и решению их на уроках и внеклассных занятиях по физике.

Введение в новые школьные программы таких разделов линейной алгебры, как неравенства и системы неравенств и их геометрический смысл, дополнительные сведения о двумерном пространстве и др., еще более укрепит эти связи (А.Н.Колмогоров "О новой программе по математике для средней школы", доклад на Научно-методическом Совете по математике Министерства высшего и среднего специального образования СССР 22 декабря 1965).

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

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

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

Предложенные методы ручного счета задач линейного программирования и линейных систем окажутся полезными для уча-

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

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

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

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

Диссертация состоит из введения и двух основных частей.

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

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

В первой части дается конкретное содержание факультативного курса "Элементы линейного программирования", так как в настоящее время нет учебной литературы по линейному программированию, рассчитанной для средней школы.

В главе I первой части на конкретных примерах вводится понятие "преобразование таблиц с разрешающим элементом" и рассматриваются свойства преобразований.

В главе II рассматриваются решение и исследование систем линейных уравнений и определение их неотрицательных решений.

Глава III посвящена системам линейных неравенств. Указываются графические и аналитические методы решения систем линейных неравенств и определения их неотрицательных решений.

Глава IV посвящена основной задаче линейного программирования, где раскрывается ее математическая и экономическая сущность, указывается геометрический смысл и графический и аналитический методы ее решения.

В главе V рассмотрена транспортная задача и приводится полное обоснование метода потенциалов для ее решения.

После каждой главы первой части дается обширный материал для упражнений.

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

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

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

Материал диссертации освещен в работе автора "Элементы линейного программирования", опубликованной в "Ученых записках НГПИ", том XXIII, Новгород, 1967, стр.66-156.

Подписано к печати 26.УГ.1968 г. Уч.-изд.л.1, 1. Заказ • 716 M-230I2. Тираж 180 экз. Бесплатно

РТП. ЛИИЖТа. Ленинград, Московский пр.9