Автор работы: Пользователь скрыл имя, 16 Ноября 2012 в 14:56, курсовая работа
Линейное программирование - один из важнейших разделов математики, изучающий теории и методы решения определенных задач. Эта математическая дисциплина стала в последние годы широко применяться в различных областях экономики, техники и военного дела, где в их развитии не последнюю роль играет математическое планирование и использование автоматических цифровых вычислительных машин. Данный раздел науки изучает линейные оптимизационные модели. Иначе говоря, линейное программирование посвящено численному анализу и решению задач, требующих нахождения оптимального значения, т.е. максимума или минимума, некоторой системы показателей в процессе, а состояние его описывает система линейных неравенств.
Введение
Задание
Глава 1. Симплексный метод решения задач линейного программирования
Математическая модель линейного программирования
Стандартная и каноническая форма задачи линейного программирования
Алгоритм решения задачи линейного программирования симплексным
методом
Решение задачи симплексным методом
Вывод
Глава 2. Транспортная задача линейного программирования
2.1 Транспортная задача
2.2 Особенности транспортной задачи с ограничением на пропускную
способность
2.3 Алгоритм решения транспортной задачи
2.4 Методы построения начального опорного решения
2.5 Метод потенциалов
2.6 Переход от одного опорного решения к другому
2.7 Решение транспортной задачи
2.8 Вывод
Заключение
Литература
2.5 Метод потенциалов
Для каждого поставщика и потребителя находят потенциал или силу. Для этого, составляют систему уравнений Ui+Vj=Cij для каждой заполненной решением клетки таблицы. В системе будет (m+n-1) уравнение с m+n неизвестными, то есть неизвестных на одну больше чем уравнений, такая система имеет бесконечное множество решений, по этому, для её решения, одной из переменных, дают конкретное значение (обычно U1=0) и система будет иметь единственное решение.
Потенциалы записываются рядом с таблицей.
Для всех не заполненных решением клеток таблицы, вычисляют оценку ij= Ui+Vj-Cij.
Если всеij0, то решение оптимальное.
Если хотя бы одинij0, то решение не оптимально и его можно улучшить.
2.6 Переход от одного опорного решения к другому
Переход к новому опорному решению, осуществляется с помощью цикла.
Циклом называется такая последовательность клеток таблицы, в которой две и только две соседние клетки, расположенные в одной строке или столбце, причем первая и последняя клетки цикла, так же находится в одной строке или столбце.
Цикл строится для клетки, в которой наибольшая положительная оценка max”+”{}. В эту клетку таблицы ставится знак плюс и она добавляется к заполненным клеткам таблицы (то есть заполненных клеток становится m+n). Затем методом вычеркивания строится цикл.
Метод «вычеркивания»
В таблице можно вычеркнуть те строки и столбцы, в которых по одной заполненной клети таблицы, причем вычеркнутые строки и столбцы уже не учитываются. Оставшиеся клети таблицы после вычеркивания, образуют цикл. В найденном цикле расставляют знаки плюс и минус в нечетных клетках плюсы, а в четных минусы, начиная с уже поставленного знака плюс. По циклу перераспределяется груз величиной =min”-“{xij}. При построении нового решения, все вычеркнутые клетки переписываются без изменения, в клетках со знаком «плюс», величина перевозки увеличивается на , со знаком «минус» уменьшив на при этом одна из помеченных клеток останутся пустой.
2.7 Решение транспортной задачи
|
Склады |
Аптеки больниц |
||||
|
|
№15 |
№7 |
№23 |
№50 |
Запасы |
АС №1 |
1 |
3 |
4 |
1 |
50 |
Фарма К. |
3 |
2 |
2 |
4 |
100 |
ПРОТЕК |
4 |
8 |
9 |
5 |
150 |
ФАРМАКОР |
9 |
6 |
7 |
10 |
150 |
Заявки |
50 |
100 |
100 |
150 |
|
Условие:
Из четырёх аптечных складов города АС №1, Фарма К., ПРОТЕК, ФАРМАКОР надо доставить лекарства в четыре больницы города №15, №7, №23 и №50.
Запасы лекарств на складах, заявки потребителей и тарифы перевозок представлены в транспортной таблице.
Однако имеются дополнительные условия: объём перевозки лекарств со склада ФАРМАКОР больнице №23 должен быть не менее 50 (х43 ≥ 50), а со склада ПРОТЕК больнице №50 – не более 100 (х34 ≤ 100).
Определить минимальный план поставок лекарств в больницы города, обеспечивающий минимальные затраты.
bj ai |
50 |
100 |
100 |
150 |
50 Ф |
|
50 |
1 |
3 |
4 |
1 |
0 |
100 |
3 |
2 |
2 |
4 |
0 |
150 |
4 |
8 |
9 |
5 |
0 |
150 |
9 |
6 |
7 |
10 |
0 |
Проверяем баланс задачи:
=50+100+100+150 = 450
=50+100+100+150 = 400
Т.к. > => вводим фиктивного поставщика b5 = 450 - 400 = 50,
сi5 = 0.
Требуется при решении транспортной задачи ограничить перевозки от поставщика с номером 4 и потребителю с номером 3.
Т.к. x43 ≥ 50, то необходимо прежде, чем решать задачу, сократить запасы 4-го поставщика и запросы 3-го потребителя на величину 50 (т.е. зарезервировать перевозку x43 = 50). В полученном оптимальном решении следует увеличить объем перевозки x43 на величину 50.
bj ai |
50 |
100 |
50 |
150 |
50 Ф |
|
50 |
1 |
3 |
4 |
1 |
0 |
100 |
3 |
2 |
2 |
4 |
0 |
150 |
4 |
8 |
9 |
5 |
0 |
100 |
9 |
6 |
7 |
10 |
0 |
Т.к. x34 ≤ 100, то необходимо вместо одного потребителя с запросами b4 ввести двух других потребителей. Один из них с номером 4 должен иметь запросы b4’ = 100, а другой с номером 6 с запросами b6 = 150 – 100 = 50. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c36, которая принимается равной сколь угодно большому числу M (M>> 1). После получения оптимального решения величины грузов, перевозимых к 6-му потребителю, прибавляются к величинам перевозок 4-го потребителя. Так как c36=M – самая большая стоимость перевозки, то в оптимальном решении клетка с номером (3,6) останется пустой (x36= 0) и объем перевозки x34 не превзойдет 100.
bj ai |
50 |
100 |
50 |
100 * |
50 Ф |
50 * |
|
50 |
1 |
3
|
4
|
1 |
0
|
1 |
100 |
3
|
2 |
2 |
4
|
0
|
4
|
150 |
4
|
8
|
9
|
5 |
0 |
M
|
100 |
9
|
6
|
7 |
10
|
0 |
10 |
Дополнительные условия выполнены, теперь нужно заполнить таблицу и проверить решение на оптимальность. Как только решение будет оптимально, нужно будет свернуть таблицу в исходный вид.
bj ai |
50 |
100 |
50 |
100 * |
50 Ф |
50 * |
|
50 |
1 50 |
3
0 |
4
- |
1 0 |
0
- |
1 + 5 |
100 |
3
- |
2 100 |
2 0 |
4
- |
0
- |
4
1 |
150 |
4
1 |
8
- |
9
- |
5 |
0 |
M
- |
100 |
9
- |
6
1 |
7 50 |
10
- |
0 0
|
10 50 |
m+n-1=4+6-1=9
С=
Задаем целевую функцию:
Z(x)=50+0+200+0+500+0+350+0+
Проверяем решение на оптимальность, для этого:
Пусть U1=0, тогда
12=00
13=-10
15=-40
16=50
21=-30
24=-40
25=-50
26=10
31=10
32=-10
33=-20
36=M0
41=-40
42=10
44=-50
так как 16,26,31,42>0, то решение неоптимальное, его можно улучшить. Для этого строим цикл для клетки max”+”{}=16=>(1;6) в которую ставим знак «+» добавляем его к заполненным клеткам.
=min”-“{0;50;50}=0
bj ai |
50 |
100 |
50 |
100 * |
50 Ф |
50 * |
|
50 |
1 50 |
3
- |
4
- |
1
- |
0
- |
1 0
|
100 |
3
2 |
2 100 |
2 0 |
4
- |
0
- |
4
1 |
150 |
4 6 |
8
- |
9
- |
5 100 |
0 50 |
M
- |
100 |
9
1 |
6
1 |
7 50 |
10
- |
0 0
|
10 50 |
Задаем целевую функцию:
Z(x)=50+0+200+0+500+0+350+0+
Проверяем решение на оптимальность
Пусть U1=0, тогда:
U2=4
U3=9
U4=9
V1=1
V2=-2
V3=-2
V4=-4
V5=-9
V6=1
Для каждой незаполненной клетки таблицы находим оценки ij= Ui+Vj-Cij
12=-50
13=-60
14=-50
15=-90
21=20
24=-40
25=-50
26=10
31=60
32=-10
33=-20
36=M0
41=10
42=10
44=-50
так как 21,26,31,41,42 >0 то решение не оптимальное, его можно улучшить. Для этого строим цикл для клетки max”+”{}=31=>(3;1) в которую ставим знак «+» добавляем его к заполненным клеткам.
=min”-“{50;50;50}=50
bj ai |
50 |
100 |
50 |
100 * |
50 Ф |
50 * |
|
50 |
1 0 |
3
1 |
4
0 |
1 1 |
0
- |
1 50 |
100 |
3
- |
2 100 |
2 0 |
4
- |
0
- |
4
- |
150 |
4 50
|
8
- |
9
- |
5 100 |
0 0 |
M
- |
100 |
9 - |
6
1 |
7 50 |
10
- |
0 50 |
10
- |
Информация о работе Решение задач линейного программирования