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




НазваниеПрактикум по решению линейных задач математического программирования
страница1/11
Дата публикации16.07.2013
Размер0.78 Mb.
ТипДокументы
zadocs.ru > Математика > Документы
  1   2   3   4   5   6   7   8   9   10   11


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ

УНИВЕРСИТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ

Акульшина Т.С., Стебко Т.В.

ПРАКТИКУМ

ПО РЕШЕНИЮ ЛИНЕЙНЫХ ЗАДАЧ

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

г. Симферополь, 2006

УДК 519.35(075)

ББК 22.18 – Я-73

А-44

Акульшина Т.С., Стебко Т.В. Практикум по решению линейных задач математического программирования. – Симферополь, УЭУ, 2006 – 44 с.
Практикум по решению линейных задач математического программирования разработан в помощь студентам всех экономических специальностей при изучении теоретического материала и выполнении самостоятельных, практических и контрольных работ по курсу «Математическое программирование». Включает в себя основные понятия и формулы математического программирования. Содержит разобранные задачи по различным темам дисциплины, а также ряд задач для самостоятельного решения.

Рассмотрено и одобрено на заседании кафедры высшей математики

протокол № 8 от 20 апреля 2006

© Симферополь, 2006.

Введение


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

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

^

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


Сформулируем общую задачу линейного программирования.

Пусть дана система m линейных уравнений и неравенств с n переменными (система ограничений):

(1)

и линейная функция

. (2)

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

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

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

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

Каноническая

Стандартная

Общая

1) Ограничения

Уравнения

,

Неравенства

,

Уравнения и неравенства

,

2) Условия неотрицательности

Все переменные

,

Все переменные

,

Часть переменных

, ,

3) Целевая функция

(max или min)

Здесь: – переменные задачи; – коэффициенты при переменных в целевой функции; – коэффициенты при переменных в основных ограничениях задачи; – правые части ограничений.

Пример. Составить экономико-математическую модель задачи: Для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделия А необходимо: 2 ед. сырья первого вида, 1 ед. второго вида, 2 ед. третьего вида и 1 ед. четвертого вида. Для изготовления изделия В требуется: 3 ед. сырья первого вида, 1 ед. второго вида, 1 ед. третьего вида. Запасы сырья составляют: I вида – 21 ед., II вида – 8 ед., III вида – 12 ед., IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 УДЕ прибыли, а одного изделия типа В – 2 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль.

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

Сырье

Кол-во сырья на ед. продукции, ед.

Запас сырья, ед.

А

В

I

2

3

21

II

1

1

8

III

2

1

12

IV

1



5

Прибыль от ед. продукции, УДЕ

3

2




Пусть – количество изделий типа А и В соответственно, планируемое к выпуску (, ).

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

Составим систему ограничений, используя заданную ограниченность сырья. При планируемых объемах производства расходуется сырья I вида: (ед.), что не должно превышать запас 21 ед. Т.о. получим неравенство: . Составляя неравенства по каждому виду сырья, получим систему:



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



Пример. Составить математическую модель задачи: На четырех станках (I, II, III, IV) обрабатываются два вида деталей (А и В). Каждая деталь проходит обработку на всех станках. Известны время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль, полученная от выпуска одной детали. Данные приведены в таблице:

Станки

Время обработки детали, ч.

Время работы станка

(цикл пр-ва), ч.

А

В

I

1

2

16

II

2

3

26

III

1

1

10

IV

3

1

24

Прибыль от 1 детали, УДЕ

4

1




Составить план производства, обеспечивающий наибольшую прибыль при условии, что количество деталей вида В не должно быть меньше количества деталей вида А.

Решение. Пусть – количество деталей вида А и В соответственно, планируемое к выпуску (, ). Задача аналогична предыдущей, но при составлении модели не следует выпускать из поля зрения фразу: количество деталей вида В не должно быть меньше количества деталей вида А, что математически представимо в виде неравенства: .

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



Любая ЗЛП может быть сведена к канонической, стандартной или общей задаче.

  1   2   3   4   5   6   7   8   9   10   11

Добавить документ в свой блог или на сайт

Похожие:

Практикум по решению линейных задач математического программирования iconРешение задач линейного программирования Цель работы
Цель работы: Изучение возможностей пакета Ms Excel при решении задач линейного программирования. Приобретение навыков решения задач...

Практикум по решению линейных задач математического программирования icon«Медитация ключ к решению жизненных задач»
Авторы книги «Человек Пути» предлагают принять участие в практическом семинаре: «Медитация ключ к решению жизненных задач». Практика...

Практикум по решению линейных задач математического программирования iconКафедра экономико-математических методов и вычислительной техники...
Алгоритм решения задач линейного программирования симплексным методом: Методические указания студентам направления 100700 «Торговое...

Практикум по решению линейных задач математического программирования iconРешение статистических задач в excel практикум Санкт-Петербург 2008...
Статистика. Практикум «Решение статистических задач в excel» для студентов специальности 080105. 65 (060400), 080109. 65 (060500),...

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

Практикум по решению линейных задач математического программирования iconЩербакова Е. И. среди задач по формированию элементарных математи­ческих...

Практикум по решению линейных задач математического программирования iconПонятие программы и программирования. Свойства программ. Назначение...
Системы счисления. Сущность перевода чисел из одной системы счисления в другую: примеры

Практикум по решению линейных задач математического программирования iconПрограммирование для начинающих turbo Pascal 0
В практической части рассмотрены основы алгоритмизации решения задач и их программирования на языке Паскаль. Приводятся примеры разработки...

Практикум по решению линейных задач математического программирования iconШаблон рабочей программы дисциплины Общий физический практикум 2
Общий Физический Практикум является неотъемлемой частью курса "Общая Физика". Основные разделы: механика; молекулярная физика; электродинамика;...

Практикум по решению линейных задач математического программирования iconВиды мультимедиа-устройств
Методические приёмы решения задач при изучении алгоритмизации и программирования

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов