Решение задач линейного программирования

 

 

 

 

Задаем целевую функцию:

Z(x)=0+50+200+0+200+500+0+350+0=1300

Проверяем решение на оптимальность

Пусть U₁=0, тогда:

U₂=-2

U₃=3

U₄=3

V₁=1

V₂=4

V₃=4

V₄=2

V₅=-3

V₆=1

 

Для каждой незаполненной  клетки таблицы находим оценки _ij= U_i+V_j-C_ij

 

₁₂=10

₁₃=00

₁₄=10

₁₅=-30

₂₁=-40

₂₄=-40

₂₅=-50

₂₆=-50

₃₂=-10

₃₃=-20

₃₆=М0

₄₁=-50

₄₂=10

₄₄=-50

₄₆=-60

 

так как ₁₂,₁₄,₄₂ >0 то решение не оптимальное, его можно улучшить. Для этого строим цикл для клетки max_”+”{}=₁₄=>(1;4) в которую ставим знак «+» добавляем его к заполненным клеткам.

=min_”-“{0;100}=0

 

 

bj ai	50	100	50	100     *	50     Ф	50     *
50	1   -	3   0	4   -	1 0	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   -

 

 

Задаем целевую функцию:

Z(x)=0+50+200+0+200+500+0+350+0=1300

Проверяем решение на оптимальность

Пусть U₁=0, тогда:

U₂=-1

U₃=4

U₄=4

V₁=0

V₂=3

V₃=3

V₄=1

V₅=-4

V₆=1

 

Для каждой незаполненной  клетки таблицы находим оценки _ij= U_i+V_j-C_ij

 

₁₁=-10

₁₂=00

₁₃=-10

₁₅=-40

₂₁=-40

₂₄=-40

₂₅=-50

₂₆=-40

₃₂=-10

₃₃=-20

₃₆=М0

₄₁=-50

₄₂=10

₄₄=-50

₄₆=-50

 

так как ₄₂ >0 то решение не оптимальное, его можно улучшить. Для этого строим цикл для клетки max_”+”{}=₄₂=>(4;2) в которую ставим знак «+» добавляем его к заполненным клеткам.

=min_”-“{50;100}=50

 

bj ai	50	100	50	100     *	50     Ф	50     *
50	1   -	3   -	4   -	1 0	0   -	1 50
100	3   -	2 50	2 50	4   -	0   -	4   -
150	4 50	8   -	9   -	5 100	0 0	M   -
100	9   -	6 50	7	10   -	0 50	10   -

 

 

 

Задаем целевую функцию:

Z(x)=0+50+100+100+200+500+0+300+0=1250

Проверяем решение на оптимальность

Пусть U₁=0, тогда:

U₂=0

U₃=4

U₄=4

V₁=0

V₂=2

V₃=2

V₄=1

V₅=-4

V₆=1

 

Для каждой незаполненной  клетки таблицы находим оценки _ij= U_i+V_j-C_ij

 

₁₁=-10

₁₂=-10

₁₃=-20

₁₅=-40

₂₁=-30

₂₄=-30

₂₅=-40

₂₆=-30

₃₂=-20

₃₃=-20

₃₆=М0

₄₁=-50

₄₃=-10

₄₄=-50

₄₆=-50

 

так как < 0, то решение единственное оптимальное. Теперь нужно свернуть таблицу.

 

bj ai	50	100	100	150	50     Ф
50	1	3	4	1 50	0
100	3	2 50	2 50	4	0
150	4 50	8	9	5 100	0 0
100	9	6 50	7 50	10	0 50

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Z(x)=50+100+100+200+500+300+350+0=1600

 

Ответ: min Z(Х)=1600 при x= 

 

 

2.8 Вывод

Для обеспечения минимальных  затрат при поставке лекарств в больницы города, необходимо:

1. Со склада АС №1 поставить в аптеку больницы №50 50 ед. лекарства
2. Со склада Фарма К. поставить в аптеки больниц №7 и №23 по 50 ед. лекарства
3. Со склада ПРОТЕК в аптеку больницы №15 поставить 50 ед. лекарства, а в аптеку больницы №50 100 ед. лекарства
4. Со склада ФАРМАКОР поставить в аптеку больниц №7 и №23 по 50 ед. лекарства. 
   

ЗАКЛЮЧЕНИЕ

 

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

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

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

 

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

 

1. Агальцов В.П. «Математические методы в программирование». – М., 2009
2. Банди Б. «Основы линейного программирования». — Радио и связь, 1989.
3. Ашманов С. А. «Линейное программирование». — Наука. Главная редакция физико-математической литературы, 1981.
4. Булдаев А.С. «Двойственные методы решения задачи линейного программирования». - Иркутск, 2000.