телефон 978-63-62
978 63 62
zadachi.org.ru рефераты курсовые дипломы контрольные сочинения доклады
zadachi.org.ru
Сочинения Доклады Контрольные
Рефераты Курсовые Дипломы
Молочный гриб необходим в каждом доме как источник здоровья и красоты

РАСПРОДАЖАВсё для дома -15% Книги -15% Образование, учебная литература -15%

все разделыраздел:Компьютеры, Программированиеподраздел:Программное обеспечение

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

найти похожие
найти еще

Микро-робот "Нано".
Nano ведет себя словно это настоящее ползающее насекомое: его движения также непредсказуемы и быстры. Благодаря оригинальной конструкции
330 руб
Раздел: Микро-роботы
Светильник-фонтан "Большой".
Светильник-релаксант в виде кружки пива с краном дополнен комнатным мини-фонтаном. Его мягкий свет и тихое журчание успокоят нервную
542 руб
Раздел: Декор, предметы интерьера
Денежное дерево "100$", 55 см.
Настольная композиция в горшочке выполнена в виде миниатюрного денежного дерева. На пластиковое основание дерева насажены купюры-дубли
499 руб
Раздел: Прочее
Министерство науки и образования Украины Днепропетровский Национальный Университет Факультет электроники, телекоммуникаций и компьютерных систем Кафедра автоматизированных систем обработки информацииРасчётная работа №1 Графический метод решения задач линейного программирования Выполнил: ст. гр. РС-05, Паляруш А.Б. Проверил: Доцент кафедры АСОИ Саликов В.А Г. Днепропетровск 2007 г. Постановка задачи Для производства двух видов продукции А и В предприятие использует 4 группы оборудования (1, 2, 3, 4) на производство одной штуки продукции А требуется занять в течение рабочей смены 1, 0, 5 и 3 единиц соответственно 1, 2, 3, 4 оборудования, а на производство одной штуки продукции В требуется 1, 1, 0, 2 единиц оборудования 1, 2, 3, 4. Имеется оборудование по группам 1 – 18, 2 – 12, 3 – 24, 4 – 18 единиц. Предприятие получает с одной штуки продукции А 4 гривны чистого дохода и 6 гривен - с одной штуки продукции В. Сколько штук продукции каждого вида должно производить предприятие, чтобы получить наибольшую прибыль? Группа оборудования, штук для производства единицы продукции Прибыль, грн 1 2 3 4 А 1 0 5 3 4 В 1 1 0 2 6 Построение математической модели Для реализации графического метода решения задач линейного программирования необходимо определить целевую функцию: Z=4 x1 6 x2, где Z при нахождении оптимального решения данной задачи следует помнить, что количество продукции (равно как и количество ресурса) целое число. Z(0,9)=4 0 9 6=54 (грн). Чувствительность модели Благодаря исследованию чувствительности модели, мы получаем информацию о ценности ресурса. Оборудование группы 1 (голубой цвет на графике) не является дефицитным и не влияет на оптимальную точку т.к. вышло далеко за ОДР, его очень много. Это оборудование станет дефицитным при уменьшении его количества на 9 единиц. Оборудование группы 2 (зелёный цвет на графике) так же не является дефицитным, однако, при уменьшении его количества на 3 единицы оно начнёт влиять на результат. Оборудование группы 3 (синий цвет на графике) не дефицитно. Изменяя его количество, при неизменном количестве других ресурсов, мы не повлияем на результат т.к. для производства продукции А (именно она должна производиться для максимальной прибыли) его расход равен 0. Оборудование группы 4 (чёрный цвет на графике) является дефицитным, ценность данного ресурса можно определить, увеличив его количество на 2 единицы (т.к. именно столько необходимо для производства одной единицы продукции А): Следовательно, при изменении количества ресурса 4 на единицу прибыль растёт на 3 гривны. Данный ресурс можно увеличивать до 24 единиц, потом он перестанет быть дефицитным, значит, не будет влиять на оптимальное решение.

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

 Журнал «Компьютерра» 2005 № 31 (603) 30 августа 2005 года

И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян[Как я узнал во время подготовки статьи, 29 апреля 2005 года Леонид Генрихович, в последние годы работавший в США, скоропостижно скончался] (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз. Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно)

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

