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

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

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

Решение задач линейного программирования в среде 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=c₁ X₁ +c₂ X₂ +...+c_n X_n ->=max

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

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

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

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

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

а₁₁ Х₁ +a₁₂ X₂ +...+a_1n X_n - объём первого ресурса, который требуется на изготовление продукции, следовательно, мы имеем следующее ограничение:

а₁₁ Х₁ +а₁₂ +...+а_1n X_n <= b₁

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

а₂₁ Х₁ +а₂₂ +...+а_2n X_n <=b₂

а₃₁ Х₁ +а₃₂ +...+а_3n X_n <=b₃

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

а_m1 Х₁ +а_m2 +...+a_mn X_n <=b_m

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

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

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать