Реализация транспортной задачи линейного программирования в системе Android

 

Рис.2.  Пользовательский интерфейс Symbian OS

 

Google Android

Google Android – стек приложений  для мобильных устройств, включающий  операционную систему (на базе  ядра Linux), промежуточное программное  обеспечение (middleware) и сервисные  программы. Система Android разработана  фирмой Android, Inc., приобретенной компанией  Google (2005). В настоящее время это  четвертая по популярности ОС  для смартфонов в США. Важной  особенностью Google Android является то, что сервисные программы и  библиотеки этой системы написаны  на Java.

Прежде всего, Google Android привлекает пользователей своим удобным  и эстетичным пользовательским интерфейсом, который разработан с использованием двумерной и трехмерной графики (библиотеки OpenGL). Основные возможности  системы следующие:

• СУБД SQLite для хранения данных;

• Поддерживаемые сетевые технологии: GSM/EDGE, IDEN, CDMA, EV-DO, UMTS, Bluetooth, Wi-Fi, WiMAX, Bluetooth 2.0;

• Обмен сообщениями SMS и MMS;
• Web-браузер на базе WebKit Application Framework.

Поддержка Java. Фирма Google по принципиальным соображениям использует в системе Android собственную реализацию Java – Dalvik Virtual Machine, разработанную специально для мобильных устройств. По мнению специалистов Google, cтандарт Java Micro Edition (JME) устарел, так как рассчитан на устаревшие типы мобильных устройств и их технические возможности. Поэтому в Google Android стандарт JME не поддерживается.

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

Поддержка разработки приложений. Система Google Android имеет свою собственную  интегрированную среду для разработки приложений - Android SDK, включающий эмулятор мобильных устройств, средства отладки, профилирования, а также plug-in к популярной среде Eclipse для разработки Java-приложений [24].

 

Рис.3. Пользовательский интерфейс Google Android

 

Apple iOS

Apple iOS – мобильная операционная система, разработанная американской компанией Apple на основе Mac OS X первоначально для iPhone, а затем расширена для поддержки таких мобильных устройств, как Apple iPod Touch, iPad и Apple TV. Apple не лицензирует iOS для установки на стороннее оборудование.

Входит  в семейство операционных систем Apple OS X, к которому также относится и Mac OS X — операционная система для настольных и мобильных компьютеров Apple. В Apple iOS используется ядро Darwin (основанное на микроядре Mach), содержащее код как самой Apple, так и код, полученный от NeXTSTEP и FreeBSD. 
iOS имеет четыре слоя абстракции: ядро ОС, сервисы ядра, Media и API (программный интерфейс) Cocoa Touch.

По  состоянию на 7 марта 2012 года магазин приложений Apple App Store содержит более 585 тысяч iOS-приложений, которые все вместе были загружены более чем 25 миллиардов раз [25].

 

Рис.4. Пользовательский интерфейс Apple iOS

 

 Перспективы ОС для мобильных устройств

По данным на 1 квартал 2012 г., 28,9 % смартфонов в мире используют Symbian OS. Для сравнения, показатели использования  других ОС: Bada – 16,7 %, Windows Phone – 8,2 %, Google Android – 44,4 %.

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

• Улучшение и упрощение пользовательского интерфейса;
• Улучшенная графика;
• Более широкие мультимедийные возможности;
• Развитие набора сервисных и игровых программ;
• Обеспечение полной совместимости с настольными компьютерами и с используемыми на них форматами файлов.

 Продолжение и развитие  использования платформы Java для  мобильных устройств; все ведущие  производители мобильных устройств  поддерживают платформу Java, что  является гарантией развития  самой Java-технологии;

 Развитие самих мобильных  устройств: улучшение разрешения  экранов, ускорение процессоров,  увеличение объема памяти, реализация  новых быстрых коммуникационных  технологий, и поддержка этих  новых возможностей в ОС для  мобильных устройств.

 

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

Под названием «транспортная  задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам  линейного программирования и могут  быть решены симплексным методом. Однако матрица системы ограничений  транспортной задачи настолько своеобразна, что для ее решения разработаны  специальные методы. Эти методы, как и симплексный метод, позволяют  найти начальное опорное решение, а затем, улучшая его, получить оптимальное  решение [14].

1. Формулировка транспортной задачи

Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n - стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

    Исходные данные транспортной  задачи обычно записываются в таблице 1.

Таблица 1.

b j  a i	b 1	b 2	…	b n
a 1	с 11	с 12	…	с 1n
a2	с 21	с 22	…	с 2n
…	…	…	…	…
am	с m1	с m1	…	с mn

 

 

    Исходные данные  задачи могут быть представлены  также в виде вектора запасов    поставщиков   А=( ),     вектора    запросов   потребителей

В=( ) и матрицы стоимостей   . 

    В транспортных задачах  под поставщиками и потребителями  понимаются различные промышленные  и сельскохозяйственные предприятия,  заводы, фабрики, слады, магазины  и т.д. Однородными считаются  грузы, которые могут быть перевезены  одним видом транспорта. Под стоимостью  перевозок понимаются тарифы, расстояния, время, расход топлива и т.п [14].

 

Математическая модель транспортной задачи

   Переменными (неизвестными)  транспортной задачи являются  i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

  .

   Так как произведение  определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид

.

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

,   i=1,2,…,m.

   Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

,   j=1, 2, … , n.

   Учитывая условие неотрицательности  объемов перевозок, математическую  модель задачи можно записать  так:

,                                          (1)

,   i=1,2,…,m ,                  (2)

,   j=1, 2, … , n,                                      (3)

,      i=1,2,,…,m,    j=1,2,…,n                       (4)

    В рассмотренной модели  транспортной задачи предполагается, что суммарные запасы поставщиков  равны суммарным запросам потребителей, т.е.  .

    Такая задача называется  задачей с правильным балансом, а ее модель – закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным  балансом, а ее модель – открытой.

    Математическая формулировка  транспортной задачи такова: найти  переменные задачи  ,    i=1,2,,…,m,  j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям не отрицательности (4) и обеспечивающие минимум целевой функции (1).

    Математическая модель  транспортной задачи может быть  записана в векторном виде. Для  этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3):

           

                                            

                .……………………………………………………

      А =                                                 .

               ……………………………………………………..

                                                        

 

  Сверху над каждым столбцом  матрицы указана переменная задачи, коэффициентами при которой являются  элементы соответствующего столбца  в уравнениях системы ограничений.  Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая – на (m+j)-м месте, т.е. 

=         ;     =      .

   Обозначим через  вектор ограничений (правых частей уравнений (2), (3)) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом [14]:

,    

= ,         

,      i=1,2,,…,m,    j=1,2,…,n    

 

Условия разрешимости транспортной  задачи

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

, т.е. задача должна быть  с правильным балансом.

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

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

Число переменных x_ij в транспортной задаче с  m пунктами отправления и   пунктами назначения равно mn, а число уравнений в системе (2)-(4) -  . Так как мы предполагаем выполнение условия , то число линейно независимых уравнений равно  . Следовательно, опорный план может иметь не более   отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности  , то план называется невырожденным, а если меньше - то вырожденным [15].

 

Выбор критерия оптимальности

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

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

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

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