Графический метод решения задач линейного программирования 1. Область решений линейных неравенств. Пусть задано линейное неравенство с двумя переменными и (1) Если величины и рассматривать как координаты точки плоскости, то совокупность точек плоскости, координаты которых удовлетворяют неравенству (1), называется областью решений данного неравенства. Следовательно, областью решений неравенства (1) является полуплоскость с граничной прямой линией . Пример 1. Найти полуплоскость, определяемую неравенством . Решение. Строим прямую по двум точкам, например, по точкам пересечения с осями координат (0; 4) и (6; 0). Эта линия делит плоскость на две части, т.е. на две полуплоскости. Берем любую точку плоскости, не лежащую на построенной прямой. Если координаты точки удовлетворяют заданному неравенству, то областью решений является та полуплоскость, в которой находится эта точка. Если же получаем неверное числовое неравенство, то областью решений является та полуплоскость, которой эта точка не принадлежит. Обычно для контроля берут точку (0; 0).

Карандаши цветные "Lyra Groove Slim", 12 цветов + точилка.
Карандаши с эргономичным захватом по всей длине. Диаметр грифеля 3,3 мм! Точилка. Уникальные карандаши с канавками! Запатентовано! Научите
338 руб
Раздел: 7-12 цветов
Крем для профилактики и коррекции растяжек "Avent", 200 мл.
Крем используется до и после родов. Повышает эластичность кожи благодаря экстрактам морского латука и водорослей. Смягчает и питает кожу
930 руб
Раздел: Косметика, гигиена для мам
Глобус политический Rotondo, 250 мм.
Глобус является уменьшенной и практически не искаженной моделью Земли и предназначен для использования в качестве наглядного
731 руб
Раздел: Глобусы
 Большая Советская Энциклопедия (СТ)

Вытекающие отсюда уравнения, которым должны удовлетворять действующие на тело силы при равновесии, см. в ст. Равновесие механической системы . Равновесие системы тел изучают, составляя уравнения равновесия для каждого тела в отдельности и учитывая закон равенства действия и противодействия. Если общее число реакций связей окажется больше числа уравнений, содержащих эти реакции, то соответствующая система тел является статически неопределимой; для изучения её равновесия надо учесть деформации тел.   Графические методы решения задач С. основываются на построении многоугольника сил и верёвочного многоугольника .   Лит.: Пуансо Л., Начала статики, П., 1920; Жуковский Н. Е., Теоретическая механика, 2 изд., М. — Л., 1952; Воронков И. М., Курс теоретической механики, 9 изд., М., 1961; Тарг С. М., Краткий курс теоретической механики, 9 изд., М., 1974; см. также лит. при ст. Механика .   С. М. Тарг. Статика механизмов Ста'тика механи'змов, раздел машин и механизмов теории , в котором рассматриваются методы определения реакций элементов кинематических пар при условии, что силами инерции звеньев механизма можно пренебречь

скачать реферат Решение задачи линейного программирования графическим методом

Министерство образования Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Пояснительная записка к курсовому проекту по дисциплине «СПЕЦКУРС-3. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ» Вариант №3 28 марта 2008 г. ТОМСК 2008 Содержание. ВВЕДЕНИЕ 3 1. ПОСТАНОВКА ЗАДАЧИ 6 Математическое программирование 6 1.2 Кратко о линейном программировании 6 1.3 Основная задача линейного программирования 8 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 10 2.1 Теоретическое введение 10 2.2 Методика решения задач ЛП графическим методом 12 3.ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ 13 3.1 Экономическая постановка задачи линейного программирования 13 3.2 Построение математической модели 14 3.3 Нахождение оптимального решения задачи с помощью линейного метода. 16 4. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 18 4.1 Теоретическое введение 18 4.2 Методика графического анализа чувствительности оптимального решения 19 4.2.1 Первая задача анализа на чувствительность (анализ на чувствительность к правой части ограничений) 19 4.2.2 Вторая задача анализа на чувствительность (увеличение запаса какого из ресурсов наиболее выгодно) 25 4.2.3 Третья задача анализа на чувствительность (в каких пределах допустимо изменение коэффициентов целевой функции) 26 ЗАКЛЮЧЕНИЕ 30 Список литературы 32 ВВЕДЕНИЕ Исследование операций – это математическая дисциплина, занимающаяся разработкой и применением методов нахождения наилучших решений в различных областях человеческой деятельности. Термин , Томск-2002. Алесинская Т.В. - Задачи по исследованию операций с решениями. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие. Кононов В.А. - Исследование операций.

 Большая Советская Энциклопедия (ИГ)

