ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, ТРАНСПОРТНАЯ ЗАДАЧА и др.

 

 

 

 

 

 

Содержание

Введение 2

Глава 1. Линейные математические модели 4

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

1.2. Графический метод решения задачи линейного программирования 7

1.3. Основная задача линейного программирования 14

1.4. Симплекс-метод 17

1.5. Двойственная задача линейного программирования. Экономическая интерпретация 26

1.6. Целочисленное линейное программирование. Метод Гомори 29

Глава 2. Специальные задачи линейного программирования 32

2.1 Построение транспортной модели 32

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

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

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

2.5 Задача о назначениях 53

2.6 Венгерский метод решения задачи о назначениях 55

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

Заключение 64 Список литературы 65

В ведение

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

Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо выбрать оптимальный план, основываясь не только на интуиции и опыте лица, принимающего решения, а использовать математические расчеты. Среди задач математического программирования самыми простыми (и лучше всего изученными) являются так называемые задачи линейного программирования. Характерно для них то, что показатель эффективности (целевая функция) линейно зависит от элементов решения x₁, x₂, …, x_n. И ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно x₁, x₂, …, x_n.

Такие задачи довольно часто встречаются на практике, на пример, при решении проблем, связанных с распределением ресурсов, планированием производства, организацией работы транспорта и т. д. Это и естественно, так как во многих задачах практики «расходы» и «доходы» линейно зависят от количества закупленных или утилизированных средств (например, суммарная стоимость партии товаров линейно зависит от количества закупленных е единиц; оплата перевозок производится пропорционально весам перевозимых грузов и т. д.).

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

Задачи:

• Рассмотреть задачу линейного программирования в общем виде;

• Рассмотреть графический метод решения и симплекс-метод;

• Изучить задачу целочисленного программирования;

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

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