ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ПСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

Решение задач линейного программирования в среде Maple

 

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

Студента 4 курса

физико-математического

факультета отделение «математика»

Гоняна Аршака Арзумановича

Научный руководитель

Матвеев Владимир Александрович

Псков

2008

Содержание

§1. Библиотека «simplex» пакета Maple

§2. Постановка задача линейного программирования для N переменных

§3. Постановка Транспортной задачи (ТЗ) для n переменных

§4. Пример решения задача линейного программирования

§5. Пример решения Транспортной задачи

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

§1. Библиотека «simplex» пакета Maple

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

После подключения библиотеки командой with(simplex) пользователю становится доступны функции и опции, указанные в следующей таблице.

basis Находит базисные переменые cterm Выводит список элементов вектора ресурсов display Представляет систему в матричной форме dual Преобразует данную задачу в двойственную задачу линейного программирования feasible Возвращает true – если решение существует, и false – если нет maximize Находит максимум целевой функции minimize Находит минимум целевой функции NONNEGATIVE Опция: указание на условие не отрицательности всех переменных setup Приводит систему ограничений к стандартной форме standardize Превращает систему ограничений в пары неравенств

§2. Постановка задача линейного программирования для N переменных

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

Построение экономико-математической модели

n - число различных видов продукции.

m - число различных ресурсов.

aij - объём i-того ресурса, который расходуется на производство одной единици j-того вида продукции i=1..m, j=1..n.

Xj - объем (количество единиц) j-того вида продукции в производственном плане предприятия (j от 1 до n).

Прибыль обозначим F, тогда F=c1X1+c2X2+...+cnXn->=max

Составим ограничения для первого ресурса:

а11 - объем первого ресурса, который расходуется на производство одной единицы первого вида продукции;

а11Х1 - объём первого ресурса, который требуется на изготовление Х1 единиц первого вида продукции;

а12Х2 - объём первого ресурса, который требуется на изготовление Х2 единиц второго вида продукции;

а1nХn - объём первого ресурса, который требуется на изготовление Хn единиц n-ого вида продукции;

а11Х1+a12X2+...+a1nXn - объём первого ресурса, который требуется на изготовление продукции, следовательно, мы имеем следующее ограничение:

 

а11Х1+а12+...+а1nXn<= b1

Аналогично для остальных ресурсов:

 

а21Х1+а22+...+а2nXn<=b2

а31Х1+а32+...+а3nXn<=b3

.........................................

аm1Х1+аm2+...+amnXn<=bm

Кроме того, количество выпущенной продукции не может быть отрицательной, следовательно, Х1>= 0, X2>=0, ...,Xn>=0.

§3. ............