Задачи математического программирования

Федеральное агентство по образованию

Новокузнецкий филиал-институт

ГОУ ВПО «Кемеровский государственный университет»

кафедра информационных систем и управления им. В.К. Буторина

Курсовая работа

Задачи математического программирования

(Вариант 4)

Новокузнецк 2010

Содержание

Введение

1. Понятие математического программирования

2. Понятие линейного программирования. Виды задач линейного программирования

3. Понятие нелинейного программирования

4. Динамическое программирование

Лабораторная работа №1 (Задача линейного программирования)

Лабораторная работа № 2(Решение задачи ЛП средствами табличного процессора Excel)

Лабораторная работа № 3 (Решение транспортной задачи)

Лабораторная работа №4 (решение задач нелинейного программирования)

Лабораторная работа №5 (задача динамического программирования об оптимальном распределении инвестиций)

Лабораторная работа №5 (задача динамического программирования о выборе оптимального пути в транспортной сети)

Заключение

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

Введение

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

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

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

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

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

В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f(x1, х2,.........., xn) при условиях gi(x1, х2,.........., xn) ≤ bi, где f и gi — заданные функции, a bi — некоторые действительные числа.

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

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

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

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

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

1. Понятие математического программирования

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

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

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

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

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

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

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

задачи динамического программирования.

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

2. Понятие линейного программирования. Виды задач линейного программирования

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

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

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

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

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

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

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

Графический метод решения задачи ЛП;

Симплексный метод;

Решение задачи ЛП средствами табличного процессора Excel;

3. Понятие нелинейного программирования

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

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

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

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

4. Динамическое программирование

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

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

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат Wk(S,Xk) и переводит систему в некоторое новое состояние S'(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение.

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

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

целевая функция является аддитивной и равна сумме целевых функций каждого шага

;

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

;

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

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

X*=(X*1, X*2, …, X*k, …, X*n),

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

Fn(S)=max{Wn(S,Xn)},

где максимум ищется по всем возможным значениям Xn.

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

Fk(S)=max{Wk(S,Xk)+Fk+1(S'(S,Xk))}. (1)

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

Лабораторная работа №1 (Задача линейного программирования)

Задание:

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

Решить задачу графическим методом;

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

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

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

Осуществить постановку двойственной задачи ЛП;

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

Проверить результаты решения в табличном процессоре Excel;

Составить отчет с приведение результатов по каждому пункту.

Ресурсы	Запасы	Продукция
		Р1	Р2
S1	18	0.2	3
S2	13.1	0.7	2
МВ	23	2.3	2
Прибыль от единицы продукции в У.Е.	3	4

Решение:

Графический метод. Для построения многоугольника решений преобразуем исходную систему

, получим

изобразим граничные прямые.

Линейная функция F=f(x) является уравнением прямой линии c1x1 + c2x2 = const. Построим график целевой функции при f(x)=0. для построения прямой 3x1 + 4x2 = 0 строим радиус-вектор N = (3; 4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую F=0 перемещаем параллельно самой себе в направлении вектора N.

0100090000032102000002009c01000000009c01000026060f002e03574d46430100000000000100c70f00000000010000000c030000000000000c030000010000006c0000000000000000000000350000006f000000000000000000000074450000f604000020454d46000001000c0300001100000002000000000000000000000000000000c0120000aa1a0000cb00000021010000000000000000000000000000c0190300c7680400160000000c000000180000000a0000001000000000000000000000000900000010000000681000002c010000520000007001000001000000a4ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000bc84110054861100708b1d0af08211007c5f6d31548611002000000048831100ffffffff38861100d0831100ec017831488311005486110020000000ffffffffcc3298056102783101000000000000005802000025000000372e9001cc00020f0502020204030204ff0200e1ffac004009000000000000009f01000000000000430061006c006900620072000000000000000000000000000000000000000000000000007c831100bd4c703107000000ffffffdfb883110068756e31c883110058616232e0831100cc3298056476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000120000000c00000001000000180000000c0000000000000254000000540000000000000000000000350000006f0000000100000055558740637b87400000000057000000010000004c000000040000000000000000000000681000002c010000500000002000000036000000180000000c0000000000000246000000280000001c0000004744494302000000ffffffffffffffff691000002d010000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c023000a702040000002e0118001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010000040000002d010000040000002d0100000400000002010100050000000902000000020d000000320a0e0000000100040000000000a6023000200f0900050000000902000000021c000000fb020300010000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010100040000002d010100030000000000

Из рисунка 1 следует, что опорной по отношению к построенному многоугольнику решений эта прямая становится в точке B, где функция F принимает максимальное значение. Точка В лежит на пересечении прямых 0,7x1 + 2x2 ≤ 13,1 и 2,3x1 + 2x2 =23/ Для определения ее координат решим систему уравнений:

Оптимальный план задачи: х1 = 6.187; х2 = 4.38, подставляя значения х1 и х2 в целевую функцию, получаем Fmax= 3*6.187+4*4.38=36.08.

Таким образом, для того, чтобы получить максимальную прибыль в размере 36.06 долларов, необходимо запланировать производство 6 ед. продукции P1 и 4 ед. продукции P2.

Канонический вид задачи ЛП. Запишем в канонической форме задачу распределения ресурсов. Добавив к исходной системе ограничений неотрицательные переменные х3 ≥ 0, х4 ≥ 0, х5 ≥ 0, имеем:

При этом в далее получаемом решении переменные х3 и х4 будут соответствовать объемам неиспользованного сырья S1 и S2, а х5 – неиспользованному машинному времени.

Симплексная таблица ЛП. В случае базисных переменных {x3, x4, x5} начальная симплекс таблица будет выглядеть:

Таблица 1.

	-х1	-х2
х3 =	0,2	3	18
х4 =	0,7	2	13,1
х5 =	2,3	2	23
f(x) =	3	4

Она уже соответствует опорному плану x(0) = [0 0 18 13,1 23]Т (столбец свободных членов).

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

Алгоритм симплекс метода.

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

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

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

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

3.1 на месте разрешающего элемента ставится 1 и делится на разрешающий элемент;

3.2 остальные элементы разрешающего столбца меняют знак на противоположный и делятся на разрешающий элемент;

3.3 остальные элементы разрешающей строки делятся на разрешающий элемент;

3.4. все остальные элементы симплексной таблицы вычисляются по формуле:

3.5. элементы правого столбца и нижней строки пересчитываются по тому же принципу, что и элементы в центральной части таблицы.

Симплексная таблица, рассчитанная по алгоритму:

Таблица 2.

	-х1	-х3
х2 =	0,067	0,3	6
х4 =	0,57	-0,67	1,1
х5 =	2,17	-0,67	11
f(x) =	-3,27	1,3	72,6

Следующим разрешающим столбцом будет столбец х1, а разрешающей строкой – х4. Далее действуем по тому же алгоритму.

Таблица 3.

	-х4	-х3	1
х2 =	-0,1	0,24	5,87
х1 =	1,75	-1,17	1,03
х5 =	-3,8	1,88	5,8
f(x) =	5,7	-2,5	35,06

Следующим разрешающим столбцом будет столбец х5, а разрешающей строкой – х3. Далее действуем по тому же алгоритму.

Таблица 4.

	-х4	-х5	1
х2 =	0,39	-0,13	4,4
х1 =	-0,61	0,6	6,19
Х3 =	-2	0,53	1,3
f(x) =	0,64	1,3	36,08

Конечная симплексная таблица:

Все коэффициенты в строке целевой функции положительны, т.е. мы нашли оптимальное решение.

Таким образом, в точке x1 = 4, x2 = 6, x3 = 1,3, x4 = 0, x5 = 0 целевая функция принимает максимальное значение f(x) = 36.

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

Постановка двойственной задачи ЛП. Определить значение двойственных оценок можно следующим образом. если некоторый i-тый ресурс используется не полностью, т.е. имеется резерв, значит дополнительная переменная в ограничении для данного ресурса будет больше нуля. Очевидно, что при увеличении общего машинного времени не произошло бы увеличение целевой функции. Следовательно, машинное время не влияет на прибыль и для третьего ограничения двойственная переменная y3 = 0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка данного ограничения равна нулю.

В данном примере оба вида сырья использовались полностью, поэтому их дополнительные переменные равны нулю (в итоговой симплексной таблице переменные х3 и х4 являются свободными, значит х3 = х4 = 0). Если ресурс использовался полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции и, следовательно, на величину целевой функции. Значение двойственной оценки при этом находится в симплекс-таблице на пересечении строки целевой функции со столбцом данной дополнительной переменной.

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

Таблица 4.

Исходная задача ЛП	Двойственная задача ЛП
Математическая постановка
Обозначения и интерпретация параметров задачи
xj, j = - количество производимой продукции j-го вида; f(x) – общая прибыль от реализации продукции	yi, i = - стоимость единицы i-го ресурса; - стоимость всех имеющихся ресурсов
Экономическая интерпретаци язадачи
Сколько и какой продукции необходимо произвести, чтобы пр заданных стоимостях cj, j = еддиницы продукции и размерах имеющихся ресурсов bi, i = максимизировать общую прибыль?	Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных их количествах bi, i = и величинах стоимости единицы продукции cj, j = минимизировать общую стоимость затрат?
Результаты решения
Результирующая симплекс-таблица -х4 -х5 1 х2 = … … 4,4 х1 = … … 6,19 Х3 = … … 1,3 f(x) = 0,64 1,3 36,08 Основные переменные х1 = 6,19 х2 = 4,4 дополнительные переменные х3 = 1,3 х4 = 0 х5 = 0	Дополнительные переменные y4 = 0 y5 = 0 основные переменные y1 = 0,64 y2 = 1,3 y3 = 0
Интерпретация дополнительных переменных
xn+1, …., xn+m – неиспользованное (резервное) количество соответствующего ресурса (при наличие резервного ресурса соответствующая двойственная переменная навна 0)	ym+1, …, ym+n – насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции (если какая-либо из основных переменных исходной задачи равна 0)

Проверить результаты решения в табличном процессоре Excel. В Excel имеется надстройка «Поиск решения», которая позволяет решать оптимизационные задачи.

Использовав эту надстройку для решения нашей задачи ЛП, получаем следующий результат:

Таблица 6.

	Переменные	Целевая функция
Вид продукции	Р1	Р2	Прибыль
Значение	6,1875	4,3844	36,1
Прибыль от ед. прод.	3	4	макс
Ограничения
Типы ресурсов	Р1	Р2	Расход ресурсов	Знак	Запас ресурсов
Сырье S1	0,2	3	14,390625	<=	18
СырьеS2	0,7	2	13,1	<=	13,1
Машинное время	2,3	2	23	<=	23

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

Таблица 7.

	Переменные
имя	x1	x2	f(x)
значение	6,19	4,38	36,1
коэф-ты f(x)	3	4	макс

Ограничения	двойств. Оценки
№	x1	x2	левая часть	знак	правая часть	y
1	8	3	62,653125	<=	18	1,333333
2	0,7	2	13,1	<=	13,1	0
3	2,3	2	23	<=	23	0
Ограничения двойственной задачи			Целевая функция двойственной задачи
	10,66667	4				24

Лабораторная работа № 2 (Решение задачи ЛП средствами табличного процессора Excel)

Для заданной содержательной постановки задачи ЛП выполнить следующие действия:

Осуществить математическую запись задачи ЛП;

Решить задачу с использование надстройки Excel «Поиск решения»;

Привести математическую постановку двойственной задачи ЛП;

Получить решение двойственной задачи ЛП с использованием надстройки Excel «Поиск решения»;

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

Произвести анализ полученных результатов и дать их содержательную интерпретацию.

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

Продукты	Питательные вещества
	белок	кальций	витамины
1. Сено	5	6	2
2. Силос	2	4	1
3. Концентраты	18	3	1
Норма потребления	200	120	40

Определить оптимальный режим кормления, из условия минимальной стоимости, если цена 1 кг продукта питания соответственно составляет: для сена - 30коп., для силоса- 20 коп., для концентрата – 50 коп.

Решение

Осуществить математическую запись задачи ЛП. Составим математическую модель. Обозначим через х1 – количество единиц сена, через х2 – количество единиц силоса а через х3 – количество единиц концентрата. Функция затрат на покупку этих продуктов выглядит так: f(x)=30x1+20x2+50x3 её необходимо минимизировать. Необходимые нормы потребления выражены в виде ограничений:

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

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

После ввода всех данных выбираем команду Сервис / Поиск Решения и, заполняем открывшееся диалоговое окно Поиск Решения:

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

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

Для данной задачи достаточно установить два флажка «Линейная модель» (т.к. ограничения и целевая функция являются линейными по переменным) и «Неотрицательные значения» (для выполнения условий задачи ЛП).

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

Таблица 9

Переменные	Целевая функция
Вид продукта	сено	силос	концентрат	f(x)
значение	16,77	0,00	6,45	76,13
затраты на ед.прод.	3	2	4	min
		Ограничения
Питательные вещества	сено	силос	концентрат	расход питательных веществ	знак	необходимое потребление пит.веществ
белки	5	2	18	200,00	>=	200
кальций	6	4	3	120,00	>=	120
витамины	2	1	1	40,00	>=	40

Привести математическую постановку двойственной задачи ЛП. Двойственная задача ЛП определяется по формуле:

Математическая постановка двойственной задачи ЛП:

Получить решение двойственной задачи ЛП с использованием надстройки Excel «Поиск решения». К имеющимся данным добавляются значения двойственных переменных, ячейка, содержащая формулу целевой функции двойственной задачи, и ячейки, определяющие левые части ограничений двойственной задачи. Далее для решения двойственной задачи выполняем с помощью надстройки Excel «Поиск решения». Получаем:

Таблица 10

	Переменные			Целевая функция
Вид продукта	сено	силос	концентрат	f(x)
значение	16,77	0,00	6,45	76,13
затраты на ед.прод.	3	2	4	min

		Ограничения
Питательные вещества	сено	силос	концентрат	Левая часть	знак	Правая часть	Двойственные оценки
белки	5	2	18	200,00	>=	200	0,6
кальций	6	4	3	120,00	>=	120	0
витамины	2	1	1	40,00	>=	40	0
Ограничения двойственной функции	Целевая функция двойственной задачи
3	1,2	10,8	120

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

Таблица 11

Переменные	Целевая функция
Вид продукта	сено	силос	концентрат	f(x)
значение	16	0	6	76
затраты на ед.прод.	3	2	4	min
		Ограничения
Питательные вещества	сено	силос	концентрат	расход питательных веществ	знак	необходимое потребление питательных веществ
белки	5	2	18	200	>=	200
кальций	6	4	3	120	>=	120
витамины	2	1	1	40	>=	40

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

Лабораторная работа № 3 (Решение транспортной задачи)

Для заданной матрицы издержек С, вектора – столбца запасов В в пунктах отправления и вектора - строки потребностей А в пунктах назначения решить транспортную задачу и составить отчет по следующим пунктам:

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

Решить задачу с помощью надстройки Excel «Поиск решения»;

Изменить данные для получения открытой задачи и решить ее.

2 3 4 2 4 140

С= 8 4 1 4 1 180

9 7 3 7 2 160

60 70 120 130 100

Решение

Осуществить математическую запись транспортнойзадачи.Обозначим через хij количество единиц сырья, перевозимого из i-го пункта его получения на j-тое предприятие. Тогда условие доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

x11+x12+x13+x14+x15 =140

x21+x22+x23+x24+x25 =180

x31+x32+x33+x34+x35 =160

x11 +x21 +x31 =60

x 12 +x22 +x32 =70

x 13 +x23 +x33 =120

x 14 +x24 +x34 =130

x 15 +x25 +x35=100

При этом общая стоимость перевозок составит

f(x)= 2x11+3x12+4x13+2x14+4x15 +8 x21+4x22+x23+4x24+x25+9 x31+7x32+3x33+7x34+2x35

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

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

Таблица 12

Пункты отправления	Пункты назначения
	В1	В2	В3	В4	В5	Запасы
А1	2	3	4	2	4	140
А2	8	4	1	4	1	180
А3	9	7	3	7	2	160
Потребности	60	70	120	130	100
Транспортная таблица
А1	140	0	0	0	0	140
А2	0	0	180	0	0	180
А3	0	0	0	0	160	160
Потребности	60	70	120	130	100
				Транспортные расходы	780

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

Таблица 13

Таблица издержек
Пункты отправления	Пункты назначения
	В1	В2	В3	В4	В5	Запасы
А1	2	3	4	2	4	140
А2	8	4	1	4	1	150
А3	9	7	3	7	2	100
Потребности	60	100	120	200	100
Транспортная таблица
А1	0	0	0	140	0	140
А2	0	0	0	0	150	150
А3	0	0	0	0	100	100
Потребности	60	100	120	200	100
				Транспортные расходы	630

Лабораторная работа №4 (решение задач нелинейного программирования)

Для заданной математической постановки задачи НП (целевой функции f(x) и ограничений - равенств) выполнить следующие действия:

Найти все условные экстремумы функций методом множителей Лагранжа и выбрать среди них глобальный минимум (максимум);

Проверить результаты решения в табличном процессоре Excel;

(1)

Метод множителей Лагранжа

Необходимо перевести условие к виду

Составим вспомогательную функцию Лагранжа:

Для данной задачи получим:

(2)

Дифференцируем данную функцию по х1, х2, x3, и , получим систему уравнений:

(3)

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

Решив это уравнение, получаем:

х1=2,25, х2=-1,25, x3= 1,5, =-1,5 и =-3, F=12

Точка экстремума заданной функции f(x) - (х1, х2, x3), является точкой глобального минимума при заданных ограничениях функции.

Решение в табличном процессоре Excel. Проверим результаты решения в табличном процессоре Excel.

Решение задачи с помощью процессора Excel дало следующие результаты:

Таблица 13

х1	х2	x3
2,25	-1,25	1,50
Целевая функция	12,00
Ограничения	4,00	=	4
	6,00	=	6

Решения задачи обеими методами дали одинаковый результат.

Лабораторная работа №5 (задача динамического программирования об оптимальном распределении инвестиций)

Задача

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

Таблица 14

X	g1	g2	g3	g4
0	0	0	0	0
20	14	17	22	20
40	26	20	21	33
60	35	32	37	46
80	52	61	67	30
100	61	72	58	42

Решение

Этап I. Условная оптимизация.

Шаг 1. k = 4. Предполагаем, что все средства 100 ден.ед. переданы на инвестирование четвертого предприятия. В этом случае максимальная прибыль составит F4(C4)= 46, данные представлены в таблице 15.

Таблица 15.

C4	x4	F4(C4)	X*
	0	20	40	60	80	100
0	0	-	-	-	-	-	0	0
20	-	20	-	-	-	-	20	20
40	-	-	33	-	-	-	33	40
60	-	-	-	46	-	-	46	60
80	-	-	-	-	30	-	30	80
100	-	-	-	-	-	42	42	100

Шаг 2. k = 3. Определяем оптимальную стратегию инвестирования в третье и четвертое предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:

.

На его основании рассчитываются данные таблицы 16

Таблица 16.

C3	X3	F3(C3)	X*
	0	20	40	60	80	100
0	0+0	-	-	-	-	-	0	0
20	0+20	22+0	-	-	-	-	22	20
40	0+33	22+20	21+0	-	-	-	42	20
60	0+46	22+33	21+20	37+0	-	-	55	20
80	0+30	22+46	21+33	37+20	67+0	-	68	20
100	0+42	22+30	21+46	37+33	67+20	58+0	87	20

Шаг 3. k = 2. Определяем оптимальную стратегию инвестирования во второе и третье предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:

.

На его основании рассчитываются данные таблицы 3.

Таблица 17.

C2	X2	F2(C2)	X*
	0	20	40	60	80	100
0	0+0	-	-	-	-	-	0	0
20	0+22	17+0	-	-	-	-	22	0
40	0+42	17+22	20+0	-	-	-	42	0
60	0+55	17+42	20+22	32+0	-	-	59	20
80	0+68	17+55	20+42	32+22	61+0	-	72	20
100	0+87	17+68	20+55	32+42	61+22	72+0	87	0

Шаг 4. k = 1. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:

.

На его основе находятся данные таблицы 4.

Таблица 18.

C1	X1	F1(C1)	X*
	0	20	40	60	80	100
0	0+0	-	-	-	-	-	0	0
20	0+48	14+0	-	-	-	-	22	0
40	0+93	14+48	26+0	-	-	-	42	0
60	0+135	14+93	26+48	35+0	-	-	59	0
80	0+149	14+135	26+93	35+48	52+0	-	72	0
100	0+160	14+149	26+135	35+93	52+48	61+0	87	0

По данным последней таблицы максимальных доход с четырех предприятий составил 87 д.ед. При этом первое и второе предприятия не принесут никакого дохода, в них нецелесообразно вкладывать инвестиции. В 3-е предприятие нужно вложить 80 д.ед. В 4-е предприятие нужно вложить 20 д.ед. В итоге останется 20-Получается, что оптимальный план Х*(0;0;80;20)

Лабораторная работа №5 (задача динамического программирования о выборе оптимального пути в транспортной сети)

Задача

В предложенной из начального пункта (1) в конечный пункт (11). Стоимость проезда между отдельными пунктами транспортной сети придумать самостоятельно и транспортной сети имеется несколько маршрутов по проезду представить в соответствующей таблице (T(i,j)). Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.

Рисунок 2 – Транспортная сеть

Элементы матрицы маршрутов транспортной сети, а так же стоимость проезда из пункта i в пункт j (tij) представлена в таблице 19.

Таблица 19.

j i	1	2	3	4	5	6	7	8	9	10	11
1	-	10	12	8	20	-	-	-	-	-	-
2	-	-	-	-	-	15	11	-	-	-	-
3	-	-	-	-	-	6	9	-	-	-	-
4	-	-	-	-	-	7	10	-	-	-	-
5	-	-	-	-	-	13	8	-	-	-	-
6	-	-	-	-	-	-	-	12	14	18	-
7	-	-	-	-	-	-	-	13	15	16	-
8	-	-	-	-	-	-	-	-	-	-	8
9	-	-	-	-	-	-	-	-	-	-	10
10	-	-	-	-	-	-	-	-	-	-	10
11	-	-	-	-	-	-	-	-	-	-	-

Решение

Этап I. Условная оптимизация.

Шаг 1. k = 1. F1(S) = ts10.

Таблица 18.

S	J=11	F(S)	J*
8	8	8	11
9	10	10	11
10	10	10	11

Шаг 2. k = 2. Функциональное уравнение на данном шаге принимает вид:

.

Результаты расчета по приведенной формуле приведены в таблице:

Таблица 19.

S	J=8	J=9	J=10	F(S)	J*
6	12+8	14+10	18+10	20	8
7	13+8	15+10	16+10	21	8

Шаг 3. k = 3. Функциональное уравнение на данном шаге принимает вид:

.

Результаты расчета по приведенной формуле приведены в таблице:

Таблица 20.

S	J=6	J=7	F(S)	J*
2	15+20	11+21	32	7
3	6+20	9+11	26	6
4	7+20	10+21	27	6
5	13+20	8+21	29	7

Шаг 4. k = 4. Функциональное уравнение на данном шаге принимает вид:

.

Результаты расчета по приведенной формуле приведены в таблице:

Таблица 21.

S	J=2	J=3	J=4	J=5	F(S)	J*
1	10+32	12+26	8+27	20+29	35	4

Этап II. Безусловная оптимизация.

На этапе условной оптимизации получено, что минимальные затраты на проезд из пункта 1 в пункт 11 составляют F4(1) = 35, что достигается следующим движением по магистралям. Из пункта 1 следует направиться в пункт 4, затем из него в пункт 6, затем в пункт 8 и из него в пункт 11. Таким образом, оптимальный маршрут будет J*(1;4;6;8;11)

Заключение

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

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

1.Графический метод;

2.Симплексный метод;

3.Постановка двойственной задачи;

4.Решение задачи в предложении целочисленности переменных;

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

1.Метод множителей Лагранжа

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

Метод об оптимальном распределении инвестиций;

Метод выбора стратегии обновления оборудования;

Метод выбора оптимального пути в транспортной сети.

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

1.Динамическое программирование: Рек к выполнению лаб. и практ.работ / Сост.: Шипилов С.А: НФИ КемГУ.- 2-е изд.перераб.- Новокузнецк. 2002.-19 с.

2.Динамическое программирование. Шипилов С.А.

3.Методы условной оптимизации: Рек. к выполнению лаб. и практ.работ / Сост.: Шипилов С.А: НФИ КемГУ.- 2-е изд.перераб.- Новокузнецк. 2002.-48 с.