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

U_i + V_j. =С_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

И в данном случае мы имеем базисные переменные – X₁₁,, X₂₁, X₂₂, X₂₃, X₃₃ и X₃₄.

И небазисные переменные - X₁₂, X₁₃, X₁₄, X₃₁, X₂₄ и X₃₂.

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

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

С₁₁=20

С₂₁=10

С₂₂=25

С₂₃=25

С₃₃=30

С₃₄=20

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

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

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

60-	Xij+
10+	50	40-
50	30

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

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

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

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

20	40
50	50
50	30

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

С₁₁=20

С₁₃=15

С₂₂=25

С₂₃=25

С₃₃=30

С₃₄=20

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

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

Таблица 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;