Существенно, что различные применяемые в И. т. принципы оптимальности могут противоречить друг другу.   Теоремы существования в И. т. доказываются преимущественно теми же неконструктивными средствами, что и в других разделах математики: при помощи теорем о неподвижной точке, о выделении из бесконечной последовательности сходящейся подпоследовательности и т. п., или же, в весьма узких случаях, путём интуитивного указания вида решения и последующего нахождения решения в этом виде.   Фактическое решение некоторых классов антагонистических игр сводится к решению дифференциальных и интегральных уравнений, а матричных игр — к решению стандартной задачи линейного программирования. Разрабатываются приближённые и численные методы решения игр. Для многих игр оптимальными оказываются так называемые смешанные стратегии, тоесть стратегии, выбираемые случайно (например, по жребию).   И. т., созданная для математического решения задач экономического и социального происхождения, не может в целом сводиться к классическим математическим теориям, созданным для решения физических и технических задач

скачать реферат Линейное программирование: постановка задач и графическое решение

Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.6) - (1.7) 3; тогда каждое неравенство определяет полупространство -мерного пространства с граничной гиперплоскостью ai1x1 ai2x2 ai x = bi (i = 1, 2, ., m), а условия неотрицательности – полупространства с граничными гиперплоскостями хj 0 (j = 1, 2, ., ). Если система ограничений совместна, то по аналогии с трехмерным пространством она образует общую часть -мерного пространства, называемую многогранником решений, так как координаты каждой его точки являются решением. Таким образом, геометрически задача линейного программирования представляет собой отыскание такой точки многогранника решений, координаты которой доставляют линейной функции минимальное значение, причем допустимыми решениями служат все точки многогранника решений. 2. Графический метод решения задачи линейного программирования. 1. Область применения. Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного простран6тва, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств.

скачать реферат Экзаменационные билеты по методам оптимизации за весенний семестр 2001 года

Классификация методов многомерного поиска экстремума. 51) Градиентный метод поиска экстремума для функции нескольких переменных. 52) Метод покоординатного спуска поиска экстремума для функции нескольких переменных. 53) Метод наискорейшего спуска поиска экстремума для функции нескольких переменных. 54) Метод Ньютона поиска нулей функции. Запишите итерационную формулу метода Ньютона. Покажите графически, как происходит процесс приближения к корню. 55) Метод секущих поиска нулей функции. Покажите графически, как происходит процесс приближения к корню. 56) Овражный метод поиска экстремума. В каких случаях он применяется? 57) Специфика задач по отысканию экстремума функции в условиях помех. 58) Метод стохастической аппроксимации нахождения экстремума в условиях помех. Выбор коэффициента коррекции. 59) Математическая формулировка задачи линейного программирования. 60) Приведите примеры (не менее 3) задач линейного программирования. 61) Геометрическая интерпретация задачи линейного программирования. 62) Понятие «симплекс-метода решения задач линейного программирования». 63) Понятие «выпуклой области» в задачах линейного программирования.

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

Оптимальное решение отыскивается среди решений, принадлежащих данной области(рис. 1.3). 4) Система ограничений имеет бесчисленное множество решений (рис. 1.4). Рис. 1.1 Рис. 1.2 Рис. 1.3 Рис. 1.4 C a b Рис. 2 Симплекс – метод. Решение задачи линейного программирования включает в себя 3 этапа: 1) Отыскание базисного решения – некой точки А (рис. 2) лежащей на функции. 2) Отыскание опорного решения – некой точки B (рис. 2) принадлежащей области, образованной ограничениями. 3) Отыскание оптимального решения – некой точки С (рис. 2) принадлежащей той – же области, и в которой целевая функция достигает своего экстремума. Отыскание оптимального решения с использованием симплекс – метода сводится к последовательному направленному перебору вершин многогранника, образованного ограничениями при котором монотонно увеличивается (уменьшается) значение целевой функции. В настоящее время решение задач ЛП с помощью симплекс – метода реализуется с помощью ЭВМ. Решение задачи методом линейного программирования. Симплекс – метод. Определить плановое задание добывающим предприятиям, если в работе находится =12 составов.

скачать реферат Анализ экономических задач симплексным методом

Что же касается избыточного ресурса , то увеличение его запаса не приведет к росту выручки, поскольку . Из приведенных рассуждений следует, что оценки ресурсов позволяют совершенствовать план выпуска продукции. Выясним экономический смысл оценок . По оптимальному плану . Оценки этих видов продукции равны нулю. Что это означает, практически станет ясно, если представить оценки в развернутой записи: Таким образом, нулевая оценка показывает, что эта продукция является неубыточной, поскольку оценка ресурсов, расходуемых на выпуск единицы такой продукции, совпадает с оценкой единицы изготовленной продукции. Что же касается продукции являющейся, как установлено выше, убыточной, а потому и не вошедшей в оптимальный план, то для ее оценок Отсюда видно, что оценка убыточной продукции показывает, насколько будет снижать каждая единица такой продукции достигнутый оптимальный уровень. §8. Программа и расчеты.{Программа составлена для решения задачи линейного программирования симплексным методом} uses cr ; co s =2;{число неизвестных исходной задачи} m=3;{число ограничений} m1=0;{последняя строка равенств} m2=1;{последняя строка неравенств вида >=} label 5,15,20,10; var b,cb:array of real;a:array of real; s0,max,mb,s1:real;i,j,k,i0,j0,m21, m1, 1:i eger; Bi:array of i eger; begi clrscr; wri el ; wri el (' Симплексный метод решения задачи линейного программирования:'); wri el ; wri el (' Проведем некоторые преобразования с данной задачей:'); wri el ; wri el (' Подготовьте матрицу: сначала равенства, потом неравенства вида >= и неравенства вида =} for i:=m1 1 o m2 do a:=-1; {переход к равенствам в неравенствах max he begi max:=e; j0:=i e d; {получили столбец с максимальной оценкой} if max0 he begi wri el (' Пустое множество планов'); go o 20 e d; for i:=1 o do wri el (' x:7:4); 20:readkey e d.

Мозаика из пайеток "Лошадь".
Предназначение: для детского творчества и игровых целей. Размеры: 280х30х380 мм.
491 руб
Раздел: Аппликации с бисером, пайетками
Пазл 3000 элементов. Всадница.
Russian Museum Collection - это собрание шедевров живописи всемирно известных русских и европейских художников из коллекций крупнейших
807 руб
Раздел: Пазлы (2000 и более элементов)
Набор "Буквы на магнитах", 52 деревянных элемента.
Для детей от 3-х лет и старше. Набор букв прекрасно подходит для обучения грамматике детей дома, в детском саду или школе. Игра формирует
517 руб
Раздел: Кассы букв и цифр (без магнита)
скачать реферат История ЭММ

В связи с этим нам представляется более целесообразным говорить об истории не экономико- математических методов, а экономико-математических исследований, понимая под ними такие экономические разработки, в которых использовалась математика. Под применением математики в экономических исследованиях в этой работе мы понимаем в основном постановку, анализ и использование экономико- математических моделей. 4. РАЗВИТИЕ МММ В 20-50е ГОДЫ: ЗА И ПРОТИВ. Советской науке принадлежит приоритет в решении многих важнейших вопросов теории и практического применения экономико-математических методов. В первую очередь это относится к разработке балансовых методов анализа экономики. Первый баланс народного хозяйства был составлен ЦСУ СССР за 1923/24 хозяйственный год. Он на многие годы опередил аналогичные работы за рубежом. В 1939 г. Л.В. Канторовичем впервые был разработан метод решения задач линейного программирования, охватывающих множество хозяйственных ситуаций, в которых возникает проблема наилучшего использования ограниченных ресурсов.

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

