Метод оптимальных решений

Заключение

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

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

Моделирование:

является одним из ключевых видов  деятельности человека;

всегда в той или иной форме  предшествует любому делу;

занимает центральное место  в исследовании объекта; позволяет

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

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

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

Список использованной литературы

1. Алгебра и начала анализа  : Учеб. для 10-11 кл. сред. шк./ Ш. А.  Алимов, Ю. М. Колягин, Ю.В. Сидоров  и др. - М.: Просвещение, 1993. - 254 c.

2. Башмаков, М. И. Алгебра и  начала анализа : Учеб. для 10-11 кл. сред. шк. - М.: Просвещение, 1992. - 351 с.

3. Вольтерра В. Математическая  теория борьбы за существование.  М.: Наука, 1976.

4. Зельдович Я.Б., Яглом И.М. «Высшая  математика для начинающих физиков  и техников». М.: Наука, 1982.

5. Задачник по курсу математического  анализа : Уч. пособие для студентов  заочн. отделений физ.-мат. фак-тов  пединститутов. Ч. I// Под ред. Н.  Я. Виленкина. - М.: Просвещение, 1971. - 343 с.

6. Колмогоров, А. Н. Алгебра и  начала анализа : Учеб. для 10-11 кл. общеобразоват. учреждений/ А.  Н. Колмогоров, А. М. Абрамов,  Ю. П. Дудницын и др. - М.: Просвещение, 1998. - 365 c.

7. Модели и моделирование в  методике обучения физике : Материалы  докладов республиканской научно-теоретической  конференции. - Киров: Изд-во Вятского  ГПУ, 2000. - 90 с.

8. Мордкович, А. Г. Алгебра  и начала анализа: Учеб. для  10-11 кл. общеобразоват. учреждений. Ч. I. - М.: Мнемозина, 2003. - 375 с.

9. Никольский, С. М. Алгебра и  начала анализа : Учеб. для 11 класса  общеобразоват. учреждений/ С. М.  Никольский, М. К. Потапов. - М.: Просвещение, 2003.

8. Пискунов. Н.С. Дифференциальное  и интегральное исчисление для  втузов. Том 2. М.: Наука, 1978.- 267с.

9. Уильямсон М.Г.. Анализ биологических  популяций. М.: Мир, 1975.

10. Филиппов А.Ф. Сборник задач  по дифференциальным уравнениям. М.: Наука, 1992.

11. Шубин М. А. «Математический  анализ для решения физических  задач» М., МЦНМО, 2003

 

 

 

 

 

 

 

 

 

4. СПЕЦИАЛЬНЫЕ  ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

4.1. Построение транспортной модели

4.2. Сбалансированные и несбалансированные транспортные модели

4.3. Определение начального плана  транспортировок. Методы «северо-западного» угла, минимального элемента, 
       Фогеля

4.4. Оптимальный план транспортной  задачи.  Метод потенциалов

4.5. Экономические задачи, сводящиеся к транспортным моделям

4.6. Задача о назначениях

4.7. Применение задачи о назначениях  к решению экономических проблем  

 

Срди задач линейной оптимизации  могут быть выделены два класса задач  со специальной структурой: транспортная задача и задача о назначениях. Эти  задачи используются для моделировали оптимизации экономических проблем, связанных с формированием оптимального плана перевозок, оптимального распределения  индивидуальных контрактов на транспортировки, составления оптимального штатного расписания, определения оптимальной  специализации предприятий, рабочих  участков и станков, оптимального назначения кандидатов на работы, оптимального использования  торговых агентов. Критерием эффективности  в данных задачах является линейная функция, ограничения также линейны, поэтому для их решения могут  применяться методы линейной оптимизации, например симплекс-метод. Однако специальная  структура таких задач позволяет  разработать более удобные методы их решения. Некоторые из таких методов  приведены этой книге. Даны общая  формулировка задач, основные термины  и определения, этапы построения математических моделей, этапы получения  оптимальных решений. Также приведены  числовые примеры экономических  задач, которые могут быть решены этими методами. 

 

4.1. Построение  транспортной модели

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

Пример 4.1

Четыре предприятия данного  экономического района для производства продукции используют некоторое  сырье. Спрос на сырье каждого  из предприятий соответственно составляет: 120, 50, 190 и 110 усл. ед. Сырье сосредоточено  в трех местах. Предложения поставщиков  сырья равны: 160, 140 и 170 усл. ед. На каждое предприятие сырье может завозиться от любого поставщика. Тарифы перевозок  известны и задаются матрицей

