Смекни!
smekni.com

Решение транспортной задачи 3 (стр. 2 из 3)

Ui + Vj. ij. (6)

Оценки для небазисных переменных определяются исходя из формулы:

. (7)

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

Не существенно, в каком направлении происходит обход цикла. Для каждого базисного переменного и соответствующей небазисной переменной можно построить только один цикл. После построения цикла вводимой небазисной переменной ставится в соответствие знака «+», далее базисным переменным, находящимся в узлах цикла ставятся поочередно знаки «-» и «+». Выводимой переменной считается базисная переменная, имеющая минимальное значение на местах со знаком «-». Далее к базисным переменным, находящимся на местах со знаком «+» прибавляется это значение, из переменных со знаком «-» – вычитается. Вводимой переменной присваивается найденное минимальное значение. После снова производятся оценки базисных и небазисных переменных и устанавливается, выполнены ли условия оптимальности. 3 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯРассмотрим основные алгоритм решения задачи. Он состоит из следующего:· нахождение начального базисного решения,· из число небазисных переменных выделяем переменную вводимую в базис, проверяем условия оптимальности, если они удовлетворены то заканчиваем расчет, если нет – переходим к следующему шагу,· из числа базисных переменных выделяем выводимую из базиса, находим новое базисное решение и возвращаемся ко второму шагу.

Далее приведены основные шаги алгоритма и демонстрация их на примере

который представлен в данной курсовой работе как тестовый пример.

Данные приведены в таблице 1.

Таблица 1. Исходные данные

Фабрика Склады (расходы на 1 партию) Предложение
Г Д Е Ж
А 20 40 15 30 60
Б 10 25 25 35 100
В 15 45 30 20 80
Спрос 70 50 90 30 240

Шаг 1. Находим начальное допустимое решение. Как уже сказано выше в данной курсовой ра­боте для отыскания начального решения будем применять про­цедуру северо-западного угла (табл. 2).

Таблица 2.

60
10 50 40
50 30

И в данном случае мы имеем базисные переменные – X11,, X21, X22, X23, X33 и X34.

И небазисные переменные - X12, X13, X14, X31, X24 и X32.

Шаг 2. Выделить из числа небазисных переменных переменную, кото­рую введем в базис.

Оценки для базисных переменных:

С11=20

С21=10

С22=25

С23=25

С33=30

С34=20

Обычно полагают что U1=0. Оценки для небазисных переменных определяются в соответствии с отношением:

Имеем переменную с наибольшим положительным значением X13=20, которую и будем вводить в базис (табл. 3).

Таблица 3. Построение цикла

60-
Xij+
10+
50 40-
50 30

Далее переходим к «шагу 3».

Шаг 3. Выбираем выводимую из базиса переменную из числа перемен­ных текущего базиса. Затем находим новое базисное решение и вернутся к «шагу 2».

X23 – выводим эту переменную из базиса.

Таблица 4. Новое базисное решение

20 40
50 50
50 30

Оценки для базисных переменных:

С11=20

С13=15

С22=25

С23=25

С33=30

С34=20

Оценки для небазисных переменных:

X11 – выводим эту переменную из базиса, а X31 – вводим в базис.

Таблица 5. Новое базисное решение

60
50 50
20 30 30

Данное решение будет оптимальным.

Оптимальное решение будет формулироваться следующим образом: общие расходы составят 4450 у.е., а маршруты будут таковы:

1-ая фабрика поставила товар в 3-й склад (1-й маршрут),

2-ая фабрика поставила товар в 1-й 2-й склады (2-й маршрут),

3-ая фабрика поставила товар в 1-й 3-й 4-й склады (3-й маршрут).

Алгоритм решения задачи можно представить в виде блок-схемы пред­ставленной в приложении А.1.

Листинг программы представлен в приложении Б.

4 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

Для входа в программу необходимо запустить файл Transport.exe. После чего на экране появится главное окно программы, изображенное на рисунке 1.

Рисунок 1 - Основное окно программы

В данном окне пользователь может изменять и задавать значения в основных таблицах: «Спрос», «Предложение», «Фабрика» и «Склады».На панели расположены основные элементы управления:· ячейки для задания количества складов и фабрик,· кнопка «Применить» используется для задания вводимых параметров,· кнопка «По умолчанию» используется для задания значений по умолчанию,· кнопка «Решить» используется для вычисления результата,· кнопка «Задание» выводит окно с содержание задания к курсовой работе. Ответ пользователь может прочитать из текстового поля. Применение всех возможностей можно просмотреть на рисунке 2.
Рисунок 2 – Работа программы.

Для работы с программой необходимы минимальные аппаратные требования:

1) разрешение экрана − 800*600;

2) цветопередача − 16 бит;

4) память − 12 Mb;

6) PentiumII 400 MHz;

7) клавиатура;

8) мышь;

9) MicrosoftWindows 98 и выше;

ЗАКЛЮЧЕНИЕВ процессе работы были рассмотрены и изучены такие понятия как транспортная задача, основные методы решения транспортных задач, а так же был произведен расчет тестового примера. Для оптимизации расчетов и для уменьшении погрешностей вычислений был создан программный модуль в программной среде Delphi 7 под названием Transport.exe, который может использоваться как совместно с другими модулями, так и быть самостоятельным программным продуктом. БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ашманов С.А. Линейное программирование/ С.А Ашманов – М.: Наука. Главная редакция физико-математической литературы, 1981. - 340 с.

2. Вентцтель Е.С. Исследование операций. Задачи, примеры, методология: Учеб. пособие для студентов ВТУЗОВ – М. Высш. шк., 2001 – 208 с.

3. Бобровский С. Delphi 7/ С. Бобровский – СПб.: Питер, 2006. –736 с.

4. Исследование операций. /Под ред. Дж.Моудера и С.Элмаграби/, - М.: Мир, 1981.

5. Эддоус М., Стэнефильд Р. Методы принятия решений / Пер. с англ. Под ред. член-корр. РАН И.И. Елисеевой. – М.: Аудит. ЮНИТИ, 1997. – 590 с.

ПРИЛОЖЕНИЕ А

Блок-схема реализованного алгоритма

Рис А.1 – Блок-схема реализованного алгоритмаПРИЛОЖЕНИЕ БЛистинг программы «Transport»

unit intr;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

Grids, ExtCtrls, StdCtrls, Buttons, Db, DBTables;

type

TForm1 = class(TForm)

tab1: TStringGrid;

Panel1: TPanel;

prdl: TEdit;

spr: TEdit;

spros: TStringGrid;

predl: TStringGrid;

Label1: TLabel;

Label2: TLabel;

Button2: TButton;

Button3: TButton;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label8: TLabel;

Memo1: TMemo;

Button1: TButton;

BitBtn1: TBitBtn;

Label7: TLabel;

Label9: TLabel;

Bevel1: TBevel;

procedure BitBtn1Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

function read_data(): bool;

procedure balans();

procedure First_resh();

procedure find_uv();

procedure xnbmax(var max:real;var xi,yi:integer);

procedure print_tabl();

end;

var

Form1: TForm1;

implementation

uses task, dec;

{$R *.DFM}

var

c: array [1..100, 1..100] of real;