Как стать высококвалифицированным специалистом? Реферат математика в программировании

Доклад : Программирование для математиков

Программирование для математиков

Наталья Дубова

В 1980 году на мехмате МГУ был введен новый курс программирования

Вместе с появлением первых вычислительных машин возникла потребность в фундаментальной подготовке тех, кто научит этих электрических монстров осмысленной деятельности, то есть программистов. На мехмате МГУ в начале 50-х Алексей Андреевич Ляпунов читал первый учебный курс по принципам программирования. В 1980 году здесь же возникает новый курс программирования, который в конечном итоге оказал серьезное влияние не только на несколько поколений «мехматян», но и в целом на преподавание информатики в стране.

В заголовок статьи мы вынесли название учебника по мехматскому курсу программирования, который вышел восемью годами позже. Авторы курса Геннадий Викторович Лебедев и Анатолий Георгиевич Кушниренко подчеркивают, что название это отражало не просто принадлежность предмета главному математическому факультету страны. К 80-м стало очевидно, что мехмат, проложивший дорогу преподаванию теоретического программирования, уже не имеет соответствующего его высокой научной планке курса по этому предмету. Преподавание программирования сводилось к изложению Фортрана — языка, авторитет которого в сфере научных расчетов был непререкаем, и описанию архитектуры машин IBM 360, с которых делались наши ЕС ЭВМ. Качество этих курсов никак не отвечало мехматским требованиям. Вызревала потребность в абсолютно новом курсе, способном внести вклад в общую математическую культуру студентов.

Теперь его авторы уверены, что в итоге, когда курс окончательно сформировался, им удалось достигнуть этой цели. Правда, накануне 1 сентября 1980 года такие глобальные идеи не формулировались. Просто молодые преподаватели решили, что каждый студент, пришедший на первое занятие по программированию, должен уйти с него с распечаткой готовой программы. Для этого решили написать пакет программ с использованием библиотек системы «Асфор» — сокращенной версии Фортрана, разработанной на мехмате специально для программирования студенческих задач. Студенты должны были построить алгоритм передвижения некого «путника» через заданный набор препятствий и составить программу, состоящую только из вызовов стандартных программ. Дальше оставалось только собрать нужные перфокарты с набитыми на них программами, запустить их обработку и получить результат.

После нескольких дней борьбы с библиотеками на Фортране создать такой пакет программ не удалось.

«В последнюю ночь в полном отчаянии и от безысходности в голове родилась шальная мысль, что Фортран здесь не нужен. Надо написать интерпретатор. С этой идеи и стартовал мехматский курс», — вспоминает Лебедев. За два часа был написан интерпретатор, обрабатывающий линейные операторы вновь придуманного языка с русской лексикой. Первое занятие прошло с полным успехом. Вся группа ушла с выполненными программами и уже приобретенным опытом исправления типовых ошибок. В прежних курсах студенты получали первые результаты не раньше чем через два-три месяца освоения языка.

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

По образному выражению авторов курса, в его основе лежат «три кита», которые призваны помочь студенту приобрести навыки грамотного программирования систем объемом в несколько тысяч строк. Это понятие исполнителя, технология «сверху вниз» и развитые структуры данных. Первое понятие, придуманное Владимиром Борисовичем Бетелиным, создатели курса сами освоили при решении вполне конкретных задач и обнаружили, что с его помощью можно с успехом строить самые большие и сложные системы. Фактически исполнитель — пакет программ, работающих над общими данными, — предшественник объектно-ориентированного программирования, экземпляр класса в современной терминологии.

Два других кита — технология программирования «сверху вниз», cхематическое изображение которой вынесено на обложку учебника, и иерархия структур данных с описанием методов реализации одних структур на базе других — важнейшие компоненты, без которых не обходится программист-практик. Мехматский курс программирования действительно закладывал базу для грамотной разработки сложных систем. Однако только изложение важных понятий, не подкрепленное практикой, мало что дало бы студентам. Поэтому в курсе предлагалось разобраться с несколькими законченными проектами (построение выпуклой оболочки, реализация компилятора с языка арифметических формул, построение изображения полиэдра) и, что самое главное, модифицировать эти проекты, то есть, изучив 6-8 тыс. строк эталонных программ, добавить тысячу-другую своих. Так студент на практике закреплял полученные теоретические знания и одновременно готовился к реальной работе. Ведь в жизни часто все так и происходит — решение задачи сводится к модификации готовых программных систем.

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

Опасения эти были безосновательны. Новая постановка преподавания программирования на мехмате не мешала изучению классических математических дисциплин. Оказалось, что сильные студенты вполне способны увлечься таким «приземленным» занятием, как программирование, найдя его интересным и своевременным. Создатели курса вложили в него всю свою энергию, увлеченность и талант. «Мы были довольно яркие ребята и делали курс с большим вкусом и интересом», — вспоминает с присущим ему юмором Кушниренко. К середине 80-х на курсе программирования для математиков была взращена группа молодых специалистов, которая вместе с ветеранами составила элиту факультетского программистского сообщества.

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

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.osp.ru

topref.ru

Реферат - Математические программирование - Математика

ЛАБОРАТОРНАЯ РАБОТА №2

по мат.программированию

«Графический и симплексный методы решения ОЗЛП»

Для изготовления 2-х различных изделий А и В используется 3 вида сырья. На производство единицы изделия А требуется затратить сырья 1-го вида а1 кг, сырья 2-го вида – а2 кг, сырья 3-го вида – а3 кг. На производство единицы изделия В требуется затратить сырья 1-го вида в1 кг, сырья 2-го вида – в2 кг, сырья 3-го вида – в3 кг. Производство обеспечено сырьём 1-го вида в количестве Р1 кг, сырьём 2-го вида в количестве Р2 кг, сырьём 3-го вида в количестве Р3 кг. Прибыль от реализации единицы готового изделия А составляет ден.ед., а изделия В –ден.ед.

Математическая модель задачи

Обозначим количество произведенной продукции 1-го вида через х1, 2-го вида – х2. Тогда линейная функция примет вид: Z (х1, х2) =2*х1+4*х2.

Это есть цена произведенной продукции. Наше решение должно обеспечить максимальное значение этой функции.

Условие налагает на величины х1 и х2 ограничения следующего вида:

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

Графическое решение задачи

Построим многоугольник решений. Для этого в системе координат х1Ох2 на плоскости изобразим граничные прямые

Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Многоугольником решений данной задачи является треугольник АОВ. Для построения прямой 2*х1+4*х2=0 строим радиус-вектор N =(2;4)=2.5*(2;4)=(5;10) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z =0 перемещаем параллельно самой себе в направлении вектора N. Опорной по отношению к многоугольнику решений эта прямая становится в точке А (0;42,5), где функция Z принимает максимальное значение.

Оптимальный план задачи: х1=0; х2=42,5.

Подставляя значения х1 и х2 в линейную функцию, получаем Zmax =2*0+4*42.5=170 у.е.

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

Решение задачи симплексным методом

Запишем систему в векторной форме

С…1*Рђ1+С…2*Рђ2+С…3*Рђ3+С…4*Рђ4+С…5*Рђ5=РђРѕ, РіРґРµ

Составляем симплексную таблицу.

Среди полученных оценок имеются две отрицательные: Z1-C1=-2<0 и Z2-C2=-4<0. Это означает, что первоначальный опорный план не является оптимальным и его можно улучшить, включив в базис вектор, которому соответствует максимальное по модулю отрицательное число в m+1 строке. Разрешающий вектор-столбец А2. Разрешающий элемент находим по минимальному симплексному отношению. Разрешающий элемент – число 10.

Составим вторую симплексную таблицу.

Просмотрев m+1 строку, убеждаемся, что опорный план – оптимален.

Оптимальный план предусматривает изготовление 42,5 ед.изделия В и не предусматривает изготовление изделий А. Изготовление изделий А привело бы к уменьшению прибыли на 2,4 у.е. Сырье 1-го вида используется полностью. Неиспользованными остается 450-237,5=212,5 тонн 2-го вида и 550-295=255 тонн 3-го вида сырья. Максимальная прибыль составляет 170 у.е.

Решение задачи на компьютере

Выполним следующие действия:

– В ячейку А1 вводим формулу для целевой функции=2*х1+4*х2

– В ячейку А3 вводим формулу для ограничения: =11*с1+10*с2.

– В ячейку А4 вводим формулу для ограничения: =7*с1+5*с2.

