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

Размещено на http://www.allbest.ru/

КУРСОВОЙ ПРОЕКТ

По предмету: «Моделирование производственных и экономических процессов»

На тему: «Использование линейного программирования для решения задач оптимизации»

Семей-2013г.



СОДЕРЖАНИЕ

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ

ВВЕДЕНИЕ

1. ИСПОЛЬЗОВАНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

1.1 Общая задача оптимизации

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

2. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

2.2 Двойственная задача линейного программирования

3. ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1 Приведение задачи к стандартной форме

3.2 Построение искусственного базиса

3.3 Первый этап двухэтапного симплекс-метода

3.4 Второй этап двухэтапного симплекс-метода

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ



ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ

По дисциплине «Моделирование производственных и экономических процессов»

Обучающийся

Группа: Специальность: 1304000 «Вычислительная техника и программное обеспечение».

Консультант:

1.Тема курсовой работы «Использование линейного программирования для решения задач оптимизации».

2.Основное содержание:

Ш Содержание

Ш Заключение

Ш Список использованной литературы

Ш Приложение

3. Требование к оформлению

3.1 Пояснительная записка должна быть оформлена в редакторе Microsoft ® Word версии 2003,2007 в соответствии с требованиями

Пояснительная записка выполняется на листах формата А4 с применением печатающих и графических устройств вывода ЭВМ.

Шрифт Times New Roman. Размер шрифта - 14 пт, выравнивание - по ширине.

Рисунки выполняются в редакторах Word,Excel,Paintbrush.

Поля страница верхнее и нижняя границы - 2см, левая-3см, правая-1,5 см.

Абзацы в тексте начинают отступом в 1 см.

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

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

К защите курсового проекта создается презентация, содержащая главную суть курсового проекта.

В пояснительной записке должны содержаться разделы:

· Введение

· Использование линейного программирования для решения задач оптимизации

· Модели линейного программирования

· Практическая часть



ВВЕДЕНИЕ

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

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

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

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

количество продукции - расход сырья

количество продукции - качество продукции

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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности». Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

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

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

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

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

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцигом симплекс-метода.

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

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

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



1. ИСПОЛЬЗОВАНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

1.1 Общая задача оптимизации

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

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

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

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

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

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

В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (х₁, х₂, ..., х_n) при условиях g_i(х₁, х₂, ..., х_n) b_i; (i =1,2,…m), где f и g_i; - заданные функции, а b_i - некоторые действительные числа.

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

В общем виде задача линейного программирования (ЗЛП) ставится следующим образом:

Найти вектор , максимизирующий линейную форму

(1)

и удовлетворяющий условиям

(2)

(3)

Линейная функция называется целевой функцией задачи. Условия (2) называются функциональными, а (3) - прямыми ограничениями задачи.

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

,

где - оптимальное решение ЗЛП. Будем считать, что ЗЛП записана в канонической форме, если ее целевая функция максимизируется, ограничения имеют вид равенств с неотрицательной правой частью и все переменные неотрицательны.

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

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

При постановке задачи оптимизации необходимо:

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

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

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

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

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

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

4. Учет ограничений.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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



2. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

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

Основные формы задачи ЛП.

Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.

Стандартная задача ЛП

или, в матричной записи,

где -- матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, -- вектором ограничений.

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



Каноническая задача ЛП

или, в матричной записи,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

Общая задача ЛП

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



Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая -- при .

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

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

1.3 Двойственная задача линейного программирования

Рассмотрим задачу ЛП

(1)

или, в матричной записи,

(2)



Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида

(3)

или, в матричной записи,

(4)

где .

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

Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.

Теорема двойственности.

Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.

Теорема равновесия.

Пусть -- оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если то



3. ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1 Приведение задачи к стандартной форме

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

X1 + X2 + X3 + X7 = 8;

X4 + X5 + X6 + X8 = 8;

2X1 - X2 + 6X4 - 3X5 = 0;

2X1 - 2X3 + 6X4 - 2X6 =0;

X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8 ? 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 ?max

где Х7 , Х8 - остаточные переменные.

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

Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Поэтому для нахождения начального решения задачи требуется выразить m переменных (т.е. количество переменных, равное количеству уравнений) через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных (в заданной задаче m=4 и n=8). Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны (некоторые из них могут оказаться равными нулю). Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением. Оно соответствует всем ограничениям.

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

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

3.2 Построение искусственного базиса

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

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



2X1 - X2 + 6X4 - 3X5 + Х9 = 0;

2X1 - 2X3 + 6X4 - 2X6 + Х10 =0.

где Х9 и Х10 - искусственные переменные, не имеющие никакого физического смысла, причем Х9 , Х10 ?0.

После построения искусственного базиса, придав нулевые значения всем переменным, кроме базисных, получим начальный базис: Х7 , Х8 , Х9 , Х10 . Всего в базисе имеется четыре переменные и их значения равны правым частям ограничений, т.е.:

Х7 = 8;

Х8 = 8;

Х9 = 0;

Х10 = 0.

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

3.3 Первый этап двухэтапного симплекс-метода

линейное программирование задача оптимизация

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

1. Строим искусственную целевую функцию - сумму всех искусственных переменных:

W = X9 + X10 ? min

2. Так как целевая функция должна быть выражена только через небазисные переменные, то выражаем искусственные переменные X9 и X10 через небазисные переменные, а затем, упростив полученное выражение, переписываем искусственную целевую функцию:

X9 = - 2X1 + X2 - 6X4 + 3X5;

X10 = - 2X1 + 2X3 - 6X4 + 2X6.

W = - 4X1 + X2 + 2X3 - 12X4 + 3X5 + 2X6 ? min

3. Для приведения к стандартной форме направим искусственную целевую функцию на максимум, для этого умножим обе ее части на -1:

-W = 4X1 - X2 - 2X3 + 12X4 - 3X5 - 2X6 ? max

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

5. Составляем исходную симплекс-таблицу:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	-1	-1	-2	-3	-3	-2	0	0	0	0	0
-W	-4	1	2	-12	3	2	0	0	0	0	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	0	0	0	1	1	1	0	1	0	0	8
X9	2	-1	0	6	-3	0	0	0	1	0	0
X10	2	0	-2	6	0	-2	0	0	0	1	0

Таблица 2. Симплекс-таблица №1.

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

6. Реализуем первый этап двухэтапного метода: с помощью процедур симплекс-метода выполняем максимизацию функции -W. При этом переменные, включаемые в базис, выбираются по W-строке (т.е. на каждом цикле в базис включается переменная, которой соответствует максимальный по модулю отрицательный элемент в W-строке; столбец, соответствующий этой переменной, становится ведущим). В нашем случае это столбец X4, т. к. коэффициент при этой переменной в W-строке равен -12. Ведущую строку определяем следующим образом: рассчитываем так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным коэффициентам ведущего столбца, соответствующим данным базисным переменным. Затем берем минимальное из этих отношений и по тому, какой строке оно соответствует, определяем ведущую строку. У нас есть три таких отношения: по переменной Х8 (8/1=8), Х9(0/6=0) и Х10 (0/6=0). Получилось два минимальных значения, значит, возьмем любое из них, например по переменной Х9. После находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца (в нашем случае он равен 6). Затем определяем переменные, которые будем исключать из базиса и включать в него. Переменную, которой соответствует ведущий столбец, будем включать в базис вместо переменной, которой соответствует ведущая строка. Далее все преобразования выполняем по обычным формулам симплекс-метода или по "правилу прямоугольника". Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W-строку и столбец решений. Получаем новую симплекс-таблицу:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	-1,5	-2	0	-4,5	-2	0	0	0,5	0	0
-W	0	-1	2	0	-3	2	0	0	2	0	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	-0,33	0,17	0	0	1,5	1	0	1	-0,17	0	8
X4	0,33	-0,17	0	1	-0,5	0	0	0	0,17	0	0
X10	0	1	-2	0	3	-2	0	0	-1	1	0

Таблица 3. Симплекс-таблица №2.

Мы получили новое решение (Х7,Х8,Х4,Х10)=(8,8,0,0). Это решение недопустимо, так как в базисе содержится искусственная переменная Х10. Выполим очередную итерацию. По строке -W для включения в базис выбираем переменную X5 (т.к. -3 - максимальное по модулю отрицательное число). Столбец X5 становится ведущим. По минимальному симплексному отношению ( 8/1,5=5,33; 0/3=0) для исключения из базиса выбираем переменную Х10. Ведущий элемент равен 3. После проведенных пересчетов получаем новую симплекс-таблицу:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	0	-5	0	0	-5	0	0	-1	1,5	0
-W	0	0	0	0	0	0	0	0	1	1	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	-0,33	-0,33	1	0	0	2	0	1	0,33	-0,5	8
X4	0,33	0	-0,33	1	0	-0.33	0	0	0	0,17	0
X5	0	0,33	-0,67	0	1	-0,67	0	0	-0,33	0,33	0