В i -й строке j -м столбце матрицы С стоит тариф на перевозку сырья от i -гo поставщика j -му потребителю, i =1, 2, 3; j =1, 2, 3, 4. Под тарифом понимается стоимость перевозки единицы сырья.

Требуется составить план перевозок, при котором общая  стоимость перевозок минимальна.

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

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

Пусть х_ij – количество сырья, перевозимого от i -го поставщика j-му потребителю. Параметры задачи – число поставщиков и потребителей, предложение и спрос сырья в каждом пункте, тарифы на перевозки.

Ограничения задачи – это  ограничения на предложение и  спрос сырья. Предложения сырья  всех поставщиков не должны быть меньше суммарного спроса на него во всех пунктах  потребления. В данной задаче имеет  место точное равенство между  предложением и спросом. 120+50+190+110=160+140+170=470.

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

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

Окончательно математическая модель задачи имеет вид

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

4.2. Сбалансированные  и несбалансированные  транспортные модели

В общем случае транспортная задача имеет следующий вид: дано т поставщиков продукции одного вида и п потребителей; предложение каждого i-го поставщика составляет a_i единиц,  ; спрос каждого j-го потребителя – b_j единиц,  тарифы перевозок равны с_ij,  , Требуется определить оптимальный план перевозок продукции (т. е. количество продукции, перевозимой от каждого поставщика каждому потребителю), и котором суммарная стоимость перевозок минимальна. Заметим, что транспортная модель строится при условии линейной зависимости стоимости перевозок от количества перевозимой продукции.

Пусть х_ij – количество продукции, перевозимой от i -го поставщика  
j-му потребителю  ;

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

                                                  (4.1)

                                          

 

Определение 4.1                              

Совокупность  чисел ( ), ; ; удовлетворяющая ограничениям (4.2)–(4.5), называется планом перевозок или планом транспортной задачи.

Решить транспортную задачу – это значит найти такие значения   ( ; ), которые удовлетворяют ограничениям (4.2)–(4.5) и доставляют минимум целевой функции (3.3.1). Целевая функция (4.1) определяет суммарную стоимость перевозок. Ограничения (4.2) соответствуют тому, что количество продукции, вывозимой от i-го поставщика, не должно превосходить предложения i-го поставщика (для всех поставщиков). Ограничения (4.3) соответствуют тому, что количество продукции, ввозимой j-му потребителю, должно полностью удовлетворять спросу j-го потребителя (для всех потребителей). Ограничения (4.4) соответствуют тому, что суммарное предложение не должно быть меньше суммарного спроса.

Определение 4.2

Задача (4.1)–(4.5) называется несбалансированной транспортной моделью (задачей).

Определение 4.3

Задача (4.1)–(4.5), в которой ограничения (4.2)–(4.4) имеют вид равенств, называется сбалансированной транспортной моделью (задачей).

Покажем, что любую несбалансированную транспортную модель можно свести к  сбалансированной.

Пусть суммарное предложение  больше суммарного спроса, т. е.

                                            (4.6)

Введем фиктивного (n+1)-гo потребителя, спрос которого

Тариф на перевозку  этому потребителю от всех поставщиков  равен 0.

Очевидно, при  этом неравенства (4.2) и (43) перейдут в  равенство, и к ним добавится  ограничение (равенство) для (n+1)-го пункта потребления.

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

                                         (4.7)

Транспортные задачи, содержащие ограничение (4.7), также являются несбалансированными  и могут быть сведены к сбалансированным с помощью ввода фиктивного (m+1)-го поставщика, предложение которого

стоимость перевозки от (m + 1)-го поставщика нулевая,

Неравенство (4.7) перейдет в  равенство

Рассмотрим сбалансированную транспортную задачу

                                         (4.8)

                                     

 

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

Для решения транспортной задачи составляют транспортную таблицу (табл. 4.1).

Таблица 4.1 

 

 

  

 

Номер поставщика	Номер потребителя						Предложение
	1	2	…	j    ■	...	п
1	c11	c12	...	c1j	...	c1n	a1
2	c21	с22	…	c2j		c2n	a2
...	...	...	…	...	...	...	...
i	ci1	ci2	…	cij	...	cin	aJ
…	…	…	…	…	…	…	…
m	cm1	cm2	…	cmj	…	cmn	am
Спрос	b1	b2	…	bJ	…	bn