– В ячейку А3 вводим формулу для ограничения: =8*с1+6*с2.

– В ячейку С1: С2 вводим начальные значения переменных (0:0).

–Выполним команду Сервис > Поиск решения.

Следовательно, план выпуска продукции, включающий изготовление 42,5 изделий В является оптимальным. При данном плане выпуска изделий полностью используется сырье 1-го вида и остаётся неиспользованным 450-237,5=212,5 тонн 2-го вида и 550-295=255 тонн 3-го вида сырья, а стоимость производимой продукции равна 170 у.е.

ЛАБОРАТОРНАЯ РАБОТА №3

по мат.программированию

«Транспортная задача»

Имеются 3 пункта поставки однородного груза А1, А2, А3 и 5 пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1-А3 находится груз соответственно в количестве а1-а3 тонн. В пункты В1-В5 требуется доставить соответственно в1-в5 тонн груза. Стоимости перевозок 1 тонны груза между пунктами поставки и пунктами потребления приведены в матрице D. Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты по перевозкам были минимальными.

Математическая модель задачи

Математическая модель транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений

при которых целевая функция

F=12*x11+10*x12+15*x13+12*x14+13*x15+16*x21+14*x22+17*x23+10*x24+8*x25+15*x31+10*x32+13*x33+14*x34+15*x35

принимает минимальное значение.

Опорный план найдем методом северо-западного угла.

Для проверки плана на оптимальность необходимо построить систему потенциалов. Для построения системы потенциалов используем условие Ui+Vj=Cij

Все незанятые клетки удовлетворяют условию Ui+Vj<=Cij.

Общая стоимость плана составляет

S=100*12+40*10+12*160+13*50+8*150+10*80+13*200=8770 Сѓ.Рµ.

Решение задачи на компьютере

www.ronl.ru

ФПМИ: зачем программисту математика?

По всем официальным и неофициальным рейтингам одними из наиболее востребованных на рынке труда являются специальности, связанные с IT-технологиями (специалисты в области информационных и вычислительных технологий компьютерной обработки данных). Согласно последним исследованиям, проведенным Международным Институтом Открытых Технологий, потребность в специалистах в области вычислительных и информационных технологий ежегодно возрастает на 36%. Профессия программиста, некогда являвшаяся привилегией избранных, становится все более массовой и востребованной. Отсюда и интерес к этой профессии, зачастую окутанной мифами и легендами, что делает ее еще более привлекательной. С другой стороны, программист программисту рознь. В области IT-технологий растет конкуренция, все большее значение приобретает не то, имеешь ли ты диплом специалиста в области IT-технологий, а уровень твоих знаний и навыков.

Подготовку специалистов на ФПМИ осуществляют две выпускающие кафедры – прикладной математики и программных систем и баз данных – и две специальные – параллельных вычислительных технологий и вычислительных технологий.

Глядя на приведенный перечень выпускающих кафедр, возникает вопрос: кого же готовит факультет Прикладной математики и информатики? Математиков или программистов? И насколько справедливо сложившееся мнение (или заблуждение), что “на ФПМИ слишком много математики”? Попробуем в этом разобраться.

Начнем с того, что сегодня термин “программист” имеет широкое многозначное толкование равно,  как и сама отрасль программирования. Специализации программистов (а точнее специальности IT-технологий) множатся и развиваются, программист, специализирующийся в одной области приложений, зачастую уже слабо понимает своего коллегу, работающего в другой области. Хотя вроде бы и языки программирования, и технологии одни и те же. Дело в том, что сами области приложений могут кардинально отличаться друг от друга, и для того, чтобы писать специализированные программы, мало знать языки и технологии программирования, нужно хорошо разбираться в той области, для которой пишется программный продукт. А для этого нужно иметь достоверную непротиворечивую модель (чаще всего математическую, но возможно и какую-либо другую – инфологическую, семантическую) той предметной области, которую Вы собираетесь исследовать или автоматизировать. У К. Маркса есть замечательные строки, что “самый плохой архитектор (читай – разработчик программ) отличается от самой хорошей пчелы, строящей соты, тем, что у него, в отличие от пчелы, в голове есть проект, план им создаваемого …”. Построение этой модели – самый важный этап разработки программного продукта, требующий не только высочайшего интеллекта, но и очень серьезного образования. Он включает анализ и исследование широкого спектра алгоритмов и математических методов, выбор наиболее приемлемых альтернатив, построение, анализ и алгоритмизацию модели, выбор и использование адекватных программных средств и технологий. Все это невозможно без основательной базовой математической подготовки, являющейся фундаментом для специалиста в области IT-технологий. Поэтому подчас вызывает умиление вид начинающего горе-программиста, который, получив сложную задачу, бросается к компьютеру и начинает “из головы” писать программу. Почему-то ни у кого не вызывает сомнения, что перед тем, как строить многоэтажный дом или разрабатывать сложное инженерное техническое сооружение, необходимо подготовить проект (и не один) того, что Вы собираетесь создавать. Конечно, каждая из специализаций IT-технологий требует глубоких познаний в соответствующих областях, но эти познания не принесут ожидаемых дивидендов без фундаментальной базовой математической подготовки.

