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

Составим двойственную задачу

1.  ,   - любые

2.     

3. 

Пусть есть план   

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

  если  ;                                                 (5)

 если  .                                                    (6)

числа u_i и v_j   называются потенциалами пунктов отправления A_i и назначения B_j соответственно.

Сформулированная теорема  позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит  в следующем. Пусть одним из рассмотренных  выше методов найден опорный план. Для этого плана, в котором  базисных клеток, можно определить потенциалы u_i и v_j так, чтобы выполнялось условие (5). Поскольку система (2)-(4) содержит   уравнений и   неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из   уравнений (5) определяются остальные потенциалы и для каждой из свободных клеток вычисляются величины . Если оказалось, что , то план оптимален. Если же хотя бы в одной свободной клетке  , то план не является оптимальным и может быть улучшен путем переноса по циклу, соответствующему данной свободной клетке.

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

Процесс улучшения плана  продолжается до тех пор, пока не будут  выполнены условия (6) [15].

4. Алгоритм решения транспортной задачи методом потенциалов

Порядок решения транспортной задачи методом потенциалов следующий:

1. Проверяют выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводят фиктивного поставщика или потребителя с недостающими запасами или запросами и нулевыми стоимостями перевозок.
2. Строят начальное опорное решение (методом минимальной стоимости или каким-либо другим методом) и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть ) и убеждаются в линейной независимости векторов-условий (методом вычеркивания).
3. Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений + = при >0. Для того чтобы найти частное решение системы, одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам 

= - при >0,                                           (7)

если известен потенциал  , и

= - при >0,                                          (8)

если известен потенциал   .

4. Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам = + - и те оценки, которые больше нуля, записывают в левые нижние углы клеток. Если для всех свободных клеток 0, то вычисляют значение целевой функции, и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, то опорное решение не является оптимальным.
5. Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка max{ }= . Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным . Далее возвращаемся к пункту 3 алгоритма.

 

ГЛАВА 3. СОЗДАНИЕ ПРИЛОЖЕНИЯ

В данной работе мы будем  показывать примеры на устройстве Sony Ericsson Xperia Pro.

1. Информация о Sony Ericsson Xperia Pro

Общее

Производитель:     Sony Ericsson

Модель:      XPERIA pro

Другие названия:     MK16i, Iyokan

Год выпуска:      2011

Опер. сист.:      Android 2.3

Емкость аккум. (мА·ч):    1500

Размеры

Габариты (мм):

(ширина х высота х  толщина)   57 x 120 x 13.7

Вес (г):      140

Процессор

Тип процессора:     Qualcomm Snapdragon MSM8255

Тактовая частота (МГц):    1000

Память

Оперативная память (Мб):    512

Flash-память (Гб):     1

Коммуникации

Телефон: GSM 850, GSM 900, GSM 1800, GSM 1900, UMTS 900, UMTS 2100

Bluetooth:      2.1

Wi-Fi:       802.11b,g,n

Другое: GPRS, EDGE, HSDPA, HSUPA, UMTS/WCDMA, GPS

Дополнительно:     DLNA

Мультимедиа

Размер экрана:     3.7

Разрешение экрана (px):    480 x 854

Тип экрана: TFT

Видеоускоритель:     Adreno 205

Камера сзади (Мп):     8

Автофокус:      Есть

Фотовспышка:     Есть

Камера спереди (Мп):    0.3

Динамик:      моно

Выход наушников:     3.5

Другое: G-Sensor, Датчик освещенности, Датчик приближения, Цифровой компас, FM-радио

Управление и  ввод

Сенсорный экран:     ёмкостный

Кнопки: физические кнопки, QWERTY-клавиатура

Расширение

Карты памяти:     microSD, microSDHC

Разъемы:      microUSB, microHDMI

Дополнительно

Время работы: В режиме разговора до 7 ч, в режиме ожидания - до 430/400 ч (2G/3G)

Особенности: Камера имеет сенсор Sony Exmor R, экран с технологией Mobile BRAVIA Engine [16].

2. Среда разработки Eclipse и Android SDK

Eclipse — свободная интегрированная среда разработки модульных кроссплатформенных приложений. Развивается и поддерживается Eclipse Foundation.

Наиболее известные приложения на основе Eclipse Platform — различные «Eclipse IDE» для разработки ПО на множестве языков (например, наиболее популярный «Java IDE», поддерживавшийся изначально, не полагается на какие-либо закрытые расширения, использует стандартный открытый API для доступа к Eclipse Platform).

Eclipse — в первую очередь полноценная Java IDE, нацеленная на групповую разработку: среда интегрирована с системами управления версиями — CVS в основной поставке, для других систем (например, Subversion, MS SourceSafe) существуют плагины. В силу бесплатности и высокого качества, Eclipse во многих организациях является корпоративным стандартом для разработки приложений.

Второе назначение Eclipse — служить платформой для разработки новых расширений, чем он и завоевал популярность: любой разработчик может расширить Eclipse своими модулями. Уже существуют C/C++ Development Tools (CDT), разрабатываемые инженерами QNX совместно с IBM, и средства для языков COBOL, FORTRAN, PHP и пр. от различных разработчиков. Множество расширений дополняет среду Eclipse менеджерами для работы с базами данных, серверами приложений и др.

Eclipse написана на Java, потому является платформо-независимым продуктом, за исключением библиотеки SWT, которая разрабатывается для всех распространённых платформ (см. ниже). Библиотека SWT используется вместо стандартной для Java библиотеки Swing. Она полностью опирается на нижележащую платформу (операционную систему), что обеспечивает быстроту и натуральный внешний вид пользовательского интерфейса, но иногда вызывает на разных платформах проблемы совместимости и устойчивости приложений [20].

 

Android SDK - программа, представляющая  собой своеобразный эмулятор  популярной мобильной платформы  Android, часто встречающейся в смартфонах  и коммуникаторах. Установив на  персональный компьютер программу-эмулятор  можно тестировать скачанные  приложения для мобильных устройств  ещё до их непосредственной  загрузки в память смартфона.  Это очень полезно особенно  для разработчиков, ведь им  не приходится, каждый раз внося  изменения в софт, закачивать  его на мобильное устройство.

Для рядовых пользователей  программа Android SDK также окажется очень  привлекательной находкой, ведь любители игр на смартфоне могут присмотреться  к скачанной новинке ещё на компьютере, чтобы не устанавливать  в мобильное устройство те приложения, которые не пригодятся.

 

Особенности программы Android SDK:

1. польза для разработчиков софта под платформу Android;
2. пользователи могут ознакомиться с программами для смартфона ещё до их непосредственной установки в гаджет;
3. легко устанавливается на ПК и не требует высокой мощности компьютера;
4. немного сложный интерфейс;
5. некоторые приложения могут не запуститься по причине несовместимости;
6. небольшой перечень возможностей [21].

 

 

Для разработки приложений для платформы Google Android нам потребуется:

• Платформа Eclipse.

Eclipse – это платформа, на которой работает плагин. Загрузите последнюю версию Eclipse Classic;

• Android Developer Tools.

Этот Eclipse-плагин можно установить, руководствуясь инструкциями по установке Android SDK;

• Исходный код.

 

Рис.7. Интерфейс программы Eclipse

 

 

3. Процесс создания приложения

Скачиваем и устанавливаем  программу Eclipse и  Android SDK. Дале создаем эмулятор, в котором мы будет тестировать наше приложение.

Запускаем установленное  приложение Eclipse.

Нажимаем File -> New Project. Нажимаем на папку Android -> Android Project.

 

 
Poject Name: Transport_Task

 

Указываем версию Android под которую мы разрабатываем приложение. В моем случае это Android 2.3.3

 
Package Name: trans.wert1go.namespace

 
Нажимаем Finish!  
Наш проект успешно создан.

Открываем файл res -> layout -> main.xml. Выделяем строку с текстом «Hello World, First_app Activity и удаляем ее. Нажимаем на вкладу xml и добавляем кнопку и немного текста:

<?xml version="1.0" encoding="utf-8"?>

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"

    android:layout_width="fill_parent"

    android:layout_height="fill_parent"

    android:background="#E5E1E2"

    android:orientation="vertical"

    android:paddingLeft="20dip"

    android:paddingRight="20dip" >

 

    <Button

        android:id="@+id/start"

        android:layout_width="fill_parent"

        android:layout_height="wrap_content"

        android:layout_centerInParent="true"

        android:text="@string/start_button" />

 

    <TextView

        android:id="@+id/textView1"

        android:layout_width="wrap_content"

        android:layout_height="wrap_content"

        android:layout_alignParentTop="true"

        android:layout_centerHorizontal="true"

        android:layout_marginTop="87dp"

        android:text="Транспортная задача"

        android:textAppearance="?android:attr/textAppearanceLarge"

        android:textColor="#000000" />

    <TextView

        android:id="@+id/textView2"

        android:layout_width="wrap_content"

        android:layout_height="wrap_content"

        android:layout_alignParentBottom="true"

        android:layout_alignRight="@+id/textView1"

        android:layout_marginBottom="74dp"

        android:text="Работу выполнил:"

        android:textColor="#000000" />

    <TextView

        android:id="@+id/textView3"

        android:layout_width="wrap_content"

        android:layout_height="wrap_content"

        android:layout_alignLeft="@+id/textView2"

        android:layout_alignTop="@+id/textView2"

        android:layout_marginTop="26dp"

        android:text="Васильев Бронислав"

        android:textColor="#000000" />

</RelativeLayout>

Получается такая картина:

 

 

Открываем файл src - > trans.wert1go.namespace -> TransActovity.java Добавляем код:

package trans.wert1go.namespace;

 

import android.app.Activity;

import android.content.Intent;

import android.os.Bundle;

import android.view.View;

import android.view.View.OnClickListener;

 

public class TransActivity extends Activity implements

android.view.View.OnClickListener {

/** Called when the activity is first created. */

@Override

public void onCreate(Bundle savedInstanceState) {

super.onCreate(savedInstanceState);

setContentView(R.layout.main);

View mStartButton = findViewById(R.id.start);

mStartButton.setOnClickListener((OnClickListener) this);

}

 

@Override

public void onClick(View view) {

Intent intent = new Intent(this, solve.class);

startActivity(intent);