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

Введение

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

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

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

Первые попытки внедрить компьютер в обучение были сделаны еще в 50-х годах, когда в качестве устройства ввода/вывода использовался телеграфный аппарат. В течение последующих 40-лет ведутся непрерывные интенсивные исследования в этой области. За это время компьютерная техника изменилась, стала более совершенной, появились персональные компьютеры, микрокомпьютеры. Разработано программное обеспечение, обеспечивающее довольно широкое использовать технические возможности компьютера. Снижение стоимости компьютерной техники позволило внедрить ее в образовательных учреждениях. Теперь компьютеры пошли в школы, институты и в количественном выражении Компьютеризация образования идет высокими темпами: в отдельных странах число школьных компьютере составляет уже десятки и сотни тысяч, а в США - миллионы. И в нашей стране школьники старших классов уже в течение семи лет изучают такой предмет как информатика, знакомятся с компьютерами и основами работы на них. Однако, обучение с помощью компьютера остается малоэффективным. Основная причина состоит в том, что разработчики автоматизированных обучающих систем преследуют цель компьютеризация обучения ради самой компьютеризацию! Мало внимания уделяется дидактике.

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

В настоящее время уже создано множество средств обучения с помощью компьютера. Их можно квалифицировать следующим образом: компьютерные учебники, предметно-ориентированные среды (микромиры, моделирующие программы, учебные пакеты), лабораторные практикумы, тренажеры, контролирующие программы.

1 НАЗНАЧЕНИЕ ОБУЧАЮЩЕЙ ПРОГРАММЫ

1.1 Обзор существующих обучающих средств и методов

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

Идея обучения с помощью компьютера появилась давно. Первые попытки относятся к концу 50-х годов. В то время уже имелась возможность "общения" человека с компьютером посредством используемого в качестве устройства ввода/вывода телеграфного аппарата-телетайпа. Надлежащим образом запрограммированный компьютер заносит в свою память набираемый человеком на клавиатуре телетайпа текст запроса, а по окончании ввода этого текста производит некоторый анализ его и печатает на телетайпе заранее заготовленный, или конструируемый из подходящих элементов текст ответа. Или проще - компьютер выдает на телетайп текст вопроса или условия задачи и ждет ввода с клавиатуры ответа, который затем сверяется с имеющимся эталоном, чтобы выдать оценку: верно/неверно. С тех пор во всем мире ведутся непрерывные научные поиски решения проблемы эффективного и дешевого способа обучения с помощью компьютера.

Проблему дороговизны попробовали решить в 70-е годы специалисты Иллинойского университета. Их силами была создана поражавшая своими техническими возможностями суперсистема PLATOIY. Каждому учащемуся здесь был предоставлен уже не телетайп, а комфортабельный терминал с плазменным дисплеем, обеспечивающим выдачу произвольного текста, графики и цветных кадров с микрофишей в сопровождении звука. Расчеты на низкую стоимость системы не оправдались и после проведенных испытаний в условиях обучения школьным предметам выявилась сложность, дидактическая неэффективность и трудоемкость подготовки учебных материалов. Создание компьютерных систем обучения приняло широкий размах и в связи с этим говорили о революции в образовании. Но в действительности существенного влияния на практику обучения разрабатываемые системы не оказали, и ни одна из них не получила сколько-нибудь значительного применения: системы создавались сами по себе, а обучение людей производилось с помощью книг и лекций. С появлением массового производства недорогих и удобных в использовании микрокомпьютеров, компьютеризация в настоящее время в количественном выражении идет высокими темпами.

В конце 80-х годов проблемной лабораторией электронных вычислительных машин Московского государственного университета была создана микрокомпьютерная система обучения "Наставник". Эта система предназначена для обучения предметам теоретического характера в вузах, техникумах, профессионально-технических училищах, общеобразовательных школах, центрах подготовки, переподготовки и повышения квалификации кадров на предприятиях. Типовой вариант системы рассчитан на обучение одновременно до 32 учащихся, обслуживаемых одним микрокомпьютером. Система проста и удобна в управлении, не требует специальной подготовки преподавателей и удобна для обучаемых. Все общение с компьютером происходит по подсказкам и контролем с его стороны. В состав аппаратуры системы входит микрокомпьютер общего назначения, дисплей с клавиатурой, гибкий магнитный диск или магнитная лента, принтер, специализированное оборудование для связи учащихся и преподавателя с компьютером, включающее мини терминалы, источники электропитания мини терминалов и контроллер для сопряжения их с микрокомпьютером, систему кабелей. Программное обеспечение системы состоит из пяти частей. Три части, "Обучение", "Экзамен", "Тест" , обеспечивают возможность проведения соответствующих занятий. Существуют еще две служебные подсистемы - подготовки управляющей информации и обработки протоколов. Программное оснащение реализовано и функционирует в диалоговой системе структурированного программирования. ДССП, которая после ее начальной загрузки, обеспечивает всю дальнейшую работу. По вводимым с клавиатуры командам производится дозагрузка требуемой подсистемы и ввод управляющей информации . Далее система работает не обращаясь к внешней памяти. И только в конце занятия согласно вводимым командам производит распечатку и (или) запись в архив протокола. Алгоритмы функционирования основных подсистем разработаны так, что обеспечивают управление обучением и проведение экзаменов или тестов независимо от конкретного содержания учебных материалов, т.е. пригодны для автоматизированных занятий по любым предметам. Работа подсистемы "Обучение" заключается в предоставлении учебных материалов, разбитых на секции, и назначении упражнений по каждому разделу, в случае неверных ответов обучаемому выдается справка, поясняющая суть ошибки и отсылающая к необходимому абзацу инструктивного текста. В отдельных случаяx назначаются дополнительные упражнения. В случае успешного ответа на все вопросы по разделу обучаемый переходит к изучению следующей секции. В случае неверного ответа - возврат в предшествующую секцию или отправка к преподавателю. Подсистемы "Экзамен" и "Тест" предназначены для контроля знаний и умений. В режиме "Экзамен" обучаемый получает от преподавa- теля набор секций, в которых получает определенное преподавателем число упражнений с ограниченным числом попыток ответов. Верные ответы подтверждаются, а неверные отрицаются, однако справки не выдаются. "Тест" отличается от "Экзамена" тем, что каждый учащийся отвечает на все имеющиеся в учебном материале вопросы, причем попытка ответа предоставляется только одна. Ответы не подтверждаются и не отрицаются. Вся работа учащегося протоколируется. Учебно-методическое оснащение наименее фиксировано и наиболее открыто для наращивания и развития. Жестко определены только форматы и правила оформления учебных материалов. Никаких ограничений по тематике и содержанию учебных материалов, равно как и методик или дидактических приемов, кроме необходимости выражаться в форме множественного выбора, нет. Подробнее о микрокомпьютерной системе " Наставник" можно прочитать в [1].

В период с 1991 по 1994 годы Российским НИИ информационных систем по заданию государственного комитета высшей школы России были проведены четыре конкурса "Электронный учебник", В результате этих конкурсов в фонде РосНИИ ИС накоплено более 150 компьютерных обучающих программ готовых к распространению на IBM PC и совместимых с ними. Их классификация и краткая характеристика, применяемых в них методов подробнее приведена в [2] Среди этих программ можно выделить следующие основные группы : инструментальные системы , прикладные пакеты, учебные пакеты. Инструментальные среды предназначены для создания компьютерных обучающих программ. Они сокращают трудоемкость при создании этих программ, то же время дают возможность легко участвовать в разработке программ преподавателям, не являющимся квалифицированными программист ми. Примерами отечественных инструментальных сред могут служить такие системы как "Адонис", "Урок", «Аосмикро», "Сценарий" и др.. Недостатком таких систем является то, что они дорогостоящи. Кроме того, для эффективного применения инструментальных систем необходимо привлечение стабильной группы специалистов, что создает определенные трудности. Обучающие программы могут создаваться на базе прикладных пакетов, которые позволяют преобразовывать математические выражения, производить вычисления, строить графики, обрабатывать экспертные данные и т.п. ... По сравнению с инструментальными средами прикладные пакеты дешевле, более универсальны, доступны широкому кругу пользователей. Альтернативой прикладным пакетам могут служить учебные пакеты.

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

1) компьютерные учебники;

2) предметно-ориентированные среды (микромиры, моделирующие программы, учебные пакеты);

3) лабораторные практикумы;

4) тренажеры;

5) контролирующие программы;

Проблема практического применения ЭВМ в учебном процессе продолжает стоять и сейчас. Важно использовать все новейшие достижения науки и техники для более эффективного обучения школьников, студентов, специалистов самых разных специальностей. На кафедре «математическая кибернетика» Московского Авиационного Института уже много лет ведется разработка подобных приложений. Там были разработаны и используются компьютерные программы по каждой из выше перечисленных групп.

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

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

1.2.1 Выбор технических средств и программного обеспечения

Для реализации данного программного продукта были выбраны языки программирования: Perl, на котором выполнена основная часть программы, обеспечивающая все необходимые расчеты; VRML - язык моделирования виртуальной реальности, обеспечивающий наглядное представление задачи; HTML, обеспечивающий диалог пользователя с компьютером. Эти языки позволяют работать с данной программой из любой точки мира, при наличии компьютера и выхода в мировую сеть Internet, и не зависеть от операционной системы.

Выбор языков VRML и HTML следует из использования языка Perl и возможного использования сети Internet, в то время как Perl удобен для решения любых задач и не зависит от операционной системы сервера (данная программа представляет клиент-серверное приложение). В отличие от языка PHP, который, в принципе удовлетворяет выше перечисленным требованиям, он имеет возможность подключения дополнительных модулей, которых было разработано огромное количество для самых различных целей, например для работы как CGI приложение, а также для работы с графикой и др..

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

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

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

2 Описание программы

2.1 Общие сведения

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

После задания произвольной задачи в окне браузера и отправки, с помощью последнего, этих данных на сервер, CGI-скрипт обрабатывает полученную информацию, т.е. рассчитывает область допустимых решений, и возвращает HTML-документ со ссылкой на трехмерную модель области, которая, в свою очередь, создается вторым CGI-скриптом. Браузер автоматически распознает, что перед ним объект VRML и запускает VRML-браузер, передавая ему ссылку на модель области допустимых решений, и, встраивая его в HTML-документ.

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

Поскольку алгоритм построения связан с расчетом двумерной задачи, то тут же имеется и двумерное графическое решение, в котором диалог пользователь проистекает точно также, только вместо VRML-объекта возвращается картинка (с областью и линией уровня) в формате PNG.

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

При желании, получившийся HTML-документ можно распечатать и использовать в качестве отчета о проделанной лабораторной работе. К сожалению, в VRML-браузере отсутствует возможность печати, видимо из-за того, что виртуальные миры имеют возможность видоизменяться со временем, но это поправимо посредством копирования документа, например, в документ Word и вставкой туда снимка с экрана, как это сделано здесь (см. рисунок выше).

2.2 Используемые технические средства

Первым делом, для работы программы, необходимо серверное программное обеспечение, такое как Apache-сервер для систем Windows или Unix, или Microsoft IIS (Internet Information Server) для системы Windows. А также, интерпретатор языка Perl, и соответствующая настройка сервера и CGI-скриптов.

Помимо серверного необходимо и клиентское программное обеспечение: интернет-браузер и VRML-браузер (для работы с задачами отличными от трехмерного графического решения VRML-браузер не нужен).

Однако возможны более сложные решения. Одно из таких решений используется кафедрой «математическая кибернетика» Московского Авиационного Института. Имеется два сервера. Unix-сервер в роли интернет-сервера (dep805.mai.ru работающий в сети MAI NET) и Windows 2000 server, который также можно было бы использовать как интернет-сервер (он находится во внутри-кафедральной сети, которая, в свою очередь, не маршрутизируется в MAI NET из соображения безопасности). На Windows 2000 server`е установлена терминальная служба, позволяющая работать на машинах, начиная с 286-х компьютеров с видеокартой с памятью 256Kb, под терминалом. Таким образом, обеспечивается большое количество машин (ведь покупка новых машин требует больших финансовых затрат), на которых можно проводить лабораторные практикумы.

2.3 Описание основных алгоритмов

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

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

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

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

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

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

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

Ищем в результате пересечения с каким ограничением получена данная точка. Далее действуем согласно пункту 3, до тех пор, пока не вернемся к первой точке.

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

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

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

Используя полученные данные, остается только построить результирующую модель.

3 Использование программы в процессе обучения

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

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

3.1 Возможности администратора

3.2 Возможности пользователя

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

Язык VRML был разработан специально для работы в сети интернет с трехмерной графикой, а потому, как и обычный HTML-документ требует специальную программу для просмотра. Обычный интернет-браузер понимает только «текстовые» документы, все остальное (графика, анимация, звук) обрабатывают дополнительные программы, подключаемые к нему. Так VRML-браузер подключается к обычному браузеру и работает вместе с ним в «симбиозе». Поскольку VRML-браузер по умолчанию не входит в установку, то его необходимо установить самостоятельно. Существуют три варианта:

Самый простой, если у вас Windows98, открываете "Панель управления", в ней "Установка и удаление программ", на закладке "установка Windows" надо выбрать "Средства интернета", а в ней "Просмотр Microsoft VRML". Ставите на последнем галочку и нажмите везде "OK", при этом вы потеряете 3,5Mb у вас на диске. Как показала практика - это самый неудачный выбор браузера особенно для работы с данной программой, т.к. каждый мир (трехмерная область допустимых решений) создается динамически, и данные о нем передаются через командную строку, то при длине последней, превышающей, приблизительно, 220 символов, выполняет недопустимую ошибку. Возможно с новой версией Internet Explorer`a поставляется исправленный VRML браузер (он поставляется "в нагрузку" с дистрибутивом Internet Explorer`a, из которого, ради экономии места, удаляется распространителями). Это не единственный недостаток браузера от Microsoft, например, при включении аппаратного ускорения или DirectX теряются некоторые свойства объектов, такие как прозрачность.

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

Браузер Cosmo Player фирмы CosmoSoftware. Входит в поставку Netscape Navigator, но существует и отдельно.

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

Страницы: 1, 2, 3