3.4 Второй этап двухэтапного симплекс-метода

Итак, как видно из Таблицы 4, все искусственные переменные вышли из базиса, искусственная целевая функция обнулилась - значит, первый этап двухэтапного симплекс-метода закончен, найдено начальное допустимое решение: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), целевая функция Е=0. Теперь переходим к реализации второго этапа: вычеркиваем из таблицы строку искусственной целевой функции и столбцы искусственных переменных; над новой таблицей выполняем обычные процедуры симплекс-метода, а именно: ведущий столбец определяется также, как и для первого этапа двухэтапного симплекс-метода, единственное различие состоит в том, что максимальный по модулю отрицательный коэффициент находим по Е-строке целевой функции. Расчет ведем до тех пор, пока в Е-строке не останется отрицательных коэффициентов:

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	0	0	-5	0	0	-5	0	0	0
X7	1	1	1	0	0	0	1	0	8
X8	-0,33	-0,33	1	0	0	2	0	1	8
X4	0,33	0	-0,33	1	0	-0,33	0	0	0
X5	0	0,33	-0,67	0	1	-0,67	0	0	0

Таблица 5. Симплекс-таблица №4.

Наше начальное допустимое решение не является оптимальным, так как в Е-строке содержатся отрицательные коэффициенты. Определим поЕ-строке новую переменную для включения в базис. Это переменная X3, т.к. -5 - максимальное по модулю отрицательное число (коэффициентЕ-строки при переменной X6 также равен -5, поэтому выбрали любую из этих переменных, например X3). Столбец X3 становится ведущим. По минимальному симплексному отношению ( 8/1=8; 8/1=8) для исключения из базиса выбираем переменную Х7 (симплексное отношение при переменной X8 также равно 8, поэтому выбрали любую из этих переменных). Ведущий элемент равен 1. После проведенных пересчетов получаем новую симплекс-таблицу:

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	5	5	0	0	0	-5	5	0	40
X3	1	1	1	0	0	0	1	0	8
X8	-1,33	-1,33	0	0	0	2	-1	1	0
X4	0,67	0,33	0	1	0	-0,33	0,33	0	2,67
X5	0,67	1	0	0	1	-0,67	0,67	0	5,33

Таблица 6. Симплекс-таблица №5.



Итак, как видно из таблицы, некоторые из искомых переменных , а именно Х3, Х4 и Х5, начали расти, что привело и к росту значения целевой функции - из нулевого значения она приняла значение 40. Это можно объяснить тем, что из точки начального допустимого решения мы перешли к соседней угловой точке области допустимых решений, причем в этой соседней точке рост целевой функции максимален. Однако в Е-строке есть еще отрицательный коэффициент, поэтому продолжим расчеты.

Определим по Е-строке новую переменную для включения в базис. Это переменная X6, т.к. -5 - максимальное по модулю отрицательное число. Столбец X6 становится ведущим. По минимальному симплексному отношению ( 0/2=0) для исключения из базиса выбираем переменную Х8. Получаем новую симплекс-таблицу:

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	1,67	1,67	0	0	0	0	2,5	2,5	40
X3	1	1	1	0	0	0	1	0	8
X6	-0,67	-0,67	0	0	0	1	-0,5	0,5	0
X4	0,44	0,11	0	1	0	0	0,17	0,17	2,67
X5	0,22	0,55	0	0	1	0	0,33	0,33	5,33

Таблица 7. Симплекс-таблица №6.

Так как все коэффициенты E-строки таблицы 7 положительные, то оптимальное решение найдено. Оптимальный план состоит в том, чтобы токарный станок работал над деталями типа 3 8 часов за смену, то есть всю рабочую смену, и не работал над деталями типа 1 и 2 вообще. Станок-автомат должен работать за смену 2,67 часа над деталями типа 1 и 5,33 часа над деталями типа 2 и не должен работать над деталями типа 3. При этом за смену будет выпускаться максимально возможное количество комплектов деталей, а именно 40 комплектов. Ни один из станков не будет простаивать.



ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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



СПИСОК ЛИТЕРАТУРЫ ПО ТЕМАМ КУРСОВЫХ ПРОЕКТОВ

Основные

1. Акулич И.Л. Математическое программирование впримерах и задачах. - М.: Высшая школа, 1986 г.

2. Власов М.П., Шимко П.Д. Моделирование экономичексих процессов. - Ростов-на -Дону, Феникс - 2005 (электронный учебник)

3. Яворский В.В., Амиров А.Ж. экономическая информатика и информационные системы (лабораторный практикум) - Астана, Фолиант, 2008 г.

4. Симонович С.В. Информатика, Питер, 2003 г.

5. Воробьев Н.Н. Теория игр для экономистов - кибернетиков. - М.: Наука, 1985 (электронный учебник)

6. Алесинская Т.В. Экономико-математические методы и модели. - Таган Рог, 2002 (электронный учебник)

7. Гершгорн А.С. Математическое программирование и его применение в экономических расчетах. -М. Экономика, 1968 г.

Дополнительно

1. Дарбинян М.М. Товарные запасы в торговле и их оптимизация. - М. Экономика, 1978 г.

2. Джонстон Д.Ж. Экономические методы. - М.: Финансы и статистика, 1960 г.

3. Епишин Ю.Г. Экономико-математические методы и планировании потребительской кооперации. - М.: Экономика, 1975 г.

4. Житников С.А., Биржанова З.Н., Аширбекова Б.М. Экономико-математические методы и модели: Учебное пособие. - Караганда, издательство КЭУ, 1998 г.

5. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. - М.: ДИС, 1997 г.

6. Иванилов Ю.П., Лотов А.В. Математические методы в экономике. - М.: Наука, 1979 г.

7. Калинина В.Н., Панкин А.В. Математическая статистика. М.: 1998 г.

8. Колемаев В.А. Математическая экономика. М., 1998 г.

9. Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операции в экономике. Учебное пособие - М.: Банки и биржи, ЮНИТИ, 1997 г

10. Спирин А.А:, Фомин Г.П. Экономико-математические методы и модели в торговле. - М.: Экономика, 1998 г.

11. http://ru.wikipedia.org

12. http://psbatishev.narod.ru/internet/11.htm

13. http://kk.wikipedia.org

14. www.kaznau.kz

15. http://45minut.kz



ПРИЛОЖЕНИЯ

Задача 1

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

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

Вид ресурсов	Нормы расхода ресурсов на ед. продукции	Запасы ресурсов
	I вид	II вид	III вид
Труд	1	4	3	200
Сырье	1	1	2	80
Оборудование	1	1	2	140
Цена изделия	40	60	80

Требуется:

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

2. Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

3. Пояснить нулевые значения переменных в оптимальном плане.

4. На основе свойств двойственных оценок и теорем двойственности:

· проанализировать использование ресурсов в оптимальном плане исходной задачи;

· определить, как изменяется выручка от реализации продукции и план ее выпуска при увеличении запасов сырья на 18 единиц;

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

Решение

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

Х₁- норма расхода ресурса первого вида

Х₂ - норма расхода ресурса второго вида

Х₃ - норма расхода ресурса третьего вида.

Целевая функция имеет вид

, где

Ограничения:

1) по труду

2) по сырью

3) по оборудованию

Оптимальный план найдем через Поиск решений в надстройках Excel (рис. 2.1) и (рис. 2.2).



Рис. 2.1

Рис. 2.2

Полученное решение означает, что максимальную выручку от реализации готовой продукции (4000 ед.) предприятие может получить при выпуске 40 единиц изделия 1 вида и 40 единиц изделия 2 вида. При этом ресурс «труд» и «сырье» будут использованы полностью, из 140 единиц оборудования будет использовано только 80 единиц.

Excel позволяет представить результаты поиска решения в форме отчета рис. 2.3

Microsoft Excel 10.0 Отчет по результатам
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$D$3		4000	4000
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$A$2	х1	40	40
	$B$2	х2	40	40
	$C$2	х3	0	0
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$D$4		200	$D$4<=$E$4	связанное	0
	$D$5		80	$D$5<=$E$5	связанное	0
	$D$6		80	$D$6<=$E$6	не связан.	60

Рис.2.3

В отчете по результатам содержатся оптимальные значения переменных , которые соответственно равны 40; 40; 0; значение целевой функции - 4000, а также недоиспользованный ресурс «оборудование» в размере 60 единиц.

Оптимальный план

2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

Число неизвестных в двойственной задаче равно числу функциональных ограничений в исходной задаче. Исходная задача содержит 3 ограничения: труд, сырье и оборудование. Следовательно, в двойственной задаче 3 неизвестных:

двойственная оценка ресурса труд

двойственная оценка ресурса сырья

двойственная оценка ресурса оборудования

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

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

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

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

Найдем оптимальный план двойственной задачи, используя теоремы двойственности.

Воспользуемся первым соотношением второй теоремы двойственности



тогда

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

И получим

,

,

, так как 80 < 140, то

В задаче и , поэтому первое и второе ограничения двойственной задачи обращаются в равенства

Решая систему уравнений получим, y₁ = 6,67, y₂ = 33,33, y₃ = 0.

Проверяем выполнение первой теоремы двойственности



Это означает, что оптимальный план двойственной задачи определен, верно.

Решение двойственной задачи можно найти, выбрав команду Поиск решений - Отчет по устойчивости (рис.2.4).

Microsoft Excel 10.0 Отчет по устойчивости
Изменяемые ячейки
		Результ.	Нормир.	Целевой	Допустимое	Допустимое
Ячейка	Имя	значение	стоимость	Коэффициент	Увеличение	Уменьшение
$A$2	х1	40	0	40	20	4.000000003
$B$2	х2	40	0	60	100	20
$C$2	х3	0	-6.666666672	80	6.666666672	1E+30
Ограничения
		Результ.	Теневая	Ограничение	Допустимое	Допустимое
Ячейка	Имя	значение	Цена	Правая часть	Увеличение	Уменьшение
$D$4		200	6.666666667	200	120	120
$D$5		80	33.33333333	80	60	30
$D$6		80	0	140	1E+30	60

Рис 2.4

3) Пояснить нулевые значения переменных в оптимальном плане.

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

Затраты на 3 изделия превышают цену (). Это же видно и в отчете по устойчивости (рис. 2.4) значения (нормир. стоимость) равно -6.67. Т.е. стоимость нормы расходов на единицу изделия больше чем цена изделия. Эти изделия не войдут в оптимальный план из-за их убыточности.

4) На основе свойств двойственных оценок и теорем двойственности:

- проанализировать использование ресурсов в оптимальном плане исходной задачи;

- определить, как изменятся выручка от реализации продукции и план ее выпуска при увеличении запасов сырья на 18 единиц;

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

Проанализировать использование ресурсов в оптимальном плане исходной задачи;

Запасы сырья по первому и второму виду были использованы полностью, а по третьему виду - оборудование - было недоиспользовано 60.

Определить, как изменятся выручка и план выпуска продукции при увеличении запасов сырья на 18 единиц

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

Из расчетов видно, если мы увеличим запасы сырья на 18 единицы, то выручка возрастет на 600 единиц, т. е общая выручка составит после изменения запасов 4600 единиц.

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

Решим систему уравнений:

И получим



Новый оптимальный план

Изменение общей стоимости продукции на 600 ед. получено за счет увеличения плана выпуска 1 вида продукции на 24 ед по цене 40 ед (40*(64-40)=960 ед.) и уменьшения на 6 ед. плана выпуска продукции 2 вида по цене 60 (60*(34-40)=-360 ед.)

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

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

,

подставим

, ,

т.к. 80>70, то включение в план изделия четвертого вида невыгодно.



Задача 2

Используя балансовый метод планирования и модель Леонтьева, построить баланс производства и распределения продукции предприятий.

Промышленная группа предприятий (холдинг) выпускает продукцию трех видов, при этом каждое из трех предприятий группы специализируется на выпуске одного вида: первое предприятие специализируется на выпуске продукции первого вида; второе предприятие - продукции второго вида; третье предприятие - продукции третьего вида. Часть выпускаемой продукции потребляется предприятиями холдинга (идет на внутренне потребление), остальная часть поставляется за его пределы (внешним потребителям, является конечным продуктом). Специалистами управляющей компании получены экономические оценки a_ij (i=1,2,3; j=1,2,3) элементов технологической матрицы А (норм расхода, коэффициентов прямых материальных затрат) и элементов y_i вектора конечной продукции Y.

Требуется:

1. Проверить продуктивность технологической матрицы А=( a_ij) (матрицы коэффициентов прямых материальных затрат).