« Решение задачи распределения методом потенциалов

 

 

ЗАДАНИЕ

Для курсового проектирования

По курсу Технология принятия решения

 

Тема задания и исходные данные

« Решение задачи распределения методом потенциалов».

   Задается открытая или закрытая модель. Перед решением открытая модель приводится к закрытой. На каждом шаге на экран выводится:

• решение задачи в виде таблицы;
• значение функции цели;
• потенциалы строк и столбцов;
• матрица оценок свободных клеток базисного решения.

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

 

 

 

 

 

 

 

 

 

Содержание

         Введение……………………………………………………………….

      Глава 1

             Формулировка проблемы в практической области…………………7

      Глава 2

                   Построение моделей транспортной задачи…………………………9

      Глава 3

                   Реализация алгоритма программы……………………………...…...13

                   Руководство пользователя…………………………………………...15

   Заключение……………………………………………………………18

Список  используемой литературы……………………………..……………………19

 

Введение

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

Экономико-математическая модель - это математическое описание экономического процесса или объекта. Такие модели используются для исследований и анализа экономических процессов.

 

Все задачи линейного  программирования можно разделить  на следующие группы:

• задачи об использовании ресурсов, сырья, планирования производства;
• задачи составления рациона
• Задачи об использовании мощностей, загрузке оборудования
• Задачи о раскрое материалов
• Транспортные задачи

 

Их рассмотрение здесь  не приведено, так как не является необходимым для данного проекта.

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

Геометрически область  допустимых решений такой задачи можно представить как многогранник в n мерном пространстве (5)

              (5)

Пример геометрического  представления области допустимых решений задачи, где F - линия целевой  функции, F=0 начальное положение  функции, F=F_max оптимальное положение функции, A, B, C, D, E - вершины многоугольника.

Причём, как правило, оптимальное  решение это одна из его вершин. А поиск оптимума выражается в  переходе от одной вершины к другой и выборе оптимальной.

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

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы  каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F-> max, уменьшение — при отыскании минимума F-> min).

Глава 1

Формулировка  проблемы в практической области

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

Цель работы – определение метода расчета плана перевозки продукции со

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

Формальная (математическая постановка задач)

Задача о размещении (транспортная задача) Это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям. Дана система из m линейных уравнений и неравенств с n переменными:

a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂

_{………………………………………….}

a_k1x₁+a_k2x₂+…+a_knx_n ≤ b_k

_{………………………………………….}

a_m1x₁+a_m2x₂+…+a_mnx_n ≤ b_m1

 

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

F=c₁x₁+c₂x₂+…+c_nx_n     (2)

Необходимо найти такое  решение (план) системы

X=(x₁,x₂….,x_j….,x_n)      (3)

где

x_j <0(j=1,2,…,l, l ≤ n)    (4)

при котором линейная функция F (2) принимает оптимальное), есть максимальное или минимальное в зависимости от задачи) значение. При этом система (1) - система ограничений, а функция F (2) - целевая функция (функция цели).

Анализ  постановки задач и обоснования  метода решения

Анализируя исходные условия задачи, следует отнести  ее к задачам линейного программирования, в частности, к задачам о принятии решений..Наша задача является однокритериальной так как у нас представлены скалярные величины Для решения задачи по оптимальному плану перевозки продукции исользуем метод решения транспортных задач методом потенциалов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2

2. ПОСТРОЕНИЕ МОДЕЛЕЙ ТРАНСПОРТНОЙ ЗАДАЧИ

 Теоретическое введение

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

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

 

Особенности экономико-математической модели транспортной задачи:

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

 

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

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

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

 

Исходные параметры  модели транспортной задачи

1) n– количество пунктов отправления, m – количество пунктов   назначения.

2) a_i– запас продукции в пункте отправления A_i (i=1, n) [ед. прод.].

3) b_j– спрос на продукцию в пункте назначения B_j (j=1,m) [ед. прод.].

4) c_ij– тариф (стоимость) перевозки единицы продукции из пункта отправления a_i в пункт назначения b_j [руб./ед. прод.].

 

Искомые параметры модели транспортной задачи

1) x_ij– количество продукции, перевозимой из пункта отправления a_i в пункт назначения b_j [ед. прод.].

2) L(x)– транспортные расходы на перевозку всей продукции [руб.].

 

Этапы построения модели

I.    Определение переменных.

II.   Проверка сбалансированности задачи.

III.  Построение сбалансированной транспортной матрицы.

IV  Задание целевой функции.

V   Задание ограничений.

 

Транспортная модель

 

;

(4.1)

 

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

Таблица 4.1

Общий вид транспортной матрицы

Пункты отправления, A1	Пункты потребления, Bj				Запасы, ед. прод.
	B1	B2	…	Bm
A1	c11, [руб./ед. прод.]	c12	…	c1m	a1
A2	c21	c22	…	C2m	a2
…	…	…	…	…	…
An	Cn1	Cn2	…	Cnm	an
Потребность ед. прод.	b1	b2	…	bm

 

Из модели (4.1) следует, что сумма  запасов продукции во всех пунктах  отправления должна равняться суммарной  потребности во всех пунктах потребления, т.е.

 

.

(4.2)