Если целевая функция достигает экстремального значения более чем на одной вершине, то она достигает того же значения в любой точке, являющейся выпуклой комбинацией этих вершин (альтернативный оптимум). Эта теорема имеет важнейшие значение, так как она указывает путь решения задачи линейного программирования. Совсем не надо перебирать все точки допустимой области. Достаточно перебрать вершины допустимой области, а ведь их конечное число. Кроме того, не нужно перебирать все вершины, можно этот перебор существенно сократить. Любой набор чисел , удовлетворяющий ограничениям задачи, называют планом, а множество всех планов допустимой областью. Тот план, который доставляет экстремум (минимум или максимум) целевой функции, называют оптимальным планом или просто решением задачи линейного программирования. Задачи линейного программирования решаются несколькими методами: 1. графический метод; 2. симплексный метод; 3. двойственность в ЛП; 4.двойственный симплексный метод. Задачи линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение невозможно.

скачать реферат Построение экономической модели c использованием симплекс-метода

Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух видов рекламы . X1=>0 , X2=>0 , Z=>0 ; Max Z = X1 25X2 ; 5X1 100X2 0 Использование графического способа удобно только при решении задач ЛП с двумя переменными . При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом . Информация , которую можно получить с помощью симплекс-метода , не ограничивается лишь оптимальными значениями переменных . Симплекс-метод фактически позволяет дать экономическую интерепритацию полученного решения и провести анализ модели на чувствительность . Процесс решения задачи линейного программирования носит итерационный характер : однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор , пока не будет получено оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования .

скачать реферат Линейное программирование: решение задач графическим способом

Министерство Образования Российской Федерации Тюменский Государственный Нефтегазовый Университет филиал в городе Ишиме Курсовая работа по программированию на тему: Линейное программирование: решение задач графическим методом Выполнил: студент 1 курса АиУ-02. Афанасьев В. Ю. Проверил: Андреенко О.В. Дата сдачи « » июня 2003г. Оценка Подпись Ишим 2003 Содержание: Выполнил: студент 1 курса1 Подпись 1 Ишим 20031 Введение3 Гл 1Математические основы решения задачи линейного программирования графическим способом 4 1.1 Математический аппарат4 1.2 Геометрическая интерпретация задачи линейного программирования.5 1.3 Этапы решения графического метода задач линейного программирования7 Гл 2 Решение задач линейного программирования графическим способом на ЭВМ15 2.1 Описание работы программы15 2.1 Текст программы20 Заключение29 Литература31 Рецензия33 Введение Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения.

скачать реферат Симплекс метод в форме презентации

Для решения задач данного типа применяются методы: 1) графический; 2) табличный (прямой, простой) симплекс - метод; 3) метод искусственного базиса; 4) модифицированный симплекс - метод; 5) двойственный симплекс - метод. Графический метод Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции задачи. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой.

Пароходик, 22 см.
Главное достоинство подушки - это осязательный массаж, приятный, полезный и антидепрессивный. Внешний материал - гладкий, эластичный и
305 руб
Раздел: Подушки
Точилка механическая "Energy".
Роликовый нож. Прочный металлический корпус. Размер - 12х7х7 см.
643 руб
Раздел: Точилки
Бусы "Фрукты" (60 деталей).
На разноцветных крупных бусинах нанесены изображения различных фруктов. К набору бус приложены шнурки с наконечниками для удобства
409 руб
Раздел: Бусины
скачать реферат Решение оптимизационной задачи линейного программирования

Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций. Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике. Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода. В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное програмное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов.

скачать реферат Решение задач линейного программирования

При этом для решения задачи линейного программирования необходимо иметь базис, т.е. набор переменных хi, в количестве, равным числу основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множитель аij = 1. Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексы хm 1, xm 2 и т.д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплекс-метод). Мы не будем рассматривать задачи, относящиеся к модифицированному симплекс-методу. Для практической рабо-ты по нахождению решения задачи линейного программирования (по варианту простого симплекс-метода) будут использоваться алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оце-нок, позволяющих делать переходы от одного шага к другому, а также показы- вающих, когда итерационный процесс остановится и результат будет найден.

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

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным. Итак, процесс нахождения решения задачи целочисленного программирования (1)- (4) методом ветвей и границ включает следующие основные этапы: 1°. Находят решение задачи линейного программирования (1)-(3). 2°. Составляют дополнительные ограничения для одной из пере-менных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом. 3°. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений. 4°. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение.

скачать реферат Транспортная задача линейного программирования

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

телефон 978-63-62978 63 62

Сайт zadachi.org.ru это сборник рефератов предназначен для студентов учебных заведений и школьников