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

     министерство  образования и  науки РФ

     Псковский государственный  университет

     Колледж строительства и экономики 
 
 
 
 

     Курсовая  работа по теме 

     «Разработка программ для решения  задач линейного программирования» 

 

     выполнил

     студент гр.420-ПО

                                                                            Лазаревский Сергей Викторович 

     проверил

     Ушарнова  Татьяна Олеговна 
 
 
 
 
 
 

     Псков 2011

 

      

     Содержание

1. Введение
2. Спецификация
3. Техническая задача
4. Математическая модель
5. Блок схемы решение задач
6. Решение задачи вручную
7. Программный код задачи
8. Локальная оценка задачи
9. Заключение

 

     

     Введение

     Главная цель данной курсовой работы, произвести разработку программного продукта  с помощью языков программирования С++, Delphi, Visual Basic. Разработка программного продукта, это процесс создания программы для её продажи. Сложность разработки программного продукта заключается в, удовлетворении требований заказчика к данному программному продукту. Существуют два метода проектирования программного продукта, по степени автоматизации проектных работ и по подходам к организации процесса создания программного продукта. 

 

Спецификация

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

1. параметры потока (частота обслуживания, вероятность отказа, т.е. вероятность того, что все места в очереди будут заняты).
2. относительную пропускную способность станции.
3. абсолютную пропускную способность станции.
4. вероятность простоя станции.
5. среднее число машин ожидающих ремонта.
6. среднее время нахождения в очереди.
7. среднее время нахождения машины на станции.

 

     Для вычисления характеристики системы обслуживания покупателей в магазине:

1. среднее время ожидания требования в очереди.
2. среднее время нахождения покупателей в магазине.

 

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

 

     

     Техническая задача

     Задача №1.Постановка задачи для вычисления характеристик работы станции технического обслуживания (задача СМО – Марковский процесс системы массового обслуживания). На станцию в случайные моменты времени поступают машины для мелкого ремонта. Станция имеет n технологических линий для ремонта и оборудованную площадку для ожидания, которая вмещает в себя m машин. Требования о ремонте получает отказ, если все места на площадке заняты. На основании статистической обработки наблюдений за потоком машин и временем обслуживания установлено, что поток требований на обслуживание – простейший с интенсивностью λ машин в час, а время обслуживания распределено по показательному закону со средним значением _обс.  машины в час.

           Найти характеристики работы  станции:

1. параметры потока (частота обслуживания, вероятность отказа, т.е. вероятность того, что все места в очереди будут заняты).
2. относительную пропускную способность станции.
3. абсолютную пропускную способность станции.
4. вероятность простоя станции.
5. среднее число машин ожидающих ремонта.
6. среднее время нахождения в очереди.
7. среднее время нахождения машины на станции.

 

     Исходные  данные для решения задачи приведены  в следующей таблице:

 

 

     

     Задача №2.  Постановка задачи для вычисления основных характеристик обслуживания покупателей в магазине (задача СМО). В магазине покупатели появляются в случайные моменты времени, распределённые по экспоненциальному закону с интенсивностью (параметром) λ. В магазине обслуживает один продавец, при этом длительность обслуживания распределена по нормальному закону со средним значением (математическим ожиданием) М дисперсией D. Требуется рассмотреть процесс обслуживания за t часов работы магазина. Найти характеристики системы обслуживания:

1. среднее время ожидания требования в очереди.
2. среднее время нахождения покупателей в магазине.

     Исходные  данные для решения задачи приведены  в следующей таблице:

 

     Задача№3. Постановка задачи планирования производства (симплекс метод).

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

 

     Исходные  данные для решения задачи приведены  в виде системы уравнений и  целевой функции: 

      28x₁ + 5x₂ + 3x₃ + 10x₄ +18x₅ + 14x₆ + 12x₇ + 5x₈ + 9x₉ + 18x₁₀ = 1763

     15x₁ + 8x₂ + 4x₃ + 20x₄ +15x₅ + 16x₆ +13x₇ + 8x₈ + 17x₉ + 17x₁₀ =1870

     30x₁ + 10x₂ + 8x₃ +12x₄ +13x₅ +15x₆ + 12x₇ + 3x₈ + 13x₉ + 15x₁₀ =1885

     25x₁ +14x₂ + 7x₃ + 22x₄ + 17x₅ + 13x₆ + 14x₇ +5x₈ +15x₉ + 16x₁₀ =1946

     12x₁ + 7x₂ + 5x₃ +16x₄ + 15x₅ + 10x₆ +16x₇ + 4x₈ + 12x₉ + 18x₁₀ =1591

     6x₁ + 3x₂ + 9x₃ +5x₄ +16x₅ + 12x₆ + 17x₇ + 7x₈ + 16x₉ + 7x₁₀ =1433

     20x₁ + 16x₂ +6x₃ +14x₄ + 7x₅ + 11x₆ + 4x₇ + 10x₈ + 14x₉ + 4x₁₀ =1501

     F(x) = 130x₁ + 215x₂ + 250x₃ + 105x₄ + 312x₅ + 234x₆ + 206x₇ + 228x₈ + 222x₉ + 145x₁₀

 

     

Математическая  модель

     Формулы

A=ƛ*Q 

Q= 

µ= 

Q=  
 
 
 
 
 

 

     

     Блок  схемы решения задачи

     

        

     

     

     

     

     

     

     

       

     

       
 
 

 

     

     

     

     

     

     

     

     

     

       

     

     

       

 

      Расчет вручную

     Задача  №1.Постановка задачи для вычисления характеристик работы станции технического обслуживания (задача СМО – Марковский процесс системы массового обслуживания). На станцию в случайные моменты времени поступают машины для мелкого ремонта. Станция имеет n технологических линий для ремонта и оборудованную площадку для ожидания, которая вмещает в себя m машин. Требования о ремонте получает отказ, если все места на площадке заняты. На основании статистической обработки наблюдений за потоком машин и временем обслуживания установлено, что поток требований на обслуживание – простейший с интенсивностью λ машин в час, а время обслуживания распределено по показательному закону со средним значением _обс.  машиныв час.

           Найти характеристики работы  станции:

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

 

     Λ=0,75 авто/ч

     n=2 линий для ремонта

     t_обс=1 ч

     m=2 авто

     µ=1/1=1 авто/ч

     q=1/1=1

     p₀=(1+1+1²/2!)^-1=(2+1/2)^-1=(5/2)^-1=2/5=0,2 (20%)

     P_отк=(1²/2!)*0,2=((1*0,2(/2)=0,1(10%)

     Q=1-0,1=0,9 (90%) (относительная пропускная способность станции обслуживания)

     А=0,9 (абсолютная пропускная способность станции обслуживания)

     =0,9/1=0,9 (среднее число занятых линий для ремонта)

     Ответ: станция обслуживания простаивает 20% времени, вероятность отказа обслуживания заявки 10%  времени, среднее число обслуженных заявок в час 0,9 заявок, что составляет 90%, среднее число занятых линий обслуживания 0.9, т.е каждая из линий обслуживания будет занята обслуживанием заявок в среднем лишь 45%. 

 

 

     Задача 2. Постановка задачи для вычисления основных характеристик обслуживания покупателей в магазине (задача СМО). В магазине покупатели появляются в случайные моменты времени, распределённые по экспоненциальному закону с интенсивностью (параметром) λ. В магазине обслуживает один продавец, при этом длительность обслуживания распределена по нормальному закону со средним значением (математическим ожиданием) М дисперсией D. Требуется рассмотреть процесс обслуживания за t часов работы магазина. Найти характеристики системы обслуживания: