Прямые и двойственные задачи линейного программирования

 

 

 

Рисунок 2.1 – Общий вид матрицы исходных данных

 

Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b1,…, bi,…, bm); внизу каждого столбца - цена продуктов (с1,…, сj,…, сm).

В каждой клеточке матрицы записаны так называемые технологические коэффициенты aij, показывающие расход i-го ресурса на производство единицы j-го продукта.

Запишем конкретный числовой пример

 

Рисунок 2.2 – Пример матрицы исходных данных

 

2.2 Построение  математической модели

 

Теперь приступим к созданию математической модели, т.е. к математической записи задачи.

Целевая функция:

 

Ограничения:

x1 ³ 0;

x2 ³ 0;

x3 ³ 0.

 

Описание решения данной задачи

 

Решим поставленную выше задачу с применением MS EXCEL.

 

Рисунок 2.3 – Исходные данные для решения задачи

 

Содержание ячеек:

B1:D1 – имена продуктов (технологических способов);

A2:A4 – имена ресурсов;

B2:D4 – технологические коэффициенты (расход ресурсов при единичных интенсивностях технологических способов);

B6:D6 – цены продуктов;

B8:D8 – переменные;

F2:F4 – запас ресурсов;

G2:G4 – плановые расходы ресурсов, получаются в результате решения;

G6 – значение целевой функции, получается в результате решения.

Формулы для вычислений:

G2=СУММПРОИЗВ (B$8:D$8; B2:D2);

G3:G4 – копируются из G2;

G6=СУММПРОИЗВ (B8:D8; B6:D6).

Запишем формулы в ячейки G2:G4. Установить курсор на G2. На панели инструментов выбрать значок формул (f). Появятся два окна. В окне «категория» выбрать «математические», затем в окне «функция» выбрать «СУММПРОИЗВ». Появится окно «СУММПРОИЗВ». В нем нужно указать, где располагаются операнды. Первый операнд – строка B$8:D$8, второй операнд – стока B2:D2. В ячейки G3:G4 формулу скопировать из G2. Аналогичным образом записать формулу целевой функции в ячейку G6. Теперь нужно указать остальные условия решения задачи. Установить курсор на ячейку целевой функции G6. В главном меню выбрать «сервис», а потом «поиск решения». Появится окно, в котором нужно указать:

1. Целевая ячейка – G6;
2. Включить кнопку «максимальное значение»;
3. Указать изменяемые ячейки (расположение переменных) – B8:D8;
4. Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:

B8:D8 0 – неотрицательности переменных;

G2:G4 F2:F4 – плановый расход ресурсов меньше их запаса.

 

Рисунок 2.4 –  Мастер поиска решения

 

Теперь электронная модель сформирована и можно решать задачу. Для этого нужно вернуться в окно «поиск решения» и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Результаты, Устойчивость, Пределы.

 

Рисунок 2.5 – Результат количественного решения задачи

 

Основные результаты видны в таблице (Рисунок 2.3).

1. Значение  целевой функции в ячейке G6 = 15880;

2. Значения  переменных в ячейках B8:D8: х1 = 86, х2 = 0, х3 = 268; это значит, что 1-й продукт должен производиться в объеме 86 единиц, 2-й – 0, а 3-й – 286.

3. Плановый  расход ресурсов в ячейках  G2:G4: расход 1-го ресурса = 271,6, расход 2-го ресурса = 310, расход 3-го ресурса = 2200.

Как видно 1-й ресурс недоиспользован, а 2-й и 3-й израсходованы полностью.

 

 

 

 

 

 

 

3 КОМПЬЮТЕРНАЯ  РЕАЛИЗАЦИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ

 

 

3.1 Руководство  пользователю по программному

продукту «Pascal ABC»

 

Программа запускается открытием файла «Pascal ABC», внешний вид которого представлен на рисунке 3.1.После открытия файла в появившемся окне будет показан текст программы.

 

Рисунок 3.1 - Файл запуска программы Pascal ABC

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

 

uses crt;

После этого идет описание переменных и массива:

 

a:array [1..4,1..3] of real; b:array [1..3] of real; i,j,k,r:integer;     При помощи функции clrscr производится очистка   clrscr;

Затем идет заполнение массива

for i:=1 to 4 do

for j:=1 to 3 do

В программе имеется процедура, которая проверяет наличие текстового файла store.txt из действительных чисел, которые представляют собой вес каждого предмета, и если этого файла нет, то создаёт его. При создании файла требуется ввести количество всех предметов n и максимальную величину веса предмета, соответствующую минимальной грузоподъёмности рюкзака min. Если файл store.txt существует в папке с программой, выполняется подпрограмма, распределяющая предметы в наименьшее количество рюкзаков. Вначале количеству рюкзаков v, суммарному весу предметов w, количеству всех предметов n присваивается нулевое значение. Программа сначала подсчитывает количество всех предметов n (количество целых чисел, содержащихся в файле g). После этого выделяется память под массив целых чисел p[0..n], и все целые числа из файла store.txt записываются в массив p[n].:

 

if a[4,1]<a[4,2] then r:=1 else r:=2; for i:=1 to 3 do b[i]:=a[i,3]/a[i,r]; if (b[1]<b[2]) and (b[1]<b[3]) then k:=1 else if (b[2]<b[1]) and (b[2]<b[3]) then k:=2 else if (b[3]<b[1]) and (b[3]<b[2]) then k:=3;

Перед нами появляется диалоговое окно в котором нужно ввести данные по исходным ресурсам и затратам с ограничениями, как показано на рисунке 3.2.

 

Рисунок 3.2 - Рабочее окно программы Pascal ABC

После появившегося окна можно вводить данные.

 

Рисунок 3.3 - Данные вводимые в программе

После ввода данных на экране появляются посчитаные значения(рис.3.4).

 

Рисунок 3.4 - Вывод решения Pascal ABC

 

Таким образом, с помощью PascalABC была реализована Двойственная задача.

Данный программный продукт может находить разрешающие элементы, а так же оптимальное решение двойственной задачи.

3.2 Краткий вывод по компьютерной реализации двойственной задачи

 

Данная задача дискретного  программирования, была реализована мною в среде Pascal ABC. С помощью руководства для пользователя этой программы продукта человек как работающий в данной области дискретного программирования, так и обычный рядовой user может разобраться в принципе работы этой программы, а так же в алгоритме ее работы. Для удобства восприятия мною были приведены графические изображения ярлыков программы и рабочие окна, подробно объяснён порядок ввода данных и действий, совершаемых пользователем, для использования программ.

Так же мною описан принцип работы программного продукта, объяснены выполняемые в нём команды и алгоритм выполняемых вычислений.

После получения данных с помощью программы , написанной на языке Pascal ABC, можно убедиться в том что она работают корректно, ввиду одинаковых выводимых конечных данных в примере ручного варианта.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

.

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

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

 Данная задача позволяет находить оптимальное решение для различных экономических задач, что делает ее незаменимой в экономике. Двойственная задача очень практична и является одной из самых распространенных примеров дискретной оптимизации.

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ЛИТЕРАТУРЫ

 

 

1. Сигал И.Х. Введение в прикладное дискретное программирование. М.: Издательский дом “Вильямс”, 2000. – 500 с.
2. Д.И. Батищев, Е.А. Неймарк. Применение генетических алгоритмов к решению задач дискретной оптимизации. Н.:2007.-100 с.
3. Таха Х. Введение в исследование операций. М.: Издательский дом “Вильямс”, 2001. – 912 с.
4. Экономико-математические методы и модели / Под ред. А.В. Кузнецова. Мн.: БГЭУ, 1999. – 413 с.
5. Акулич И.Л. Математическое программирование. – М.: Наука. 1986.
6. Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация. Учебное пособие – Н.Новгород: ННГУ им. Н. И. Лобачевского. 2005. – 260 с
7. Сигал И.Х. Задача о рюкзаке: теория и вычислительные алгоритмы. – М.: МИИТ. 1999.
8. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. – М.: Наука, 1969.

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ А

program dvoystvennaya_zadacha;

uses crt;

 

var

a:array [1..4,1..3] of real;

b:array [1..3] of real;

i,j,k,r:integer;

begin

clrscr;

for i:=1 to 4 do

for j:=1 to 3 do

begin

     write('vvedite a[',i,';',j,']  ');

     readln(a[i,j]);

end;

 

while (a[4,1]<0) or (a[4,2]<0) do

begin

if a[4,1]<a[4,2] then r:=1 else r:=2;

for i:=1 to 3 do

b[i]:=a[i,3]/a[i,r];

if (b[1]<b[2]) and (b[1]<b[3]) then k:=1 else

if (b[2]<b[1]) and (b[2]<b[3]) then k:=2 else

if (b[3]<b[1]) and (b[3]<b[2]) then k:=3;

writeln('a[',k,';',r,']-razreshaushchiy element');

for i:=1 to 4 do

for j:=1 to 3 do begin

if (i<>k) and (j<>r) then

a[i,j]:=a[i,j]-(a[i,r]*a[k,j])/a[k,r]; end;

for j:=1 to 3 do

if j<>r then a[k,j]:=a[k,j]/a[k,r];

for i:=1 to 4 do

if i<>k then a[i,r]:=-(a[i,r]/a[k,r]);

 

a[k,r]:=1/a[k,r];

for i:=1 to 4 do

begin for j:=1 to 3 do

write (a[i,j]:5:2); writeln; end;

end;

writeln('x1=',a[1,3]:5:2);

writeln('x2=',a[2,3]:5:2);

writeln('z=',a[4,3]:5:2);

writeln('y1=',a[4,1]:5:2);

writeln('y2=',a[4,2]:5:2);

readln;

end.