русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 1454; Нарушение авторских прав


 

Поиск оптимальных плановых решений в АСУ можно свести к двум основным постановкам задач:

  1. получение запланированного эффекта при минимуме за­трат;
  2. получение максимального эффекта при использовании за­данных организацией ресурсов.

 

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

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

Все экономические показатели и факторы можно разделить на:

  • неуправляемые (zi,z2,-,Zi,-,Zm)\
  • управляемые (xl,x2,--;Xj,...,xn).

 

На этом основании целевую функцию можно записать в виде уравнения этих показателей с критерием оптимальности (extre-mum).

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

 

Для представления экономической постановки задачи в виде математической модели линейного программирования необходи­мо целевую функцию представить в виде линейной формы, а связь с ограниченными ресурсами описать с помощью линейных уравнений или неравенств. Кроме того, вводится дополнительное ограничение — значения переменных не должны быть отрица­тельны, т.е. x1>0,x2>0,...,Xj>0,...,xn>0. В целом экономи­ко-математическая формулировка и модель общей задачи линей­ного программирования (ОЗЛП) имеют следующий вид: найти max(min) линейной целевой функции:



 

 

при условиях ограничении:

ay, bj, Cj—заданные постоянные величины.

 

Стандартной задачей линейного программирования назы­вают задачу, которая состоит в определении максимального (ми­нимального) значения целевой функций (2.1), при выполнении условия (2.2) и (2.4), где к = 0 и е = п.

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

Совокупность чисел Зс = (д:1,А"2,...,jc„), удовлетворяющих ог­раничениям, называется допустимым решением (или планом).

План х* = (х1*, х2*,хп*), при котором целевая функция за­дачи принимает max(min), называется оптимальным.

В случае, когда требуется найти min функции F(x) =

= (с,л-, 2х2 +... + спхп), можно перейти к нахождению max функции

 

 

Ограничение — неравенство исходной ЗИП, имеющее вид «<», преобразуется в ограничение равенства с добавлением ле­вой части дополнительной неотрицательной переменной. Огра­ничение-неравенство вида «>» преобразуется в ограничение-ра­венство вычитанием из левой части дополнительной неотрица­тельной переменной.

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

Запишем в ОЗЛП ограничения (2.3) в векторной форме.

Х,А| + Х2А2 + ...+ ХпАп = В, (2.5)

где A\,Ai,...,A„ и В m-мерные векторы-столбцы, составленные при неизвестных и свободных членах системы уравнений задачи. План х-(хх2,...,хп)называется опорным планом ОЗЛП,

если система векторов А/, входящих в разложение (2.5) с поло­жительными коэффициентами Xj, линейно независима. Так как векторы Aj являются m-мерными, то из определения опорного плана следует, что число его положительных компонентов может превысить га. Опорный план называется невырожденным, если он содер­жит ровно га положительных компонентов.

Если в опорном плане число положительных компонентов меньше га, то план является вырожденным.

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

 

Пример 1.На предприятии выпускают два вида продукции: мотоциклы и велосипеды. Исходя из возможностей сборочного цеха, в нем могут собирать или 25 мотоциклов в день, или 100 ве­лосипедов в день, либо комбинацию тех и других, определяемую приемлемыми трудозатратами. Склад может принять не более 70 изделий любого вида в сутки. Мотоцикл стоит в 2 раза дороже ве­лосипеда. Требуется определить такой план выпуска продукции, который обеспечил бы предприятию наибольшую выручку.

Обозначим:

X— число выпускаемых мотоциклов в день.

Y— число выпускаемых велосипедов в день.

Т\ — время (в часах) производства одного мотоцикла.

Т2 — время (в часах) производства одного велосипеда.

Из условия задачи следует, что Т\ = 4Т2.

Если завод работает круглосуточно, то при одновременном выпуске обоих изделий

АХ + Y < 24/Т2, но 24/Т2 — max число производимых велосипе­дов, равное 100. Итак: 4Х+ Y < 100.

Еще одно условие — ограниченная емкость склада

Обозначим цену мотоцикла щ (руб.), цену велосипеда — а2 (руб.). По условию: а\ = 2а2.

Следовательно, общая цена дневной продукции S

Поскольку а2 — заданная положительная константа, то наи­большего значения следует добиваться от величины F = 2Х + Y.

Учитывая все условия задачи, приходим к ее математической модели: среди неотрицательных целочисленных решений систе­мы линейных неравенств

 

 

найти такое, которое соответствует максимуму линейной функ­ции F = 2Х + Y. (**)

Проще всего задачу решить геометрически (см. рис. 2.15). Построим на плоскости (х, у) область, соответствующую нера­венствам (*) и условию не отрицательности х и у. Эта область М выделена жирной линией. Всякая ее точка удовлетворяет усло­вию (*) и условию неотрицательности переменных. Пунктирные линии — семейство прямых, удовлетворяющее уравнению (**) (с разными значениями константы с). Вполне очевидно, что наи­большему возможному (max) значению F, вместе с предыдущими условиями, соответствует пунктирная линия, соприкасающаяся с областью М в точке Р. Этой линии соответствует F = 80. Пунк­тирные линии правее и левее не имеют общих точек с жирной линией. Координаты точки Р(10; 60) — искомый оптимальный план производства.

 

 

Пример 2.АО «Садко» ведет ежедневный учет:

  • обьемов выпускаемой продукции (кондитерских изделий — кг/сутки);
  • суммарных затрат на суточный выпуск;
  • выручки и суточного размера прибыли.

Эти данные по каждому цеху ежедневно представляют руко­водству в виде компьютерных распечаток.

Объемы выпуска определяются объемами поставок и стрем­лением получить максимально возможную прибыль при имею­щихся мощностях предприятия.

Вопрос: Оптимальны ли сейчас объемы выпуска?

Оптимизация может быть осуществлена на базе модели ли­нейного программирования. В качестве оптимизируемых пара­метров (управляемых переменных) Х1-Х8 выберем объемы вы­пуска продукции (в кг) из приведенных восьми переменных Xi. Для построения модели получим на основании данных номенкла­туры таблицы удельные показатели производства, рассчитанные на единицу выпуска продукции. Удельная себестоимость опреде­ляется как себестоимость/объем, а удельная прибыль как прибыль/объем.

 


Целевая функция — суммарная себестоимость, которую сле­дует минимизировать:

F (х) = С\ХХ + C2X2 + с3а3 + с4а'4 + CjA'j + с6а6 + С1Х1 + cgag —> 1ТПП

В такой постановке можно прийти к абсурдному выводу, что для достижения абсолютного минимума себестоимости ничего не надо производить. Поэтому следует ввести разумное ограничение — требование обеспечить достижение уровня суммарной суточной прибыли N = 20 569 руб. Ограничение G\(x) запишется так:

Gj (а) = а,а, + а2х2 + «зА3 + а4х4 + а5х5 + а6х6 + а1х1 + а%х% < N.

Математическая постановка задачи: найти управляющие пе­ременные X\-Xiy обеспечивающие минимум целевой функции при выполнении ограничения.

Решение этой задачи в Microsoft Excel с помощью инстру­мента Поиск решения в меню Сервис аналогично приведенно­му в [11].

Анализируя полученные при расчетах данные, можно опре­делить возможности сбыта.

Можно вычислить и альтернативные варианты сбыта.

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

 

Пример 3.Транспортная задача.

Классическая транспортная задача (задача Хитчкока-Куп-манса) — задача о поставке грузов от поставщиков к потребите­лям. Является типовой задачей для промышленных фирм, имею­щих несколько предприятий, рынков сбыта и оптовых баз. Реше­ние сводится к выбору оптимальных маршрутов, особенно когда фирмы ежемесячно пересматривают свои планы распределения продукции и номенклатура заказов меняется. Если нет других приоритетных целей, то задача состоит в том, чтобы минимизи­ровать транспортные расходы.

Например, сталь вырабатывается на т заводах Р\, Р2, Р„. Ежемесячная выработка аи а2, а,„ (т/мес).Сталь надо доста­вить на предприятия Q\,Q2, <2ь причем bub2, bk — ежеме­сячная потребность этих предприятий, с — стоимость перевозки одной тонны стали с завода Р, на предприятие Qj.

Общее производство стали равно суммарной потребности в ней (производство): а\ + а2 + ... + ат = b] + Ь2 + ... + Ьк (потребность).

Необходимо составить план перевозок, при котором:

1) удовлетворялась потребность в стали предприятий <2ь Qi,

.... «2*;

2) с заводов Р„ ...,Рт вывозилась вся сталь;

3) общая стоимость перевозок была минимальной.

Обозначим через Ху количество стали (в тоннах), предназна­ченной к отправке с завода Р, на предприятие Qj. План перевозок состоит из (т; к) неотрицательных чисел Х{] (i = 1, 2, m; j = 1, 2, к). Схему перевозок стали см. в табл. 2.4.

Первое условие примет вид:

 

 

Раз стоимость перевозки одной тонны Р,- в Q, равна Су, то общая стоимость S всех перевозок равна:

 

 

Приходим к чисто математической задаче: Дана система т + к линейных алгебраических уравнений (2.6) и (2.7) с mк неиз­вестными (обычно mк m + к)и линейная функция S (2.8). Тре­буется среди всех неотрицательных решений данной системы найти такое, при котором функция S минимизируется. Практиче­ское значение этой задачи огромно, ее умелое решение в масшта­бах страны могло бы экономить ежегодно огромные средства.

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

 



<== предыдущая лекция | следующая лекция ==>
Краткая характеристика метода исследования операций (ИСО) | Назначение и состав программного обеспечения (ПО)


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.