Наш факультет не готовит “узких” специалистов в  какой-то области знаний. Основная цель – подготовка специалистов, обладающих фундаментальными знаниями в области компьютерных технологий (computer science, computer science and engineering, information system  и аналогичных).

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

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

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

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

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

Последние десятилетия характеризуются тем, что во многих областях человеческой деятельности обновление фундаментальных знаний осуществляется за счет интенсивного использования математического моделирования. Физическая реализация экспериментов, экспериментальная проверка выдвинутых гипотез являются очень дорогостоящими, как правило, требуют значительных человеческих и материальных ресурсов. А имитация экспериментов на математических моделях, выявление закономерностей в ходе многократного моделирования оказывается на порядки дешевле. Не случайно наиболее весомые результаты в различных научных направлениях (в математике, физике, геофизике, химии, технике, технологиях, экономике, управлении …) получены благодаря эффективному применению методов математического моделирования. Если быть более точным, эти результаты получены с при­менением соответствующего программного обеспечения, реализующего матема­тическую модель объекта и математические методы, позволяющие найти решение, причем оптимальное. И если мы заменяем физический эксперимент математическим, то должны быть уверены в том, что их результаты совпадают, что математическая модель адекватна “физическому” объекту. И как тут специалисту по IT-технологиям обойтись без глубоких математических знаний и вычислительных методов?

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

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

Примечательно, что выпускники ФПМИ легко адаптируются в любой прикладной области, в том числе, в гуманитарных и экономических областях, быстро добиваясь успехов благодаря основательной фундаментальной подготовке и подготовке в области IT-технологий.

ami.nstu.ru

Курсовая работа - Математические модели в экономике и программировании

1. Детерминированные и вероятностные математические модели в экономике. Преимущества и недостатки

Методы исследования экономических процессов базируются на использовании математических — детерминированных и вероятностных — моделей, представляющих изучаемый процесс, систему или вид деятельности. Такие модели дают количественную характеристику проблемы и служат основой для принятия управленческого решения при поисках оптимального варианта. Насколько обоснованы эти решения, являются ли они лучшими из возможных, учтены ли и взвешены все факторы, определяющие оптимальное решение, каков критерий, позволяющий определить, что данное решение действительно наилучшее, — таков круг вопросов, имеющих большое значение для руководителей производства, и ответ на которые можно найти с помощью методов исследования операций [Чесноков С. В. Детерминационный анализ социально-экономических данных. — М.: Наука, 1982, стр. 45].

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

По этим причинам часто, говоря о математическом моделировании экономических процессов, имеют в виду именно вероятностные модели.

Опишем каждый из типов математических моделей.

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

Вероятностные математические модели принципиально отличаются от детерминированных тем, что в вероятностных моделях взаимосвязь между факторами и результирующим признаком вероятностная (стохастическая): при функциональной зависимости (детерминированные модели) одному и тому же состоянию факторов соответствует единственное состояние результирующего признака, тогда как в вероятностных моделях одному и тому же состоянию факторов соответствует целое множество состояний результирующего признака [Толстова Ю. Н. Логика математического анализа экономических процессов. — М.: Наука, 2001, с. 32-33].

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

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

2. Постановка задачи линейного программирования на примере задачи о пищевом рационе

Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок; позволяющего минимизировать суммарной километраж, была дана в работе советского экономиста А. Н. Толстого в 1930 году.

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

Задача линейного программирования состоит в максимизации (минимизации) линейной функции.

, РіРґРµ

при ограничениях

(*)

причем все

Замечание. Неравенства могут быть и противоположного смысла. Умножением соответствующих неравенств на (-1) можно всегда получить систему вида (*).

Если число переменных системы ограничений и целевой функции в математической модели задачи равно 2, то её можно решить графически.

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

Обратимся к одному из неравенств системы ограничений.

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

Замечание 2. Если , то проще взять точку (0;0).

Условия неотрицательности также определяют полуплоскости соответственно с пограничными прямыми . Будем считать, что система неравенств совместна, тогда полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты которых являются решением данной системы — это множество допустимых решений. Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, лучом, многоугольником, неограниченной многоугольной областью. Таким образом, задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху (снизу). При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим прямую (где h — некоторая постоянная). Чаще всего берется прямая . Остается выяснить направление движения данной прямой. Это направление определяется градиентом (антиградиентом) целевой функции.

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

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

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

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

Находят полуплоскости, определяемые каждым из ограничений задачи.

Находят многоугольник решений.

Строят вектор .

Строят прямую .

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

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

Задача о рациональном питании (задача о пищевом рационе)

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

Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1, П2, П3, П4; стоимость единицы каждого продукта равна соответственно С1, С2, С3, С4. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков — не менее b1 единиц; углеводов — не менее b2 единиц; жиров — не менее b3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где aij (i=1,2,3,4; j=1,2,3) — какие-то определённые числа; первый индекс указывает номер продукта, второй — номер элемента (белки, углеводы, жиры).

Требуется составить такой пищевой рацион (т. е. назначить количества продуктов П1, П2, П3, П4, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Математическая модель

Обозначим x1, x2, x3, x4 количества продуктов П1, П2, П3, П4, входящих в рацион. Показатель эффективности, который требуется минимизировать, — стоимость рациона (обозначим её L): она линейно зависит от элементов решения x1, x2, x3, x4.

Целевая функция:

Система ограничений:

a11x1+a21x2+a31x3+a41x4 больше или равно b1

a12x1+a22x2+a32x3+a42x4 больше или равно b2

a13x1+a23x2+a32x3+a43x4 больше или равно b3

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x1, x2, x3, x4.

Таким образом, поставленная задача сводится к следующему: найти такие неотрицательные значения переменных x1, x2, x3, x4, чтобы они удовлетворяли ограничениям — неравенствам и одновременно обращали в минимум линейную функцию этих переменных:

Список литературы

Гончаров В. В. Важнейшие понятия и концепции в современном управлении. — М.: МНИИПУ, 2002, 341 с.

История экономических учений. // Под ред. Н. А. Хохлова. — СПб: Питер, 2002, 324 с.

Казаков А. П., Минаев Н. В. Экономика. Курс лекций. Упражнения. Тесты и тренинги. — М.: Изд-во ЦИПКК АП, 1999, 359 с.

Макроэкономика. Учебное пособие. // Под ред. А. М. Бункина. — М.: Инфра-М, 1995, 337 с.

Нуриев, Розанова. Поведение потребителя в рыночной экономике. // Вопросы экономики, 2003, № 1, с. 4-9.

Социально-экономическая статистика. // Под ред. Г. Л. Громыко. — М.: Изд-во МГУ, 1999, 350 с.

Толстова Ю. Н. Логика математического анализа экономических процессов. — М.: Наука, 2001, 160 с.

Ховард К., Эриашвили Н. Д., Никитин А. М. Экономическая теория. — М, 2000, 564 с.

Чесноков С. В. Детерминационный анализ социально-экономических данных. — М.: Наука, 1982, 259 с.

www.ronl.ru

Смотрите также

• 
  Современные психологические направления реферат
• 
  Реферат фукуяма конец истории
• 
  Реферат страхование в германии
• 
  Реферат на тему мольер
• 
  Реферат материнство и здоровье
• 
  Реферат загрязнение водных ресурсов
• 
  Диалектический материализм маркса реферат
• 
  Экологические проблемы атмосферы реферат
• 
  Эволюция нервной системы реферат
• 
  Создание рекламного текста реферат
• 
  Реферат языковой облик газеты