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 с.
ПРИЛОЖЕНИЕ А Блок-схема реализованного алгоритма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;